source: branches/LearningClassifierSystems/HeuristicLab.Encodings.DecisionList/3.3/Evaluator/MDLEvaluator.cs @ 12009

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab 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 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab 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 HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Optimization.Operators.LCS;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Encodings.DecisionList {
  [Item("MDLEvaluator", "Description missing")]
  [StorableClass]
  public class MDLEvaluator : SingleSuccessorOperator, IDecisionListEvaluator, IDecisionListOperator, IMDLCalculatorBasedOperator, IIterationBasedOperator, IStochasticOperator {

    #region Parameter Properties
    public ILookupParameter<IRandom> RandomParameter {
      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    }
    public ILookupParameter<DecisionList> DecisionListParameter {
      get { return (ILookupParameter<DecisionList>)Parameters["DecisionList"]; }
    }
    public IValueLookupParameter<IntValue> SizePenaltyMinRulesParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["SizePenaltyMinRules"]; }
    }
    public ILookupParameter<DoubleValue> QualityParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    }
    public ILookupParameter<DoubleValue> LengthParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["Length"]; }
    }
    public IValueLookupParameter<IDecisionListClassificationProblemData> ProblemDataParameter {
      get { return (IValueLookupParameter<IDecisionListClassificationProblemData>)Parameters["ProblemData"]; }
    }

    public IValueLookupParameter<BoolValue> UseMDLParameter {
      get { return (IValueLookupParameter<BoolValue>)Parameters["UseMDL"]; }
    }
    public ILookupParameter<MDLCalculator> MDLCalculatorParameter {
      get { return (ILookupParameter<MDLCalculator>)Parameters["MDLCalculator"]; }
    }
    public ILookupParameter<IntValue> IterationsParameter {
      get { return (ILookupParameter<IntValue>)Parameters["Iterations"]; }
    }
    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
    }

    public IValueLookupParameter<IntValue> IterationRuleDeletionParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["IterationRuleDeletion"]; }
    }
    public IValueLookupParameter<IntValue> RuleDeletionMinRulesParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["RuleDeletionMinRules"]; }
    }

    public ILookupParameter<ItemList<ItemList<IntValue>>> StrataParameter {
      get { return (ILookupParameter<ItemList<ItemList<IntValue>>>)Parameters["Strata"]; }
    }
    public IValueLookupParameter<BoolValue> MaximizationParameter {
      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
    }
    #endregion

    public IRandom Random {
      get { return RandomParameter.ActualValue; }
    }

    [StorableConstructor]
    protected MDLEvaluator(bool deserializing) : base(deserializing) { }
    protected MDLEvaluator(MDLEvaluator original, Cloner cloner)
      : base(original, cloner) {
    }
    public MDLEvaluator()
      : base() {
      Parameters.Add(new LookupParameter<IRandom>("Random", "The random generator to use."));
      Parameters.Add(new LookupParameter<DecisionList>("DecisionList", ""));
      Parameters.Add(new ValueLookupParameter<IntValue>("SizePenaltyMinRules", ""));
      Parameters.Add(new LookupParameter<DoubleValue>("Quality", ""));
      Parameters.Add(new LookupParameter<DoubleValue>("Length", ""));
      Parameters.Add(new ValueLookupParameter<IDecisionListClassificationProblemData>("ProblemData", ""));
      Parameters.Add(new ValueLookupParameter<BoolValue>("UseMDL", "", new BoolValue(true)));
      Parameters.Add(new LookupParameter<MDLCalculator>("MDLCalculator", ""));
      Parameters.Add(new LookupParameter<IntValue>("Iterations", ""));
      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", ""));
      Parameters.Add(new ValueLookupParameter<IntValue>("IterationRuleDeletion", "", new IntValue(5)));
      Parameters.Add(new ValueLookupParameter<IntValue>("RuleDeletionMinRules", "", new IntValue(12)));
      Parameters.Add(new ValueLookupParameter<ItemList<ItemList<IntValue>>>("Strata", ""));
      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "", new BoolValue(false)));

      UseMDLParameter.Value.ValueChanged += UseMDLParameter_ValueChanged;
    }

    private void UseMDLParameter_ValueChanged(object sender, System.EventArgs e) {
      MaximizationParameter.Value.Value = !UseMDLParameter.Value.Value;
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new MDLEvaluator(this, cloner);
    }

    public override IOperation Apply() {
      var strata = StrataParameter.ActualValue;
      int iteration = IterationsParameter.ActualValue.Value;
      int numberOfStrata = strata.Count;
      var dl = DecisionListParameter.ActualValue;
      var problemData = ProblemDataParameter.ActualValue;
      bool lastIteration = iteration == MaximumIterationsParameter.ActualValue.Value - 1;
      IEnumerable<int> rows;
      if (lastIteration) {
        rows = from s in strata
               from row in s
               select row.Value;
      } else {
        rows = strata[iteration % numberOfStrata].Select(x => x.Value);
      }
      var input = problemData.FetchInput(rows);
      var actions = problemData.FetchAction(rows);
      ItemSet<Rule> aliveRules;
      double theoryLength;
      var estimated = dl.Evaluate(input, out aliveRules, out theoryLength);

      double penalty = 1;
      if (aliveRules.Count < SizePenaltyMinRulesParameter.ActualValue.Value) {
        penalty = (1 - 0.025 * (SizePenaltyMinRulesParameter.ActualValue.Value - aliveRules.Count));
        if (penalty <= 0) penalty = 0.01;
        penalty *= penalty;
      }

      double accuracy = DecisionListSolution.CalculateAccuracy(actions, estimated);
      if (UseMDLParameter.ActualValue.Value) {
        QualityParameter.ActualValue =
          new DoubleValue(MDLCalculatorParameter.ActualValue.CalculateFitness(theoryLength, accuracy) / penalty);
      } else {
        QualityParameter.ActualValue = new DoubleValue(accuracy * accuracy * penalty);
      }

      if (iteration >= IterationRuleDeletionParameter.ActualValue.Value) {
        if (lastIteration) {
          DoRuleDeletion(dl, aliveRules, 1);
        } else {
          DoRuleDeletion(dl, aliveRules, RuleDeletionMinRulesParameter.ActualValue.Value);
        }
      }

      LengthParameter.ActualValue = new DoubleValue(dl.Length * aliveRules.Count / dl.RuleSetSize);
      return base.Apply();
    }

    // default rule cannot be deleted, but it has to be considered in the rule set size
    private void DoRuleDeletion(DecisionList dl, IEnumerable<Rule> aliveRules, int minRules) {
      int ruleSetSize = dl.RuleSetSize;
      if (ruleSetSize <= minRules) { return; }

      var deadRules = dl.Rules.Except(aliveRules).ToList();
      int numberOfDeadRules = deadRules.Count();

      int keepRules = minRules - (ruleSetSize - numberOfDeadRules);

      if (keepRules > 0) {
        for (int i = 0; i < keepRules; i++) {
          int pos = Random.Next(deadRules.Count);
          deadRules.RemoveAt(pos);
        }
      }

      dl.RemoveRules(deadRules);
    }
  }
}