smoothedNgramPredictor.cpp
Go to the documentation of this file.
/******************************************************
* Presage, an extensible predictive text entry system
* ---------------------------------------------------
*
* Copyright (C) 2008 Matteo Vescovi <matteo.vescovi@yahoo.co.uk>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*
**********(*)*/
#include "smoothedNgramPredictor.h"
#include <sstream>
#include <algorithm>
SmoothedNgramPredictor::SmoothedNgramPredictor(Configuration* config, ContextTracker* ct, const char* name)
: Predictor(config,
ct,
name,
"SmoothedNgramPredictor, a linear interpolating n-gram predictor",
"SmoothedNgramPredictor, long description." ),
db (0),
cardinality (0),
learn_mode_set (false),
dispatcher (this)
{
LOGGER = PREDICTORS + name + ".LOGGER";
DBFILENAME = PREDICTORS + name + ".DBFILENAME";
DELTAS = PREDICTORS + name + ".DELTAS";
LEARN = PREDICTORS + name + ".LEARN";
DATABASE_LOGGER = PREDICTORS + name + ".DatabaseConnector.LOGGER";
// build notification dispatch map
dispatcher.map (config->find (LOGGER), & SmoothedNgramPredictor::set_logger);
dispatcher.map (config->find (DATABASE_LOGGER), & SmoothedNgramPredictor::set_database_logger_level);
dispatcher.map (config->find (DBFILENAME), & SmoothedNgramPredictor::set_dbfilename);
dispatcher.map (config->find (DELTAS), & SmoothedNgramPredictor::set_deltas);
dispatcher.map (config->find (LEARN), & SmoothedNgramPredictor::set_learn);
}
SmoothedNgramPredictor::~SmoothedNgramPredictor()
{
delete db;
}
void SmoothedNgramPredictor::set_dbfilename (const std::string& filename)
{
dbfilename = filename;
logger << INFO << "DBFILENAME: " << dbfilename << endl;
init_database_connector_if_ready ();
}
void SmoothedNgramPredictor::set_database_logger_level (const std::string& value)
{
dbloglevel = value;
}
void SmoothedNgramPredictor::set_deltas (const std::string& value)
{
std::stringstream ss_deltas(value);
cardinality = 0;
std::string delta;
while (ss_deltas >> delta) {
logger << DEBUG << "Pushing delta: " << delta << endl;
deltas.push_back (Utility::toDouble (delta));
cardinality++;
}
logger << INFO << "DELTAS: " << value << endl;
logger << INFO << "CARDINALITY: " << cardinality << endl;
init_database_connector_if_ready ();
}
void SmoothedNgramPredictor::set_learn (const std::string& value)
{
learn_mode = Utility::isYes (value);
logger << INFO << "LEARN: " << value << endl;
learn_mode_set = true;
init_database_connector_if_ready ();
}
void SmoothedNgramPredictor::init_database_connector_if_ready ()
{
// we can only init the sqlite database connector once we know the
// following:
// - what database file we need to open
// - what cardinality we expect the database file to be
// - whether we need to open the database in read only or
// read/write mode (learning requires read/write access)
//
if (! dbfilename.empty()
&& cardinality > 0
&& learn_mode_set ) {
delete db;
if (dbloglevel.empty ()) {
// open database connector
db = new SqliteDatabaseConnector(dbfilename,
cardinality,
learn_mode);
} else {
// open database connector with logger lever
db = new SqliteDatabaseConnector(dbfilename,
cardinality,
learn_mode,
dbloglevel);
}
}
}
// convenience function to convert ngram to string
//
static std::string ngram_to_string(const Ngram& ngram)
{
const char separator[] = "|";
std::string result = separator;
for (Ngram::const_iterator it = ngram.begin();
it != ngram.end();
it++)
{
result += *it + separator;
}
return result;
}
unsigned int SmoothedNgramPredictor::count(const std::vector<std::string>& tokens, int offset, int ngram_size) const
{
unsigned int result = 0;
assert(offset <= 0); // TODO: handle this better
assert(ngram_size >= 0);
if (ngram_size > 0) {
Ngram ngram(ngram_size);
copy(tokens.end() - ngram_size + offset , tokens.end() + offset, ngram.begin());
result = db->getNgramCount(ngram);
logger << DEBUG << "count ngram: " << ngram_to_string (ngram) << " : " << result << endl;
} else {
result = db->getUnigramCountsSum();
logger << DEBUG << "unigram counts sum: " << result << endl;
}
return result;
}
Prediction SmoothedNgramPredictor::predict(const size_t max_partial_prediction_size, const char** filter) const
{
logger << DEBUG << "predict()" << endl;
// Result prediction
Prediction prediction;
// Cache all the needed tokens.
// tokens[k] corresponds to w_{i-k} in the generalized smoothed
// n-gram probability formula
//
std::vector<std::string> tokens(cardinality);
for (int i = 0; i < cardinality; i++) {
tokens[cardinality - 1 - i] = contextTracker->getToken(i);
logger << DEBUG << "Cached tokens[" << cardinality - 1 - i << "] = " << tokens[cardinality - 1 - i] << endl;
}
// Generate list of prefix completition candidates.
//
// The prefix completion candidates used to be obtained from the
// _1_gram table because in a well-constructed ngram database the
// _1_gram table (which contains all known tokens). However, this
// introduced a skew, since the unigram counts will take
// precedence over the higher-order counts.
//
// The current solution retrieves candidates from the highest
// n-gram table, falling back on lower order n-gram tables if
// initial completion set is smaller than required.
//
std::vector<std::string> prefixCompletionCandidates;
for (size_t k = cardinality; (k > 0 && prefixCompletionCandidates.size() < max_partial_prediction_size); k--) {
logger << DEBUG << "Building partial prefix completion table of cardinality: " << k << endl;
// create n-gram used to retrieve initial prefix completion table
Ngram prefix_ngram(k);
copy(tokens.end() - k, tokens.end(), prefix_ngram.begin());
if (logger.shouldLog()) {
logger << DEBUG << "prefix_ngram: ";
for (size_t r = 0; r < prefix_ngram.size(); r++) {
logger << DEBUG << prefix_ngram[r] << ' ';
}
logger << DEBUG << endl;
}
// obtain initial prefix completion candidates
db->beginTransaction();
NgramTable partial;
if (filter == 0) {
partial = db->getNgramLikeTable(prefix_ngram,max_partial_prediction_size - prefixCompletionCandidates.size());
} else {
partial = db->getNgramLikeTableFiltered(prefix_ngram,filter, max_partial_prediction_size - prefixCompletionCandidates.size());
}
db->endTransaction();
if (logger.shouldLog()) {
logger << DEBUG << "partial prefixCompletionCandidates" << endl
<< DEBUG << "----------------------------------" << endl;
for (size_t j = 0; j < partial.size(); j++) {
for (size_t k = 0; k < partial[j].size(); k++) {
logger << DEBUG << partial[j][k] << " ";
}
logger << endl;
}
}
logger << DEBUG << "Partial prefix completion table contains " << partial.size() << " potential completions." << endl;
// append newly discovered potential completions to prefix
// completion candidates array to fill it up to
// max_partial_prediction_size
//
std::vector<Ngram>::const_iterator it = partial.begin();
while (it != partial.end() && prefixCompletionCandidates.size() < max_partial_prediction_size) {
// only add new candidates, iterator it points to Ngram,
// it->end() - 2 points to the token candidate
//
std::string candidate = *(it->end() - 2);
if (find(prefixCompletionCandidates.begin(),
prefixCompletionCandidates.end(),
candidate) == prefixCompletionCandidates.end()) {
prefixCompletionCandidates.push_back(candidate);
}
it++;
}
}
if (logger.shouldLog()) {
logger << DEBUG << "prefixCompletionCandidates" << endl
<< DEBUG << "--------------------------" << endl;
for (size_t j = 0; j < prefixCompletionCandidates.size(); j++) {
logger << DEBUG << prefixCompletionCandidates[j] << endl;
}
}
// compute smoothed probabilities for all candidates
//
db->beginTransaction();
// getUnigramCountsSum is an expensive SQL query
// caching it here saves much time later inside the loop
int unigrams_counts_sum = db->getUnigramCountsSum();
for (size_t j = 0; (j < prefixCompletionCandidates.size() && j < max_partial_prediction_size); j++) {
// store w_i candidate at end of tokens
tokens[cardinality - 1] = prefixCompletionCandidates[j];
logger << DEBUG << "------------------" << endl;
logger << DEBUG << "w_i: " << tokens[cardinality - 1] << endl;
double probability = 0;
for (int k = 0; k < cardinality; k++) {
double numerator = count(tokens, 0, k+1);
// reuse cached unigrams_counts_sum to speed things up
double denominator = (k == 0 ? unigrams_counts_sum : count(tokens, -1, k));
double frequency = ((denominator > 0) ? (numerator / denominator) : 0);
probability += deltas[k] * frequency;
logger << DEBUG << "numerator: " << numerator << endl;
logger << DEBUG << "denominator: " << denominator << endl;
logger << DEBUG << "frequency: " << frequency << endl;
logger << DEBUG << "delta: " << deltas[k] << endl;
// for some sanity checks
assert(numerator <= denominator);
assert(frequency <= 1);
}
logger << DEBUG << "____________" << endl;
logger << DEBUG << "probability: " << probability << endl;
if (probability > 0) {
prediction.addSuggestion(Suggestion(tokens[cardinality - 1], probability));
}
}
db->endTransaction();
logger << DEBUG << "Prediction:" << endl;
logger << DEBUG << "-----------" << endl;
logger << DEBUG << prediction << endl;
return prediction;
}
void SmoothedNgramPredictor::learn(const std::vector<std::string>& change)
{
logger << INFO << "learn(\"" << ngram_to_string(change) << "\")" << endl;
if (learn_mode) {
// learning is turned on
std::map<std::list<std::string>, int> ngramMap;
// build up ngram map for all cardinalities
// i.e. learn all ngrams and counts in memory
for (size_t curr_cardinality = 1;
curr_cardinality < cardinality + 1;
curr_cardinality++)
{
int change_idx = 0;
int change_size = change.size();
std::list<std::string> ngram_list;
// take care of first N-1 tokens
for (int i = 0;
(i < curr_cardinality - 1 && change_idx < change_size);
i++)
{
ngram_list.push_back(change[change_idx]);
change_idx++;
}
while (change_idx < change_size)
{
ngram_list.push_back(change[change_idx++]);
ngramMap[ngram_list] = ngramMap[ngram_list] + 1;
ngram_list.pop_front();
}
}
// use (past stream - change) to learn token at the boundary
// change, i.e.
//
// if change is "bar foobar", then "bar" will only occur in a
// 1-gram, since there are no token before it. By dipping in
// the past stream, we additional context to learn a 2-gram by
// getting extra tokens (assuming past stream ends with token
// "foo":
//
// <"foo", "bar"> will be learnt
//
// We do this till we build up to n equal to cardinality.
//
// First check that change is not empty (nothing to learn) and
// that change and past stream match by sampling first and
// last token in change and comparing them with corresponding
// tokens from past stream
//
if (change.size() > 0 &&
change.back() == contextTracker->getToken(1) &&
change.front() == contextTracker->getToken(change.size()))
{
// create ngram list with first (oldest) token from change
std::list<std::string> ngram_list(change.begin(), change.begin() + 1);
// prepend token to ngram list by grabbing extra tokens
// from past stream (if there are any) till we have built
// up to n==cardinality ngrams, and commit them to
// ngramMap
//
for (int tk_idx = 1;
ngram_list.size() < cardinality;
tk_idx++)
{
// getExtraTokenToLearn returns tokens from
// past stream that come before and are not in
// change vector
//
std::string extra_token = contextTracker->getExtraTokenToLearn(tk_idx, change);
logger << DEBUG << "Adding extra token: " << extra_token << endl;
if (extra_token.empty())
{
break;
}
ngram_list.push_front(extra_token);
ngramMap[ngram_list] = ngramMap[ngram_list] + 1;
}
}
// then write out to language model database
try
{
db->beginTransaction();
std::map<std::list<std::string>, int>::const_iterator it;
for (it = ngramMap.begin(); it != ngramMap.end(); it++)
{
// convert ngram from list to vector based Ngram
Ngram ngram((it->first).begin(), (it->first).end());
// update the counts
int count = db->getNgramCount(ngram);
if (count > 0)
{
// ngram already in database, update count
db->updateNgram(ngram, count + it->second);
check_learn_consistency(ngram);
}
else
{
// ngram not in database, insert it
db->insertNgram(ngram, it->second);
}
}
db->endTransaction();
logger << INFO << "Committed learning update to database" << endl;
}
catch (SqliteDatabaseConnector::SqliteDatabaseConnectorException& ex)
{
db->rollbackTransaction();
logger << ERROR << "Rolling back learning update : " << ex.what() << endl;
throw;
}
}
logger << DEBUG << "end learn()" << endl;
}
void SmoothedNgramPredictor::check_learn_consistency(const Ngram& ngram) const
{
// no need to begin a new transaction, as we'll be called from
// within an existing transaction from learn()
// BEWARE: if the previous sentence is not true, then performance
// WILL suffer!
size_t size = ngram.size();
for (size_t i = 0; i < size; i++) {
if (count(ngram, -i, size - i) > count(ngram, -(i + 1), size - (i + 1))) {
logger << INFO << "consistency adjustment needed!" << endl;
int offset = -(i + 1);
int sub_ngram_size = size - (i + 1);
logger << DEBUG << "i: " << i << " | offset: " << offset << " | sub_ngram_size: " << sub_ngram_size << endl;
Ngram sub_ngram(sub_ngram_size); // need to init to right size for sub_ngram
copy(ngram.end() - sub_ngram_size + offset, ngram.end() + offset, sub_ngram.begin());
if (logger.shouldLog()) {
logger << "ngram to be count adjusted is: ";
for (size_t i = 0; i < sub_ngram.size(); i++) {
logger << sub_ngram[i] << ' ';
}
logger << endl;
}
db->incrementNgramCount(sub_ngram);
logger << DEBUG << "consistency adjusted" << endl;
}
}
}
void SmoothedNgramPredictor::update (const Observable* var)
{
logger << DEBUG << "About to invoke dispatcher: " << var->get_name () << " - " << var->get_value() << endl;
dispatcher.dispatch (var);
}
Predictor::logger
Logger< char > logger
Definition: predictor.h:87
SqliteDatabaseConnector
Definition: sqliteDatabaseConnector.h:43
Prediction
Definition: prediction.h:47
Dispatcher::dispatch
void dispatch(const Observable *var)
Definition: dispatcher.h:73
SmoothedNgramPredictor::~SmoothedNgramPredictor
~SmoothedNgramPredictor()
Definition: smoothedNgramPredictor.cpp:58
SmoothedNgramPredictor::dispatcher
Dispatcher< SmoothedNgramPredictor > dispatcher
Definition: smoothedNgramPredictor.h:83
Predictor
Definition: predictor.h:46
DatabaseConnector::getNgramCount
int getNgramCount(const Ngram ngram) const
Definition: databaseConnector.cpp:104
SmoothedNgramPredictor::learn_mode_set
bool learn_mode_set
Definition: smoothedNgramPredictor.h:81
DatabaseConnector::insertNgram
void insertNgram(const Ngram ngram, const int count) const
Definition: databaseConnector.cpp:180
SmoothedNgramPredictor::dbloglevel
std::string dbloglevel
Definition: smoothedNgramPredictor.h:77
PresageException::what
virtual const char * what() const
Definition: presageException.h:81
SmoothedNgramPredictor::learn
virtual void learn(const std::vector< std::string > &change)
Definition: smoothedNgramPredictor.cpp:335
SmoothedNgramPredictor::LEARN
std::string LEARN
Definition: smoothedNgramPredictor.h:62
DatabaseConnector::getNgramLikeTable
NgramTable getNgramLikeTable(const Ngram ngram, int limit=-1) const
Definition: databaseConnector.cpp:124
DatabaseConnector::getUnigramCountsSum
int getUnigramCountsSum() const
Definition: databaseConnector.cpp:87
SmoothedNgramPredictor::DBFILENAME
std::string DBFILENAME
Definition: smoothedNgramPredictor.h:60
SmoothedNgramPredictor::set_database_logger_level
void set_database_logger_level(const std::string &level)
Definition: smoothedNgramPredictor.cpp:73
Predictor::set_logger
virtual void set_logger(const std::string &level)
Definition: predictor.cpp:88
Configuration::find
Variable * find(const std::string &variable) const
Definition: configuration.cpp:46
smoothedNgramPredictor.h
config
std::string config
Definition: presageDemo.cpp:70
SmoothedNgramPredictor::set_deltas
void set_deltas(const std::string &deltas)
Definition: smoothedNgramPredictor.cpp:79
Predictor::PREDICTORS
const std::string PREDICTORS
Definition: predictor.h:81
ngram_to_string
static std::string ngram_to_string(const Ngram &ngram)
Definition: smoothedNgramPredictor.cpp:140
SmoothedNgramPredictor::deltas
std::vector< double > deltas
Definition: smoothedNgramPredictor.h:78
SmoothedNgramPredictor::init_database_connector_if_ready
void init_database_connector_if_ready()
Definition: smoothedNgramPredictor.cpp:107
Utility::toDouble
static double toDouble(const std::string)
Definition: utility.cpp:258
SmoothedNgramPredictor::count
unsigned int count(const std::vector< std::string > &tokens, int offset, int ngram_size) const
Builds the required n-gram and returns its count.
Definition: smoothedNgramPredictor.cpp:171
SqliteDatabaseConnector::SqliteDatabaseConnectorException
Definition: sqliteDatabaseConnector.h:58
SmoothedNgramPredictor::cardinality
size_t cardinality
Definition: smoothedNgramPredictor.h:79
SmoothedNgramPredictor::update
virtual void update(const Observable *variable)
Definition: smoothedNgramPredictor.cpp:499
NgramTable
std::vector< Ngram > NgramTable
Definition: databaseConnector.h:39
SmoothedNgramPredictor::DELTAS
std::string DELTAS
Definition: smoothedNgramPredictor.h:61
SmoothedNgramPredictor::set_learn
void set_learn(const std::string &learn_mode)
Definition: smoothedNgramPredictor.cpp:96
ContextTracker::getExtraTokenToLearn
std::string getExtraTokenToLearn(const int index, const std::vector< std::string > &change) const
Definition: contextTracker.cpp:231
SmoothedNgramPredictor::check_learn_consistency
void check_learn_consistency(const Ngram &name) const
Definition: smoothedNgramPredictor.cpp:464
Configuration
Definition: configuration.h:36
Observable::get_name
virtual std::string get_name() const =0
SmoothedNgramPredictor::SmoothedNgramPredictor
SmoothedNgramPredictor(Configuration *, ContextTracker *, const char *)
Definition: smoothedNgramPredictor.cpp:31
SmoothedNgramPredictor::learn_mode
bool learn_mode
Definition: smoothedNgramPredictor.h:80
DatabaseConnector::incrementNgramCount
int incrementNgramCount(const Ngram ngram) const
Definition: databaseConnector.cpp:156
DatabaseConnector::beginTransaction
virtual void beginTransaction() const
Definition: databaseConnector.cpp:335
DatabaseConnector::updateNgram
void updateNgram(const Ngram ngram, const int count) const
Definition: databaseConnector.cpp:191
Dispatcher::map
void map(Observable *var, const mbr_func_ptr_t &ptr)
Definition: dispatcher.h:62
DatabaseConnector::rollbackTransaction
virtual void rollbackTransaction() const
Definition: databaseConnector.cpp:345
Predictor::contextTracker
ContextTracker * contextTracker
Definition: predictor.h:83
SmoothedNgramPredictor::db
DatabaseConnector * db
Definition: smoothedNgramPredictor.h:75
SmoothedNgramPredictor::dbfilename
std::string dbfilename
Definition: smoothedNgramPredictor.h:76
DatabaseConnector::endTransaction
virtual void endTransaction() const
Definition: databaseConnector.cpp:340
Prediction::addSuggestion
void addSuggestion(Suggestion)
Definition: prediction.cpp:90
Utility::isYes
static bool isYes(const char *)
Definition: utility.cpp:185
SmoothedNgramPredictor::DATABASE_LOGGER
std::string DATABASE_LOGGER
Definition: smoothedNgramPredictor.h:63
SmoothedNgramPredictor::predict
virtual Prediction predict(const size_t size, const char **filter) const
Generate prediction.
Definition: smoothedNgramPredictor.cpp:191
Suggestion
Definition: suggestion.h:50
ContextTracker
Tracks user interaction and context.
Definition: contextTracker.h:155
Logger::shouldLog
bool shouldLog() const
Definition: logger.h:149
Observable::get_value
virtual std::string get_value() const =0
DatabaseConnector::getNgramLikeTableFiltered
NgramTable getNgramLikeTableFiltered(const Ngram ngram, const char **filter, int limit=-1) const
Definition: databaseConnector.cpp:140
Observable
Definition: observable.h:37
Ngram
Definition: ngram.h:33
SmoothedNgramPredictor::set_dbfilename
void set_dbfilename(const std::string &filename)
Definition: smoothedNgramPredictor.cpp:64
SmoothedNgramPredictor::LOGGER
std::string LOGGER
Definition: smoothedNgramPredictor.h:59
endl
const Logger< _charT, _Traits > & endl(const Logger< _charT, _Traits > &lgr)
Definition: logger.h:278
ContextTracker::getToken
std::string getToken(const int) const
Definition: contextTracker.cpp:191