edu.udo.cs.yale.operator.learner
Class BestRuleInduction

java.lang.Object
  edu.udo.cs.yale.operator.Operator
      edu.udo.cs.yale.operator.learner.AbstractLearner
          edu.udo.cs.yale.operator.learner.BestRuleInduction

All Implemented Interfaces:

ConfigurationListener, Learner

public class BestRuleInduction
extends AbstractLearner

This operator returns the best rule regarding WRAcc using exhaustive search. Features like the incorporation of other metrics and the search for more than a single rule are prepared. The search strategy is BFS, with save pruning whenever applicable. This operator can easily be extended to support other search strategies.

Version:

$Id: BestRuleInduction.java,v 1.6 2006/04/11 22:43:29 martin_scholz Exp $

Author:

Martin Scholz

Nested Class Summary

class

BestRuleInduction.RuleWithScoreUpperBound

Field Summary

protected ConjunctiveRuleModel	bestRule
private double	bestScore
private static java.lang.String	BINOMIAL
private static java.lang.String	DEPTH_BOUND
private double	globalN
private double	globalP
private static java.lang.String	MAX_CACHE
private java.util.Vector<BestRuleInduction.RuleWithScoreUpperBound>	openNodes
private java.util.Vector<ConjunctiveRuleModel>	prunedNodes
private static java.lang.String	REL_TO_PRED
private static java.lang.String	UTILITY_FUNCTION
private static java.lang.String[]	UTILITY_FUNCTION_LIST
private static java.lang.String	WRACC

Constructor Summary

BestRuleInduction(OperatorDescription description)

Method Summary

private void	addRulesToOpenNodes(java.util.Collection rules, double scoreUpperBound) Annotates the collection of ConjunctiveRuleModels with an optimistic score they may achieve in the best case and adds them to the collection of open nodes.
protected boolean	communicateToHighscore(ConjunctiveRuleModel rule, double[] counts) Adds a rule to the set of best rules if its score is high enough.
private void	expandNode(ConjunctiveRuleModel rule, ExampleSet exampleSet) Evaluates a single rule by computing its score, and the best possible score after refining this rule.
protected ConjunctiveRuleModel	getBestRule()
protected double[]	getCounts(ConjunctiveRuleModel rule, ExampleSet exampleSet)
protected double	getOptimisticScore(double[] counts) Computes the best possible score that might be achieved by refining the rule.
java.util.List<ParameterType>	getParameterTypes() Adds the parameters "number of iterations" and "model file".
protected double	getPruningScore()
protected double	getScore(double[] counts, boolean predictPositives) Computes the WRAcc or BINOMIAL TEST FUNCTION based on p, n, and the global values P and N stored in this object.
protected void	initHighscore()
boolean	isRefinementOfPrunedRule(ConjunctiveRuleModel rule)
Model	learn(ExampleSet exampleSet) Trains a model.
boolean	supportsCapability(LearnerCapability lc) Checks for Learner capabilities.

Methods inherited from class edu.udo.cs.yale.operator.learner.AbstractLearner

apply, checkLearnerCapabilities, getEstimatedPerformance, getInputClasses, getInputDescription, getOptimizationPerformance, getOutputClasses, getWeights, shouldCalculateWeights, shouldDeliverOptimizationPerformance, shouldEstimatePerformance

Methods inherited from class edu.udo.cs.yale.operator.Operator

addError, addValue, addWarning, apply, checkDeprecations, checkIO, checkProperties, clearErrorList, cloneOperator, createExperimentTree, createExperimentTree, createFromXML, createMarkedExperimentTree, delete, experimentFinished, experimentStarts, getAddOnlyAdditionalOutput, getApplyCount, getDeliveredOutputClasses, getDeprecationInfo, getDesiredInputClasses, getErrorList, getExperiment, getInnerOperatorsXML, getInput, getInput, getInput, getIOContainerForInApplyLoopBreakpoint, getName, getNumberOfSteps, getOperatorClassName, getOperatorDescription, getParameter, getParameterAsBoolean, getParameterAsColor, getParameterAsDouble, getParameterAsFile, getParameterAsInt, getParameterAsString, getParameterList, getParameters, getParameterType, getParent, getStartTime, getStatus, getUserDescription, getValue, getValues, getXML, hasBreakpoint, hasBreakpoint, hasInput, inApplyLoop, isEnabled, isParameterSet, logMessage, performAdditionalChecks, register, remove, rename, resume, setBreakpoint, setEnabled, setExperiment, setInput, setListParameter, setOperatorParameters, setParameter, setParameters, setParent, setUserDescription, toString, writeXML

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface edu.udo.cs.yale.operator.learner.Learner

getName

Field Detail

DEPTH_BOUND

private static final java.lang.String DEPTH_BOUND

See Also:

Constant Field Values

UTILITY_FUNCTION

private static final java.lang.String UTILITY_FUNCTION

See Also:

Constant Field Values

MAX_CACHE

private static final java.lang.String MAX_CACHE

See Also:

Constant Field Values

REL_TO_PRED

private static final java.lang.String REL_TO_PRED

See Also:

Constant Field Values

WRACC

private static final java.lang.String WRACC

See Also:

Constant Field Values

BINOMIAL

private static final java.lang.String BINOMIAL

See Also:

Constant Field Values

UTILITY_FUNCTION_LIST

private static final java.lang.String[] UTILITY_FUNCTION_LIST

globalP

private double globalP

globalN

private double globalN

bestRule

protected ConjunctiveRuleModel bestRule

bestScore

private double bestScore

openNodes

private final java.util.Vector<BestRuleInduction.RuleWithScoreUpperBound> openNodes

prunedNodes

private final java.util.Vector<ConjunctiveRuleModel> prunedNodes

Constructor Detail

BestRuleInduction

public BestRuleInduction(OperatorDescription description)

Method Detail

supportsCapability

public boolean supportsCapability(LearnerCapability lc)

Description copied from interface: Learner

Checks for Learner capabilities. Should return true if the given capability is supported.

initHighscore

protected void initHighscore()

communicateToHighscore

protected boolean communicateToHighscore(ConjunctiveRuleModel rule,
                                         double[] counts)
                                  throws UndefinedParameterError

Adds a rule to the set of best rules if its score is high enough. Currently just a single rule is stored. Additionally it is checked whether the rule is bad enough to be pruned.

Returns:

true iff the rule can be pruned

Throws:

UndefinedParameterError

getBestRule

protected ConjunctiveRuleModel getBestRule()

Returns:

the best rule found

getPruningScore

protected double getPruningScore()

Returns:

the lowest score of the stored best rules for pruning

learn

public Model learn(ExampleSet exampleSet)
            throws OperatorException

Description copied from interface: Learner

Trains a model. This method should be called by apply() and is implemented by subclasses.

Throws:

OperatorException

addRulesToOpenNodes

private void addRulesToOpenNodes(java.util.Collection rules,
                                 double scoreUpperBound)

Annotates the collection of ConjunctiveRuleModels with an optimistic score they may achieve in the best case and adds them to the collection of open nodes.

expandNode

private void expandNode(ConjunctiveRuleModel rule,
                        ExampleSet exampleSet)
                 throws OperatorException

Evaluates a single rule by computing its score, and the best possible score after refining this rule. If this cannot improve over the currently best rules, then the refinements are pruned. Otherwise all refinements plus optimistic estimates are added to the collection of open nodes. If the evaluated rule is good enough, then it is stored toghether with its score.

Throws:

OperatorException

isRefinementOfPrunedRule

public boolean isRefinementOfPrunedRule(ConjunctiveRuleModel rule)

Parameters:

rule - a ConjuctiveRuleModel for which it is checked whether a more general rule has already been pruned.

Returns:

true, if this rule is a refinement of a pruned rule. The rules are compared using the method ConjunctiveRuleModel.isRefinementOf(ConjunctiveRuleModel model)

getScore

protected double getScore(double[] counts,
                          boolean predictPositives)
                   throws UndefinedParameterError

Computes the WRAcc or BINOMIAL TEST FUNCTION based on p, n, and the global values P and N stored in this object. First two entries of counts are p and n, optionally estimates for p and n can be supplied as further parameters.

Throws:

UndefinedParameterError

getOptimisticScore

protected double getOptimisticScore(double[] counts)
                             throws UndefinedParameterError

Computes the best possible score that might be achieved by refining the rule. During learning the conclusion is normalized to "positive", so the better of the estimates of the better conclusion is returned.

Throws:

UndefinedParameterError

getCounts

protected double[] getCounts(ConjunctiveRuleModel rule,
                             ExampleSet exampleSet)
                      throws OperatorException

Parameters:

rule - the rule to evaluate

exampleSet - the exampleSet to get the counts for

Returns:

a double[2] object, first parameter is p, second is n. If rule discovery relative to a predicted label is activated, then a double[4] is returned, which contains the estimated positives and negatives in the covered part as fields 3 and 4.

Throws:

OperatorException

getParameterTypes

public java.util.List<ParameterType> getParameterTypes()

Adds the parameters "number of iterations" and "model file".

Overrides:

getParameterTypes in class Operator