2
* This program is free software; you can redistribute it and/or modify
3
* it under the terms of the GNU General Public License as published by
4
* the Free Software Foundation; either version 2 of the License, or
5
* (at your option) any later version.
7
* This program is distributed in the hope that it will be useful,
8
* but WITHOUT ANY WARRANTY; without even the implied warranty of
9
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10
* GNU General Public License for more details.
12
* You should have received a copy of the GNU General Public License
13
* along with this program; if not, write to the Free Software
14
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19
* Copyright (C) 2005 University of Waikato, Hamilton, New Zealand
23
package weka.classifiers.mi;
25
import weka.classifiers.RandomizableClassifier;
26
import weka.core.Capabilities;
27
import weka.core.Instance;
28
import weka.core.Instances;
29
import weka.core.MultiInstanceCapabilitiesHandler;
30
import weka.core.Optimization;
31
import weka.core.Option;
32
import weka.core.OptionHandler;
33
import weka.core.TechnicalInformation;
34
import weka.core.TechnicalInformationHandler;
35
import weka.core.Utils;
36
import weka.core.Capabilities.Capability;
37
import weka.core.TechnicalInformation.Field;
38
import weka.core.TechnicalInformation.Type;
40
import java.util.Enumeration;
41
import java.util.Random;
42
import java.util.Vector;
45
<!-- globalinfo-start -->
46
* Two-Level Distribution approach, changes the starting value of the searching algorithm, supplement the cut-off modification and check missing values.<br/>
48
* For more information see:<br/>
50
* Xin Xu (2003). Statistical learning in multiple instance problem. Hamilton, NZ.
52
<!-- globalinfo-end -->
54
<!-- technical-bibtex-start -->
57
* @mastersthesis{Xu2003,
58
* address = {Hamilton, NZ},
61
* school = {University of Waikato},
62
* title = {Statistical learning in multiple instance problem},
67
<!-- technical-bibtex-end -->
69
<!-- options-start -->
70
* Valid options are: <p/>
73
* Set whether or not use empirical
74
* log-odds cut-off instead of 0</pre>
76
* <pre> -R <numOfRuns>
77
* Set the number of multiple runs
78
* needed for searching the MLE.</pre>
80
* <pre> -S <num>
85
* If set, classifier is run in debug mode and
86
* may output additional info to the console</pre>
90
* @author Eibe Frank (eibe@cs.waikato.ac.nz)
91
* @author Xin Xu (xx5@cs.waikato.ac.nz)
92
* @version $Revision: 1.5 $
95
extends RandomizableClassifier
96
implements OptionHandler, MultiInstanceCapabilitiesHandler,
97
TechnicalInformationHandler {
99
/** for serialization */
100
static final long serialVersionUID = 6657315525171152210L;
102
/** The mean for each attribute of each positive exemplar */
103
protected double[][] m_MeanP = null;
105
/** The variance for each attribute of each positive exemplar */
106
protected double[][] m_VarianceP = null;
108
/** The mean for each attribute of each negative exemplar */
109
protected double[][] m_MeanN = null;
111
/** The variance for each attribute of each negative exemplar */
112
protected double[][] m_VarianceN = null;
114
/** The effective sum of weights of each positive exemplar in each dimension*/
115
protected double[][] m_SumP = null;
117
/** The effective sum of weights of each negative exemplar in each dimension*/
118
protected double[][] m_SumN = null;
120
/** The parameters to be estimated for each positive exemplar*/
121
protected double[] m_ParamsP = null;
123
/** The parameters to be estimated for each negative exemplar*/
124
protected double[] m_ParamsN = null;
126
/** The dimension of each exemplar, i.e. (numAttributes-2) */
127
protected int m_Dimension = 0;
129
/** The class label of each exemplar */
130
protected double[] m_Class = null;
132
/** The number of class labels in the data */
133
protected int m_NumClasses = 2;
135
/** The very small number representing zero */
136
static public double ZERO = 1.0e-6;
138
/** The number of runs to perform */
139
protected int m_Run = 1;
141
protected double m_Cutoff;
143
protected boolean m_UseEmpiricalCutOff = false;
146
* Returns a string describing this filter
148
* @return a description of the filter suitable for
149
* displaying in the explorer/experimenter gui
151
public String globalInfo() {
153
"Two-Level Distribution approach, changes the starting value of "
154
+ "the searching algorithm, supplement the cut-off modification and "
155
+ "check missing values.\n\n"
156
+ "For more information see:\n\n"
157
+ getTechnicalInformation().toString();
161
* Returns an instance of a TechnicalInformation object, containing
162
* detailed information about the technical background of this class,
163
* e.g., paper reference or book this class is based on.
165
* @return the technical information about this class
167
public TechnicalInformation getTechnicalInformation() {
168
TechnicalInformation result;
170
result = new TechnicalInformation(Type.MASTERSTHESIS);
171
result.setValue(Field.AUTHOR, "Xin Xu");
172
result.setValue(Field.YEAR, "2003");
173
result.setValue(Field.TITLE, "Statistical learning in multiple instance problem");
174
result.setValue(Field.SCHOOL, "University of Waikato");
175
result.setValue(Field.ADDRESS, "Hamilton, NZ");
176
result.setValue(Field.NOTE, "0657.594");
182
* Returns default capabilities of the classifier.
184
* @return the capabilities of this classifier
186
public Capabilities getCapabilities() {
187
Capabilities result = super.getCapabilities();
190
result.enable(Capability.NOMINAL_ATTRIBUTES);
191
result.enable(Capability.RELATIONAL_ATTRIBUTES);
192
result.enable(Capability.MISSING_VALUES);
195
result.enable(Capability.BINARY_CLASS);
196
result.enable(Capability.MISSING_CLASS_VALUES);
199
result.enable(Capability.ONLY_MULTIINSTANCE);
205
* Returns the capabilities of this multi-instance classifier for the
208
* @return the capabilities of this object
211
public Capabilities getMultiInstanceCapabilities() {
212
Capabilities result = super.getCapabilities();
215
result.enable(Capability.NUMERIC_ATTRIBUTES);
216
result.enable(Capability.MISSING_VALUES);
219
result.disableAllClasses();
220
result.enable(Capability.NO_CLASS);
227
* @param exs the training exemplars
228
* @throws Exception if the model cannot be built properly
230
public void buildClassifier(Instances exs)throws Exception{
231
// can classifier handle the data?
232
getCapabilities().testWithFail(exs);
234
// remove instances with missing class
235
exs = new Instances(exs);
236
exs.deleteWithMissingClass();
238
int numegs = exs.numInstances();
239
m_Dimension = exs.attribute(1).relation(). numAttributes();
240
Instances pos = new Instances(exs, 0), neg = new Instances(exs, 0);
242
for(int u=0; u<numegs; u++){
243
Instance example = exs.instance(u);
244
if(example.classValue() == 1)
250
int pnum = pos.numInstances(), nnum = neg.numInstances();
252
m_MeanP = new double[pnum][m_Dimension];
253
m_VarianceP = new double[pnum][m_Dimension];
254
m_SumP = new double[pnum][m_Dimension];
255
m_MeanN = new double[nnum][m_Dimension];
256
m_VarianceN = new double[nnum][m_Dimension];
257
m_SumN = new double[nnum][m_Dimension];
258
m_ParamsP = new double[4*m_Dimension];
259
m_ParamsN = new double[4*m_Dimension];
261
// Estimation of the parameters: as the start value for search
262
double[] pSumVal=new double[m_Dimension], // for m
263
nSumVal=new double[m_Dimension];
264
double[] maxVarsP=new double[m_Dimension], // for a
265
maxVarsN=new double[m_Dimension];
266
// Mean of sample variances: for b, b=a/E(\sigma^2)+2
267
double[] varMeanP = new double[m_Dimension],
268
varMeanN = new double[m_Dimension];
269
// Variances of sample means: for w, w=E[var(\mu)]/E[\sigma^2]
270
double[] meanVarP = new double[m_Dimension],
271
meanVarN = new double[m_Dimension];
272
// number of exemplars without all values missing
273
double[] numExsP = new double[m_Dimension],
274
numExsN = new double[m_Dimension];
276
// Extract metadata fro both positive and negative bags
277
for(int v=0; v < pnum; v++){
278
/*Exemplar px = pos.exemplar(v);
279
m_MeanP[v] = px.meanOrMode();
280
m_VarianceP[v] = px.variance();
281
Instances pxi = px.getInstances();
284
Instances pxi = pos.instance(v).relationalValue(1);
285
for (int k=0; k<pxi.numAttributes(); k++) {
286
m_MeanP[v][k] = pxi.meanOrMode(k);
287
m_VarianceP[v][k] = pxi.variance(k);
290
for (int w=0,t=0; w < m_Dimension; w++,t++){
291
//if((t==m_ClassIndex) || (t==m_IdIndex))
294
if(!Double.isNaN(m_MeanP[v][w])){
295
for(int u=0;u<pxi.numInstances();u++){
296
Instance ins = pxi.instance(u);
297
if(!ins.isMissing(t))
298
m_SumP[v][w] += ins.weight();
301
pSumVal[w] += m_MeanP[v][w];
302
meanVarP[w] += m_MeanP[v][w]*m_MeanP[v][w];
303
if(maxVarsP[w] < m_VarianceP[v][w])
304
maxVarsP[w] = m_VarianceP[v][w];
305
varMeanP[w] += m_VarianceP[v][w];
306
m_VarianceP[v][w] *= (m_SumP[v][w]-1.0);
307
if(m_VarianceP[v][w] < 0.0)
308
m_VarianceP[v][w] = 0.0;
313
for(int v=0; v < nnum; v++){
314
/*Exemplar nx = neg.exemplar(v);
315
m_MeanN[v] = nx.meanOrMode();
316
m_VarianceN[v] = nx.variance();
317
Instances nxi = nx.getInstances();
319
Instances nxi = neg.instance(v).relationalValue(1);
320
for (int k=0; k<nxi.numAttributes(); k++) {
321
m_MeanN[v][k] = nxi.meanOrMode(k);
322
m_VarianceN[v][k] = nxi.variance(k);
325
for (int w=0,t=0; w < m_Dimension; w++,t++){
326
//if((t==m_ClassIndex) || (t==m_IdIndex))
329
if(!Double.isNaN(m_MeanN[v][w])){
330
for(int u=0;u<nxi.numInstances();u++)
331
if(!nxi.instance(u).isMissing(t))
332
m_SumN[v][w] += nxi.instance(u).weight();
334
nSumVal[w] += m_MeanN[v][w];
335
meanVarN[w] += m_MeanN[v][w]*m_MeanN[v][w];
336
if(maxVarsN[w] < m_VarianceN[v][w])
337
maxVarsN[w] = m_VarianceN[v][w];
338
varMeanN[w] += m_VarianceN[v][w];
339
m_VarianceN[v][w] *= (m_SumN[v][w]-1.0);
340
if(m_VarianceN[v][w] < 0.0)
341
m_VarianceN[v][w] = 0.0;
346
for(int w=0; w<m_Dimension; w++){
347
pSumVal[w] /= numExsP[w];
348
nSumVal[w] /= numExsN[w];
350
meanVarP[w] = meanVarP[w]/(numExsP[w]-1.0)
351
- pSumVal[w]*numExsP[w]/(numExsP[w]-1.0);
353
meanVarN[w] = meanVarN[w]/(numExsN[w]-1.0)
354
- nSumVal[w]*numExsN[w]/(numExsN[w]-1.0);
355
varMeanP[w] /= numExsP[w];
356
varMeanN[w] /= numExsN[w];
359
//Bounds and parameter values for each run
360
double[][] bounds = new double[2][4];
361
double[] pThisParam = new double[4],
362
nThisParam = new double[4];
364
// Initial values for parameters
367
// Optimize for one dimension
368
for (int x=0; x < m_Dimension; x++){
370
System.err.println("\n\n!!!!!!!!!!!!!!!!!!!!!!???Dimension #"+x);
372
// Positive examplars: first run
373
a = (maxVarsP[x]>ZERO) ? maxVarsP[x]:1.0;
374
if (varMeanP[x]<=ZERO) varMeanP[x] = ZERO; // modified by LinDong (09/2005)
375
b = a/varMeanP[x]+2.0; // a/(b-2) = E(\sigma^2)
376
w = meanVarP[x]/varMeanP[x]; // E[var(\mu)] = w*E[\sigma^2]
380
pThisParam[0] = a; // a
381
pThisParam[1] = b; // b
382
pThisParam[2] = w; // w
383
pThisParam[3] = m; // m
385
// Negative examplars: first run
386
a = (maxVarsN[x]>ZERO) ? maxVarsN[x]:1.0;
387
if (varMeanN[x]<=ZERO) varMeanN[x] = ZERO; // modified by LinDong (09/2005)
388
b = a/varMeanN[x]+2.0; // a/(b-2) = E(\sigma^2)
389
w = meanVarN[x]/varMeanN[x]; // E[var(\mu)] = w*E[\sigma^2]
393
nThisParam[0] = a; // a
394
nThisParam[1] = b; // b
395
nThisParam[2] = w; // w
396
nThisParam[3] = m; // m
399
bounds[0][0] = ZERO; // a > 0
400
bounds[0][1] = 2.0+ZERO; // b > 2
401
bounds[0][2] = ZERO; // w > 0
402
bounds[0][3] = Double.NaN;
404
for(int t=0; t<4; t++){
405
bounds[1][t] = Double.NaN;
406
m_ParamsP[4*x+t] = pThisParam[t];
407
m_ParamsN[4*x+t] = nThisParam[t];
409
double pminVal=Double.MAX_VALUE, nminVal=Double.MAX_VALUE;
410
Random whichEx = new Random(m_Seed);
411
TLD_Optm pOp=null, nOp=null;
412
boolean isRunValid = true;
413
double[] sumP=new double[pnum], meanP=new double[pnum],
414
varP=new double[pnum];
415
double[] sumN=new double[nnum], meanN=new double[nnum],
416
varN=new double[nnum];
419
for(int p=0; p<pnum; p++){
420
sumP[p] = m_SumP[p][x];
421
meanP[p] = m_MeanP[p][x];
422
varP[p] = m_VarianceP[p][x];
424
for(int q=0; q<nnum; q++){
425
sumN[q] = m_SumN[q][x];
426
meanN[q] = m_MeanN[q][x];
427
varN[q] = m_VarianceN[q][x];
430
for(int y=0; y<m_Run;){
432
System.err.println("\n\n!!!!!!!!!!!!!!!!!!!!!!???Run #"+y);
436
System.err.println("\nPositive exemplars");
437
pOp = new TLD_Optm();
439
pOp.setSSquare(varP);
442
pThisParam = pOp.findArgmin(pThisParam, bounds);
443
while(pThisParam==null){
444
pThisParam = pOp.getVarbValues();
446
System.err.println("!!! 200 iterations finished, not enough!");
447
pThisParam = pOp.findArgmin(pThisParam, bounds);
450
thisMin = pOp.getMinFunction();
451
if(!Double.isNaN(thisMin) && (thisMin<pminVal)){
453
for(int z=0; z<4; z++)
454
m_ParamsP[4*x+z] = pThisParam[z];
457
if(Double.isNaN(thisMin)){
458
pThisParam = new double[4];
463
System.err.println("\nNegative exemplars");
464
nOp = new TLD_Optm();
466
nOp.setSSquare(varN);
469
nThisParam = nOp.findArgmin(nThisParam, bounds);
470
while(nThisParam==null){
471
nThisParam = nOp.getVarbValues();
473
System.err.println("!!! 200 iterations finished, not enough!");
474
nThisParam = nOp.findArgmin(nThisParam, bounds);
476
thisMin = nOp.getMinFunction();
477
if(!Double.isNaN(thisMin) && (thisMin<nminVal)){
479
for(int z=0; z<4; z++)
480
m_ParamsN[4*x+z] = nThisParam[z];
483
if(Double.isNaN(thisMin)){
484
nThisParam = new double[4];
488
if(!isRunValid){ y--; isRunValid=true; }
491
// Change the initial parameters and restart
492
int pone = whichEx.nextInt(pnum), // Randomly pick one pos. exmpl.
493
none = whichEx.nextInt(nnum);
495
// Positive exemplars: next run
496
while((m_SumP[pone][x]<=1.0)||Double.isNaN(m_MeanP[pone][x]))
497
pone = whichEx.nextInt(pnum);
499
a = m_VarianceP[pone][x]/(m_SumP[pone][x]-1.0);
500
if(a<=ZERO) a=m_ParamsN[4*x]; // Change to negative params
501
m = m_MeanP[pone][x];
502
double sq = (m-m_ParamsP[4*x+3])*(m-m_ParamsP[4*x+3]);
504
b = a*m_ParamsP[4*x+2]/sq+2.0; // b=a/Var+2, assuming Var=Sq/w'
505
if((b<=ZERO) || Double.isNaN(b) || Double.isInfinite(b))
508
w = sq*(m_ParamsP[4*x+1]-2.0)/m_ParamsP[4*x];//w=Sq/Var, assuming Var=a'/(b'-2)
509
if((w<=ZERO) || Double.isNaN(w) || Double.isInfinite(w))
512
pThisParam[0] = a; // a
513
pThisParam[1] = b; // b
514
pThisParam[2] = w; // w
515
pThisParam[3] = m; // m
517
// Negative exemplars: next run
518
while((m_SumN[none][x]<=1.0)||Double.isNaN(m_MeanN[none][x]))
519
none = whichEx.nextInt(nnum);
521
a = m_VarianceN[none][x]/(m_SumN[none][x]-1.0);
522
if(a<=ZERO) a=m_ParamsP[4*x];
523
m = m_MeanN[none][x];
524
sq = (m-m_ParamsN[4*x+3])*(m-m_ParamsN[4*x+3]);
526
b = a*m_ParamsN[4*x+2]/sq+2.0; // b=a/Var+2, assuming Var=Sq/w'
527
if((b<=ZERO) || Double.isNaN(b) || Double.isInfinite(b))
530
w = sq*(m_ParamsN[4*x+1]-2.0)/m_ParamsN[4*x];//w=Sq/Var, assuming Var=a'/(b'-2)
531
if((w<=ZERO) || Double.isNaN(w) || Double.isInfinite(w))
534
nThisParam[0] = a; // a
535
nThisParam[1] = b; // b
536
nThisParam[2] = w; // w
537
nThisParam[3] = m; // m
542
for (int x=0, y=0; x<m_Dimension; x++, y++){
543
//if((x==exs.classIndex()) || (x==exs.idIndex()))
545
a=m_ParamsP[4*x]; b=m_ParamsP[4*x+1];
546
w=m_ParamsP[4*x+2]; m=m_ParamsP[4*x+3];
548
System.err.println("\n\n???Positive: ( "+exs.attribute(1).relation().attribute(y)+
549
"): a="+a+", b="+b+", w="+w+", m="+m);
551
a=m_ParamsN[4*x]; b=m_ParamsN[4*x+1];
552
w=m_ParamsN[4*x+2]; m=m_ParamsN[4*x+3];
554
System.err.println("???Negative: ("+exs.attribute(1).relation().attribute(y)+
555
"): a="+a+", b="+b+", w="+w+", m="+m);
558
if(m_UseEmpiricalCutOff){
559
// Find the empirical cut-off
560
double[] pLogOdds=new double[pnum], nLogOdds=new double[nnum];
561
for(int p=0; p<pnum; p++)
563
likelihoodRatio(m_SumP[p], m_MeanP[p], m_VarianceP[p]);
565
for(int q=0; q<nnum; q++)
567
likelihoodRatio(m_SumN[q], m_MeanN[q], m_VarianceN[q]);
570
findCutOff(pLogOdds, nLogOdds);
573
m_Cutoff = -Math.log((double)pnum/(double)nnum);
576
System.err.println("???Cut-off="+m_Cutoff);
581
* @param ex the given test exemplar
582
* @return the classification
583
* @throws Exception if the exemplar could not be classified
586
public double classifyInstance(Instance ex)throws Exception{
587
//Exemplar ex = new Exemplar(e);
588
Instances exi = ex.relationalValue(1);
589
double[] n = new double[m_Dimension];
590
double [] xBar = new double[m_Dimension];
591
double [] sSq = new double[m_Dimension];
592
for (int i=0; i<exi.numAttributes() ; i++){
593
xBar[i] = exi.meanOrMode(i);
594
sSq[i] = exi.variance(i);
597
for (int w=0, t=0; w < m_Dimension; w++, t++){
598
//if((t==m_ClassIndex) || (t==m_IdIndex))
600
for(int u=0;u<exi.numInstances();u++)
601
if(!exi.instance(u).isMissing(t))
602
n[w] += exi.instance(u).weight();
604
sSq[w] = sSq[w]*(n[w]-1.0);
609
double logOdds = likelihoodRatio(n, xBar, sSq);
610
return (logOdds > m_Cutoff) ? 1 : 0 ;
613
private double likelihoodRatio(double[] n, double[] xBar, double[] sSq){
614
double LLP = 0.0, LLN = 0.0;
616
for (int x=0; x<m_Dimension; x++){
617
if(Double.isNaN(xBar[x])) continue; // All missing values
619
int halfN = ((int)n[x])/2;
620
//Log-likelihood for positive
621
double a=m_ParamsP[4*x], b=m_ParamsP[4*x+1],
622
w=m_ParamsP[4*x+2], m=m_ParamsP[4*x+3];
623
LLP += 0.5*b*Math.log(a) + 0.5*(b+n[x]-1.0)*Math.log(1.0+n[x]*w)
624
- 0.5*(b+n[x])*Math.log((1.0+n[x]*w)*(a+sSq[x])+
625
n[x]*(xBar[x]-m)*(xBar[x]-m))
626
- 0.5*n[x]*Math.log(Math.PI);
627
for(int y=1; y<=halfN; y++)
628
LLP += Math.log(b/2.0+n[x]/2.0-(double)y);
630
if(n[x]/2.0 > halfN) // n is odd
631
LLP += TLD_Optm.diffLnGamma(b/2.0);
633
//Log-likelihood for negative
638
LLN += 0.5*b*Math.log(a) + 0.5*(b+n[x]-1.0)*Math.log(1.0+n[x]*w)
639
- 0.5*(b+n[x])*Math.log((1.0+n[x]*w)*(a+sSq[x])+
640
n[x]*(xBar[x]-m)*(xBar[x]-m))
641
- 0.5*n[x]*Math.log(Math.PI);
642
for(int y=1; y<=halfN; y++)
643
LLN += Math.log(b/2.0+n[x]/2.0-(double)y);
645
if(n[x]/2.0 > halfN) // n is odd
646
LLN += TLD_Optm.diffLnGamma(b/2.0);
652
private void findCutOff(double[] pos, double[] neg){
653
int[] pOrder = Utils.sort(pos),
654
nOrder = Utils.sort(neg);
656
System.err.println("\n\n???Positive: ");
657
for(int t=0; t<pOrder.length; t++)
658
System.err.print(t+":"+Utils.doubleToString(pos[pOrder[t]],0,2)+" ");
659
System.err.println("\n\n???Negative: ");
660
for(int t=0; t<nOrder.length; t++)
661
System.err.print(t+":"+Utils.doubleToString(neg[nOrder[t]],0,2)+" ");
663
int pNum = pos.length, nNum = neg.length, count, p=0, n=0;
664
double fstAccu=0.0, sndAccu=(double)pNum, split;
665
double maxAccu = 0, minDistTo0 = Double.MAX_VALUE;
667
// Skip continuous negatives
668
for(;(n<nNum)&&(pos[pOrder[0]]>=neg[nOrder[n]]); n++, fstAccu++);
670
if(n>=nNum){ // totally seperate
671
m_Cutoff = (neg[nOrder[nNum-1]]+pos[pOrder[0]])/2.0;
672
//m_Cutoff = neg[nOrder[nNum-1]];
677
while((p<pNum)&&(n<nNum)){
678
// Compare the next in the two lists
679
if(pos[pOrder[p]]>=neg[nOrder[n]]){ // Neg has less log-odds
681
split=neg[nOrder[n]];
686
split=pos[pOrder[p]];
690
if((fstAccu+sndAccu > maxAccu)
691
|| ((fstAccu+sndAccu == maxAccu) && (Math.abs(split)<minDistTo0))){
692
maxAccu = fstAccu+sndAccu;
694
minDistTo0 = Math.abs(split);
700
* Returns an enumeration describing the available options
702
* @return an enumeration of all the available options
704
public Enumeration listOptions() {
705
Vector result = new Vector();
707
result.addElement(new Option(
708
"\tSet whether or not use empirical\n"
709
+ "\tlog-odds cut-off instead of 0",
712
result.addElement(new Option(
713
"\tSet the number of multiple runs \n"
714
+ "\tneeded for searching the MLE.",
715
"R", 1, "-R <numOfRuns>"));
717
Enumeration enu = super.listOptions();
718
while (enu.hasMoreElements()) {
719
result.addElement(enu.nextElement());
722
return result.elements();
726
* Parses a given list of options. <p/>
728
<!-- options-start -->
729
* Valid options are: <p/>
732
* Set whether or not use empirical
733
* log-odds cut-off instead of 0</pre>
735
* <pre> -R <numOfRuns>
736
* Set the number of multiple runs
737
* needed for searching the MLE.</pre>
739
* <pre> -S <num>
740
* Random number seed.
744
* If set, classifier is run in debug mode and
745
* may output additional info to the console</pre>
749
* @param options the list of options as an array of strings
750
* @throws Exception if an option is not supported
752
public void setOptions(String[] options) throws Exception{
753
setDebug(Utils.getFlag('D', options));
755
setUsingCutOff(Utils.getFlag('C', options));
757
String runString = Utils.getOption('R', options);
758
if (runString.length() != 0)
759
setNumRuns(Integer.parseInt(runString));
763
super.setOptions(options);
767
* Gets the current settings of the Classifier.
769
* @return an array of strings suitable for passing to setOptions
771
public String[] getOptions() {
776
result = new Vector();
777
options = super.getOptions();
778
for (i = 0; i < options.length; i++)
779
result.add(options[i]);
784
if (getUsingCutOff())
788
result.add("" + getNumRuns());
790
return (String[]) result.toArray(new String[result.size()]);
794
* Returns the tip text for this property
796
* @return tip text for this property suitable for
797
* displaying in the explorer/experimenter gui
799
public String numRunsTipText() {
800
return "The number of runs to perform.";
804
* Sets the number of runs to perform.
806
* @param numRuns the number of runs to perform
808
public void setNumRuns(int numRuns) {
813
* Returns the number of runs to perform.
815
* @return the number of runs to perform
817
public int getNumRuns() {
822
* Returns the tip text for this property
824
* @return tip text for this property suitable for
825
* displaying in the explorer/experimenter gui
827
public String usingCutOffTipText() {
828
return "Whether to use an empirical cutoff.";
832
* Sets whether to use an empirical cutoff.
834
* @param cutOff whether to use an empirical cutoff
836
public void setUsingCutOff (boolean cutOff) {
837
m_UseEmpiricalCutOff = cutOff;
841
* Returns whether an empirical cutoff is used
843
* @return true if an empirical cutoff is used
845
public boolean getUsingCutOff() {
846
return m_UseEmpiricalCutOff;
850
* Main method for testing.
852
* @param args the options for the classifier
854
public static void main(String[] args) {
855
runClassifier(new TLD(), args);
859
class TLD_Optm extends Optimization{
861
private double[] num;
862
private double[] sSq;
863
private double[] xBar;
865
public void setNum(double[] n) {num = n;}
866
public void setSSquare(double[] s){sSq = s;}
867
public void setXBar(double[] x){xBar = x;}
870
* Compute Ln[Gamma(b+0.5)] - Ln[Gamma(b)]
872
* @param b the value in the above formula
875
public static double diffLnGamma(double b){
876
double[] coef= {76.18009172947146, -86.50532032941677,
877
24.01409824083091, -1.231739572450155,
878
0.1208650973866179e-2, -0.5395239384953e-5};
880
rt += (b+1.0)*Math.log(b+6.0) - (b+0.5)*Math.log(b+5.5);
881
double series1=1.000000000190015, series2=1.000000000190015;
882
for(int i=0; i<6; i++){
883
series1 += coef[i]/(b+1.5+(double)i);
884
series2 += coef[i]/(b+1.0+(double)i);
887
rt += Math.log(series1*b)-Math.log(series2*(b+0.5));
892
* Compute dLn[Gamma(x+0.5)]/dx - dLn[Gamma(x)]/dx
894
* @param x the value in the above formula
897
protected double diffFstDervLnGamma(double x){
898
double rt=0, series=1.0;// Just make it >0
899
for(int i=0;series>=m_Zero*1e-3;i++){
900
series = 0.5/((x+(double)i)*(x+(double)i+0.5));
907
* Compute {Ln[Gamma(x+0.5)]}'' - {Ln[Gamma(x)]}''
909
* @param x the value in the above formula
912
protected double diffSndDervLnGamma(double x){
913
double rt=0, series=1.0;// Just make it >0
914
for(int i=0;series>=m_Zero*1e-3;i++){
915
series = (x+(double)i+0.25)/
916
((x+(double)i)*(x+(double)i)*(x+(double)i+0.5)*(x+(double)i+0.5));
923
* Implement this procedure to evaluate objective
924
* function to be minimized
926
protected double objectiveFunction(double[] x){
927
int numExs = num.length;
928
double NLL = 0; // Negative Log-Likelihood
930
double a=x[0], b=x[1], w=x[2], m=x[3];
931
for(int j=0; j < numExs; j++){
933
if(Double.isNaN(xBar[j])) continue; // All missing values
935
NLL += 0.5*(b+num[j])*
936
Math.log((1.0+num[j]*w)*(a+sSq[j]) +
937
num[j]*(xBar[j]-m)*(xBar[j]-m));
939
if(Double.isNaN(NLL) && m_Debug){
940
System.err.println("???????????1: "+a+" "+b+" "+w+" "+m
942
"|n: "+num[j] + "|S^2: "+sSq[j]);
946
// Doesn't affect optimization
947
//NLL += 0.5*num[j]*Math.log(Math.PI);
949
NLL -= 0.5*(b+num[j]-1.0)*Math.log(1.0+num[j]*w);
952
if(Double.isNaN(NLL) && m_Debug){
953
System.err.println("???????????2: "+a+" "+b+" "+w+" "+m
955
"|n: "+num[j] + "|S^2: "+sSq[j]);
959
int halfNum = ((int)num[j])/2;
960
for(int z=1; z<=halfNum; z++)
961
NLL -= Math.log(0.5*b+0.5*num[j]-(double)z);
963
if(0.5*num[j] > halfNum) // num[j] is odd
964
NLL -= diffLnGamma(0.5*b);
966
if(Double.isNaN(NLL) && m_Debug){
967
System.err.println("???????????3: "+a+" "+b+" "+w+" "+m
969
"|n: "+num[j] + "|S^2: "+sSq[j]);
973
NLL -= 0.5*Math.log(a)*b;
974
if(Double.isNaN(NLL) && m_Debug){
975
System.err.println("???????????4:"+a+" "+b+" "+w+" "+m);
980
System.err.println("?????????????5: "+NLL);
981
if(Double.isNaN(NLL))
988
* Subclass should implement this procedure to evaluate gradient
989
* of the objective function
991
protected double[] evaluateGradient(double[] x){
992
double[] g = new double[x.length];
993
int numExs = num.length;
995
double a=x[0],b=x[1],w=x[2],m=x[3];
997
double da=0.0, db=0.0, dw=0.0, dm=0.0;
998
for(int j=0; j < numExs; j++){
1000
if(Double.isNaN(xBar[j])) continue; // All missing values
1002
double denorm = (1.0+num[j]*w)*(a+sSq[j]) +
1003
num[j]*(xBar[j]-m)*(xBar[j]-m);
1005
da += 0.5*(b+num[j])*(1.0+num[j]*w)/denorm-0.5*b/a;
1007
db += 0.5*Math.log(denorm)
1008
- 0.5*Math.log(1.0+num[j]*w)
1011
int halfNum = ((int)num[j])/2;
1012
for(int z=1; z<=halfNum; z++)
1013
db -= 1.0/(b+num[j]-2.0*(double)z);
1014
if(num[j]/2.0 > halfNum) // num[j] is odd
1015
db -= 0.5*diffFstDervLnGamma(0.5*b);
1017
dw += 0.5*(b+num[j])*(a+sSq[j])*num[j]/denorm -
1018
0.5*(b+num[j]-1.0)*num[j]/(1.0+num[j]*w);
1020
dm += num[j]*(b+num[j])*(m-xBar[j])/denorm;
1031
* Subclass should implement this procedure to evaluate second-order
1032
* gradient of the objective function
1034
protected double[] evaluateHessian(double[] x, int index){
1035
double[] h = new double[x.length];
1037
// # of exemplars, # of dimensions
1038
// which dimension and which variable for 'index'
1039
int numExs = num.length;
1041
// Take the 2nd-order derivative
1044
a=x[0];b=x[1];w=x[2];m=x[3];
1046
for(int j=0; j < numExs; j++){
1047
if(Double.isNaN(xBar[j])) continue; //All missing values
1048
double denorm = (1.0+num[j]*w)*(a+sSq[j]) +
1049
num[j]*(xBar[j]-m)*(xBar[j]-m);
1052
- 0.5*(b+num[j])*(1.0+num[j]*w)*(1.0+num[j]*w)
1055
h[1] += 0.5*(1.0+num[j]*w)/denorm - 0.5/a;
1057
h[2] += 0.5*num[j]*num[j]*(b+num[j])*
1058
(xBar[j]-m)*(xBar[j]-m)/(denorm*denorm);
1060
h[3] -= num[j]*(b+num[j])*(m-xBar[j])
1061
*(1.0+num[j]*w)/(denorm*denorm);
1066
a=x[0];b=x[1];w=x[2];m=x[3];
1068
for(int j=0; j < numExs; j++){
1069
if(Double.isNaN(xBar[j])) continue; //All missing values
1070
double denorm = (1.0+num[j]*w)*(a+sSq[j]) +
1071
num[j]*(xBar[j]-m)*(xBar[j]-m);
1073
h[0] += 0.5*(1.0+num[j]*w)/denorm - 0.5/a;
1075
int halfNum = ((int)num[j])/2;
1076
for(int z=1; z<=halfNum; z++)
1078
1.0/((b+num[j]-2.0*(double)z)*(b+num[j]-2.0*(double)z));
1079
if(num[j]/2.0 > halfNum) // num[j] is odd
1080
h[1] -= 0.25*diffSndDervLnGamma(0.5*b);
1082
h[2] += 0.5*(a+sSq[j])*num[j]/denorm -
1083
0.5*num[j]/(1.0+num[j]*w);
1085
h[3] += num[j]*(m-xBar[j])/denorm;
1090
a=x[0];b=x[1];w=x[2];m=x[3];
1092
for(int j=0; j < numExs; j++){
1093
if(Double.isNaN(xBar[j])) continue; //All missing values
1094
double denorm = (1.0+num[j]*w)*(a+sSq[j]) +
1095
num[j]*(xBar[j]-m)*(xBar[j]-m);
1097
h[0] += 0.5*num[j]*num[j]*(b+num[j])*
1098
(xBar[j]-m)*(xBar[j]-m)/(denorm*denorm);
1100
h[1] += 0.5*(a+sSq[j])*num[j]/denorm -
1101
0.5*num[j]/(1.0+num[j]*w);
1103
h[2] += 0.5*(b+num[j]-1.0)*num[j]*num[j]/
1104
((1.0+num[j]*w)*(1.0+num[j]*w)) -
1105
0.5*(b+num[j])*(a+sSq[j])*(a+sSq[j])*
1106
num[j]*num[j]/(denorm*denorm);
1108
h[3] -= num[j]*num[j]*(b+num[j])*
1109
(m-xBar[j])*(a+sSq[j])/(denorm*denorm);
1114
a=x[0];b=x[1];w=x[2];m=x[3];
1116
for(int j=0; j < numExs; j++){
1117
if(Double.isNaN(xBar[j])) continue; //All missing values
1118
double denorm = (1.0+num[j]*w)*(a+sSq[j]) +
1119
num[j]*(xBar[j]-m)*(xBar[j]-m);
1121
h[0] -= num[j]*(b+num[j])*(m-xBar[j])
1122
*(1.0+num[j]*w)/(denorm*denorm);
1124
h[1] += num[j]*(m-xBar[j])/denorm;
1126
h[2] -= num[j]*num[j]*(b+num[j])*
1127
(m-xBar[j])*(a+sSq[j])/(denorm*denorm);
1129
h[3] += num[j]*(b+num[j])*
1130
((1.0+num[j]*w)*(a+sSq[j])-
1131
num[j]*(m-xBar[j])*(m-xBar[j]))