Loading...
Searching...
No Matches
dlist.cc
/*************************************************************************/
/* */
/* Centre for Speech Technology Research */
/* University of Edinburgh, UK */
/* Copyright (c) 1996,1997 */
/* All Rights Reserved. */
/* */
/* Permission is hereby granted, free of charge, to use and distribute */
/* this software and its documentation without restriction, including */
/* without limitation the rights to use, copy, modify, merge, publish, */
/* distribute, sublicense, and/or sell copies of this work, and to */
/* permit persons to whom this work is furnished to do so, subject to */
/* the following conditions: */
/* 1. The code must retain the above copyright notice, this list of */
/* conditions and the following disclaimer. */
/* 2. Any modifications must be clearly marked as such. */
/* 3. Original authors' names are not deleted. */
/* 4. The authors' names are not used to endorse or promote products */
/* derived from this software without specific prior written */
/* permission. */
/* */
/* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
/* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
/* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
/* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
/* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
/* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
/* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
/* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
/* THIS SOFTWARE. */
/* */
/*************************************************************************/
/* Author : Alan W Black */
/* Date : February 1997 */
/*-----------------------------------------------------------------------*/
/* Decision lists */
/* These are like a right branching decision tree, yes answers are not */
/* partitioned any further. These are used for the Yarowsky-style */
/* homograph disambiguators */
/* */
/* Yarowsky, D. "Homograph Disambiguation in Text-to_Speech Synthesis" */
/* in "Progress in Speech Synthesis" eds van Santen, J. et al. Springer */
/* pp 157-172, 1996 */
/* Rivest, R.L. "Learning decision lists", Machine Learning 2:229-246 */
/* 1987 */
/* */
/*=======================================================================*/
#include <iostream>
#include <cstring>
#include "EST_Wagon.h"
#include "EST_FMatrix.h"
#include "EST_multistats.h"
static WDlist *wagon_decision_list();
static void do_dlist_summary(WDlist *dlist, WDataSet &dataset);
static WDlist *dlist_score_question(WQuestion &q, WVectorList &ds);
WNode *wgn_build_dlist(float &score,ostream *output)
{
WDlist *dlist;
dlist = wagon_decision_list();
*output << *dlist;
if (wgn_test_dataset.width() > 0) // load in test data
do_dlist_summary(dlist,wgn_test_dataset);
else
do_dlist_summary(dlist,wgn_dataset);
score = 0;
return 0;
}
static void do_dlist_summary(WDlist *dlist, WDataSet &dataset)
{
// Test dlist against data to get summary of results
EST_StrStr_KVL pairs;
EST_StrList lex;
EST_Litem *p;
EST_String predict,real;
int i,type;
for (p=dataset.head(); p != 0; p=p->next())
{
predict = (EST_String)dlist->predict(*dataset(p));
type = dataset.ftype(0);
real = wgn_discretes[type].name(dataset(p)->get_int_val(0));
pairs.add_item(real,predict,1);
}
for (i=0; i<wgn_discretes[dataset.ftype(0)].length(); i++)
lex.append(wgn_discretes[dataset.ftype(0)].name(i));
const EST_FMatrix &m = confusion(pairs,lex);
print_confusion(m,pairs,lex);
}
static WDlist *wagon_decision_list()
{
// For each possible question, measure it using
// yarowsky's loglikelihood ratio
// Abs(log(P(class_1|question_j)/P(class_2|question_j)))
// Output it for external sorting
// Hmm this implies binary classes
int i,cl;
WQuestion ques;
WDlist *dlist, *d;
dlist=0;
for (i=1;i < wgn_dataset.width(); i++)
{
if (wgn_dataset.ftype(i) == wndt_ignore)
continue;
else if (wgn_dataset.ftype(i) >= wndt_class)
{
ques.set_fp(i);
ques.set_oper(wnop_is);
for (cl=0; cl < wgn_discretes[wgn_dataset.ftype(i)].length(); cl++)
{
ques.set_operand1(EST_Val(cl));
d = dlist_score_question(ques,wgn_dataset);
if (d != 0)
dlist = add_to_dlist(dlist,d);
}
}
}
return dlist;
}
static WDlist *dlist_score_question(WQuestion &q, WVectorList &ds)
{
// score this question for decision lists
// the sum of the impurities when ds is split with this question
WImpurity y;
EST_Litem *d;
WVector *wv;
int i;
for (i=0,d=ds.head(); d != 0; d=d->next(),i++)
{
wv = ds(d);
if (q.ask(*wv) == TRUE)
y.cumulate((*wv)[0]);
}
if (y.samples() > wgn_min_cluster_size)
{
q.set_yes((int)y.samples());
EST_DiscreteProbDistribution &pd = y.pd();
// Generalizing the formula in Yarowsky (pp157-172) we modify it
// to take absolute log-likelihood ration of the most probability
// of the most probable over the rest
EST_String t;
double p;
double f;
WDlist *n = new WDlist;
n->set_question(q);
t = pd.most_probable(&p);
f = pd.frequency(t);
n->set_score(fabs(log((f+0.0001)/(pd.samples()-f+0.0001))));
n->set_best(t,(int)f,(int)pd.samples());
#if 0 // original two-case code
int freqa, freqb;
pd.item_freq(0,s,freqa);
pd.item_freq(1,s,freqb);
n->set_score(fabs(log((0.0001+freqa)/(0.0001+freqb))));
n->set_freqs(freqa,freqb);
#endif
return n;
}
return 0;
}
EST_Val WDlist::predict(const WVector &d)
{
if (p_question.ask(d))
return p_token;
else if (next == 0)
return "guess"; // should be a priori most probable as dlist can't help
else
return next->predict(d);
}
WDlist *add_to_dlist(WDlist *l, WDlist *a)
{
// Add a to l at appropriate place in score order
WDlist *p,*lp;
if (l == 0)
return a;
else
{
for (lp=0,p=l; p != 0; lp=p,p=p->next)
{
if (a->score() > p->score())
{
a->next = p;
if (lp == 0)
return a;
else
{
lp->next = a;
return l;
}
}
}
// add to end
lp->next = a;
}
return l;
}
ostream &operator <<(ostream &s, WDlist &dlist)
{
s << endl;
s << "(";
s << dlist.p_question;
s << " ((";
s << dlist.p_score;
s << " " << dlist.p_freq << " " << dlist.p_samples <<
" " << dlist.p_token << "))";
if (dlist.next != 0)
s << *dlist.next;
else
s << endl;
s << ")";
return s;
}
EST_DiscreteProbDistribution
Definition EST_simplestats.h:210
EST_DiscreteProbDistribution::item_freq
void item_freq(EST_Litem *idx, EST_String &s, double &freq) const
During iteration returns name and frequency given index.
Definition EST_DProbDist.cc:402
EST_DiscreteProbDistribution::most_probable
const EST_String & most_probable(double *prob=NULL) const
Return the most probable member of the distribution.
Definition EST_DProbDist.cc:182
EST_DiscreteProbDistribution::samples
double samples(void) const
Total number of example found.
Definition EST_simplestats.h:250
EST_FMatrix
Definition EST_FMatrix.h:56
EST_String
Definition EST_String.h:70
EST_TKVL::add_item
int add_item(const K &rkey, const V &rval, int no_search=0)
add key-val pair to list
Definition EST_TKVL.cc:248
EST_TList::append
void append(const T &item)
add item onto end of list
Definition EST_TList.h:191
EST_Val
Definition EST_Val.h:70
WDataSet
Definition EST_Wagon.h:86
WDlist
Definition EST_Wagon.h:199
WImpurity
Definition EST_Wagon.h:146
WNode
Definition EST_Wagon.h:222
WQuestion
Definition EST_Wagon.h:106
WVector
Definition EST_Wagon.h:65