Changeset 4255 for branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis

Timestamp:

08/18/10 19:46:02 (14 years ago)

Author:

gkronber

Message:

Added complexity reduction scheme based on validation performance for CPP. #1142

Location:

branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis/3.3

Files:

• HeuristicLab.Problems.DataAnalysis-3.3.csproj (modified) (1 diff)
• Operators/CovariantParsimonyPressure.cs (modified) (5 diffs)

branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis/3.3/HeuristicLab.Problems.DataAnalysis-3.3.csproj

@@ -182 +182 @@
   </ItemGroup>
   <ItemGroup>
+    <ProjectReference Include="..\..\HeuristicLab.Analysis\3.3\HeuristicLab.Analysis-3.3.csproj">
+      <Project>{887425B4-4348-49ED-A457-B7D2C26DDBF9}</Project>
+      <Name>HeuristicLab.Analysis-3.3</Name>
+    </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Collections\3.3\HeuristicLab.Collections-3.3.csproj">
       <Project>{958B43BC-CC5C-4FA2-8628-2B3B01D890B6}</Project>

branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis/3.3/Operators/CovariantParsimonyPressure.cs

@@ -32 +32 @@
 using System.Collections.Generic;
 using HeuristicLab.Problems.DataAnalysis.Evaluators;
+using HeuristicLab.Analysis;
 
 namespace HeuristicLab.Problems.DataAnalysis.Operators {
@@ -43 +44 @@
       get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
     }
+    public IScopeTreeLookupParameter<DoubleValue> AdjustedQualityParameter {
+      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["AdjustedQuality"]; }
+    }
+
     public ILookupParameter<BoolValue> MaximizationParameter {
       get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
@@ -49 +54 @@
       get { return (IValueLookupParameter<DoubleValue>)Parameters["K"]; }
     }
-
+    public ILookupParameter<IntValue> GenerationsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["Generations"]; }
+    }
+    public IValueLookupParameter<IntValue> FirstGenerationParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["FirstGenerationParameter"]; }
+    }
+    public IValueLookupParameter<BoolValue> AntiOverfitParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["AntiOverfit"]; }
+    }
+    public ILookupParameter<DataTable> ValidationQualityParameter {
+      get { return (ILookupParameter<DataTable>)Parameters["Validation Quality"]; }
+    }
+    public ILookupParameter<DoubleValue> CurrentBestValidationQualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["Current best validation quality"]; }
+    }
+    public ILookupParameter<DoubleValue> BestValidationQualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["Best solution quality (validation)"]; }
+    }
+    public ILookupParameter<DoubleValue> LengthCorrelationParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["Correlation(Length, AdjustedFitness)"]; }
+    }
+    public ILookupParameter<DoubleValue> FitnessCorrelationParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["Correlation(Fitness, AdjustedFitness)"]; }
+    }
+    public IValueLookupParameter<IntValue> GenerationSpanParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["GenerationSpan"]; }
+    }
+    public IValueLookupParameter<PercentValue> OverfittingLimitParameter {
+      get { return (IValueLookupParameter<PercentValue>)Parameters["OverfittingLimit"]; }
+    }
+    public IValueLookupParameter<PercentValue> ComplexityAdaptionParameter {
+      get { return (IValueLookupParameter<PercentValue>)Parameters["ComplexityAdaption"]; }
+    }
+    public ILookupParameter<DataTable> QualitiesParameter {
+      get { return (ILookupParameter<DataTable>)Parameters["Qualities"]; }
+    }
 
     public CovariantParsimonyPressure(bool deserializing) : base(deserializing) { }
@@ -56 +96 @@
       Parameters.Add(new ScopeTreeLookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree"));
       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality"));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("AdjustedQuality"));
       Parameters.Add(new LookupParameter<BoolValue>("Maximization"));
       Parameters.Add(new ValueLookupParameter<DoubleValue>("K", new DoubleValue(1.0)));
+      Parameters.Add(new LookupParameter<IntValue>("Generations"));
+      Parameters.Add(new ValueLookupParameter<IntValue>("FirstGenerationParameter", new IntValue(5)));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("AntiOverfit", new BoolValue(false)));
+      //Parameters.Add(new LookupParameter<DoubleValue>("Current best validation quality"));
+      //Parameters.Add(new LookupParameter<DoubleValue>("Best solution quality (validation)"));
+      Parameters.Add(new LookupParameter<DataTable>("Validation Quality"));
+      Parameters.Add(new LookupParameter<DataTable>("Qualities"));
+      Parameters.Add(new ValueLookupParameter<IntValue>("GenerationSpan", new IntValue(5)));
+      Parameters.Add(new ValueLookupParameter<PercentValue>("OverfittingLimit", new PercentValue(5)));
+      Parameters.Add(new ValueLookupParameter<PercentValue>("ComplexityAdaption", new PercentValue(-5)));
+      Parameters.Add(new LookupParameter<DoubleValue>("Correlation(Length, AdjustedFitness)"));
+      Parameters.Add(new LookupParameter<DoubleValue>("Correlation(Fitness, AdjustedFitness)"));
     }
 
@@ -66 +119 @@
       if (!Parameters.ContainsKey("K"))
         Parameters.Add(new ValueLookupParameter<DoubleValue>("K", new DoubleValue(1.0)));
+      if (!Parameters.ContainsKey("AdjustedQuality")) {
+        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("AdjustedQuality"));
+      }
+      if (!Parameters.ContainsKey("Generations")) {
+        Parameters.Add(new LookupParameter<IntValue>("Generations"));
+      }
+      if (!Parameters.ContainsKey("FirstGenerationParameter")) {
+        Parameters.Add(new ValueLookupParameter<IntValue>("FirstGenerationParameter", new IntValue(5)));
+      }
+      if (!Parameters.ContainsKey("AntiOverfit")) {
+        Parameters.Add(new ValueLookupParameter<BoolValue>("AntiOverfit", new BoolValue(false)));
+      }
+      //if (!Parameters.ContainsKey("Current best validation quality")) {
+      //  Parameters.Add(new LookupParameter<DoubleValue>("Current best validation quality"));
+      //}
+      //if (!Parameters.ContainsKey("Best solution quality (validation)")) {
+      //  Parameters.Add(new LookupParameter<DoubleValue>("Best solution quality (validation)"));
+      //}
+      if (!Parameters.ContainsKey("Correlation(Length, AdjustedFitness)")) {
+        Parameters.Add(new LookupParameter<DoubleValue>("Correlation(Length, AdjustedFitness)"));
+      }
+      if (!Parameters.ContainsKey("Correlation(Fitness, AdjustedFitness)")) {
+        Parameters.Add(new LookupParameter<DoubleValue>("Correlation(Fitness, AdjustedFitness)"));
+      }
+      if (!Parameters.ContainsKey("Validation Quality")) {
+        Parameters.Add(new LookupParameter<DataTable>("Validation Quality"));
+      }
+      if (!Parameters.ContainsKey("Qualities")) {
+        Parameters.Add(new LookupParameter<DataTable>("Qualities"));
+      }
+      if (!Parameters.ContainsKey("GenerationSpan")) {
+        Parameters.Add(new ValueLookupParameter<IntValue>("GenerationSpan", new IntValue(5)));
+      }
+      if (!Parameters.ContainsKey("OverfittingLimit")) {
+        Parameters.Add(new ValueLookupParameter<PercentValue>("OverfittingLimit", new PercentValue(5)));
+      }
+      if (!Parameters.ContainsKey("ComplexityAdaption")) {
+        Parameters.Add(new ValueLookupParameter<PercentValue>("ComplexityAdaption", new PercentValue(-5)));
+      }
     }
 
     public override IOperation Apply() {
-      var trees = SymbolicExpressionTreeParameter.ActualValue;
-      var qualities = QualityParameter.ActualValue;
-      var lengths = from tree in trees
-                    select tree.Size;
-      double k = KParameter.ActualValue.Value;
-
-      // calculate cov(f, l) and cov(l, l^k)
-      OnlineCovarianceEvaluator lengthFitnessCovEvaluator = new OnlineCovarianceEvaluator();
-      OnlineCovarianceEvaluator lengthAdjLengthCovEvaluator = new OnlineCovarianceEvaluator();
-      var lengthEnumerator = lengths.GetEnumerator();
-      var qualityEnumerator = qualities.GetEnumerator();
-      while (lengthEnumerator.MoveNext() & qualityEnumerator.MoveNext()) {
-        double fitness = qualityEnumerator.Current.Value;
-        if (!MaximizationParameter.ActualValue.Value) {
-          // use f = 1 / (1 + quality) for minimization problems
-          fitness = 1.0 / (1.0 + fitness);
+      ItemArray<SymbolicExpressionTree> trees = SymbolicExpressionTreeParameter.ActualValue;
+      ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
+      // always apply Parsimony pressure if anti-overfit is false
+      // otherwise appliy PP only when we are currently overfitting
+      if (GenerationsParameter.ActualValue != null && GenerationsParameter.ActualValue.Value >= FirstGenerationParameter.ActualValue.Value &&
+         (AntiOverfitParameter.ActualValue.Value == false || IsOverfitting())) {
+        var lengths = from tree in trees
+                      select tree.Size;
+        double k = KParameter.ActualValue.Value;
+
+        // calculate cov(f, l) and cov(l, l^k)
+        OnlineCovarianceEvaluator lengthFitnessCovEvaluator = new OnlineCovarianceEvaluator();
+        OnlineCovarianceEvaluator lengthAdjLengthCovEvaluator = new OnlineCovarianceEvaluator();
+        OnlineMeanAndVarianceCalculator lengthMeanCalculator = new OnlineMeanAndVarianceCalculator();
+        OnlineMeanAndVarianceCalculator fitnessMeanCalculator = new OnlineMeanAndVarianceCalculator();
+        OnlineMeanAndVarianceCalculator adjLengthMeanCalculator = new OnlineMeanAndVarianceCalculator();
+        var lengthEnumerator = lengths.GetEnumerator();
+        var qualityEnumerator = qualities.GetEnumerator();
+        while (lengthEnumerator.MoveNext() & qualityEnumerator.MoveNext()) {
+          double fitness = qualityEnumerator.Current.Value;
+          if (!MaximizationParameter.ActualValue.Value) {
+            // use f = 1 / (1 + quality) for minimization problems
+            fitness = 1.0 / (1.0 + fitness);
+          }
+          lengthFitnessCovEvaluator.Add(lengthEnumerator.Current, fitness);
+          lengthAdjLengthCovEvaluator.Add(lengthEnumerator.Current, Math.Pow(lengthEnumerator.Current, k));
+          lengthMeanCalculator.Add(lengthEnumerator.Current);
+          fitnessMeanCalculator.Add(fitness);
+          adjLengthMeanCalculator.Add(Math.Pow(lengthEnumerator.Current, k));
         }
-        lengthFitnessCovEvaluator.Add(lengthEnumerator.Current, fitness);
-        lengthAdjLengthCovEvaluator.Add(lengthEnumerator.Current, Math.Pow(lengthEnumerator.Current, k));
-      }
-
-      // c = cov(l, f) / cov(l, l^k)
-      double c = lengthFitnessCovEvaluator.Covariance / lengthAdjLengthCovEvaluator.Covariance;
-
-      // adjust fitness
+
+        double sizeAdaption = lengthMeanCalculator.Mean * ComplexityAdaptionParameter.ActualValue.Value;
+        if (sizeAdaption < 0) sizeAdaption = Math.Floor(sizeAdaption);
+        else sizeAdaption = Math.Ceiling(sizeAdaption);
+        double g = lengthMeanCalculator.Mean + sizeAdaption;
+
+        //            cov(l, f) - (g(t+1) - mu(t)) avgF
+        // c(t) =  --------------------------------------------
+        //           cov(l, l^k) - (g(t+1) - mu(t)) E[l^k]
+        double c = lengthFitnessCovEvaluator.Covariance - (g - lengthMeanCalculator.Mean) * fitnessMeanCalculator.Mean;
+        c /= lengthAdjLengthCovEvaluator.Covariance - (g - lengthMeanCalculator.Mean) * adjLengthMeanCalculator.Mean;
+
+        // adjust fitness
+        bool maximization = MaximizationParameter.ActualValue.Value;
+
+        lengthEnumerator = lengths.GetEnumerator();
+        qualityEnumerator = qualities.GetEnumerator();
+        int i = 0;
+        ItemArray<DoubleValue> adjQualities = new ItemArray<DoubleValue>(qualities.Length);
+
+        while (lengthEnumerator.MoveNext() & qualityEnumerator.MoveNext()) {
+          adjQualities[i++] = new DoubleValue(qualityEnumerator.Current.Value - c * Math.Pow(lengthEnumerator.Current, k));
+        }
+        AdjustedQualityParameter.ActualValue = adjQualities;
+        double[] lengthArr = lengths.Select(x => (double)x).ToArray<double>();
+
+        double[] adjFitess = (from f in AdjustedQualityParameter.ActualValue
+                              select f.Value).ToArray<double>();
+        double[] fitnessArr = (from f in QualityParameter.ActualValue
+                               let normFit = maximization ? f.Value : 1.0 / (1.0 + f.Value)
+                               select normFit).ToArray<double>();
+
+        LengthCorrelationParameter.ActualValue = new DoubleValue(alglib.correlation.spearmanrankcorrelation(lengthArr, adjFitess, lengthArr.Length));
+        FitnessCorrelationParameter.ActualValue = new DoubleValue(alglib.correlation.spearmanrankcorrelation(fitnessArr, adjFitess, lengthArr.Length));
+
+      } else {
+        // adjusted fitness is equal to fitness
+        AdjustedQualityParameter.ActualValue = (ItemArray<DoubleValue>)QualityParameter.ActualValue.Clone();
+        FitnessCorrelationParameter.ActualValue = new DoubleValue(1.0);
+
+        double[] lengths = (from tree in trees
+                            select (double)tree.Size).ToArray<double>();
+
+        double[] fitess = (from f in AdjustedQualityParameter.ActualValue
+                           select f.Value).ToArray<double>();
+
+        LengthCorrelationParameter.ActualValue = new DoubleValue(alglib.correlation.spearmanrankcorrelation(lengths, fitess, lengths.Length));
+      }
+      return base.Apply();
+    }
+
+    private bool IsOverfitting() {
       bool maximization = MaximizationParameter.ActualValue.Value;
-
-      lengthEnumerator = lengths.GetEnumerator();
-      qualityEnumerator = qualities.GetEnumerator();
-      while (lengthEnumerator.MoveNext() & qualityEnumerator.MoveNext()) {
-        qualityEnumerator.Current.Value = qualityEnumerator.Current.Value - c * Math.Pow(lengthEnumerator.Current, k);
-      }
-
-      return base.Apply();
+      DataTable trainingQualities = QualitiesParameter.ActualValue;
+      DataTable validationQualities = ValidationQualityParameter.ActualValue;
+      int genSpan = GenerationSpanParameter.ActualValue.Value;
+      if (validationQualities == null || trainingQualities == null) return false;
+      if (validationQualities.Rows["Best solution quality (validation)"].Values.Count < genSpan) return false;
+
+      IEnumerable<double> bestTrainingQualities = trainingQualities.Rows["CurrentBestQuality"].Values;
+      IEnumerable<double> bestValidationQualities = validationQualities.Rows["Current best validation quality"].Values;
+
+      double trainingAvg = bestTrainingQualities.Reverse().Take(genSpan).Average();
+      double validationAvg = bestValidationQualities.Reverse().Take(genSpan).Average();
+
+      double maxPercentDiff = OverfittingLimitParameter.ActualValue.Value;
+
+      double percentDiff = maximization ? trainingAvg / validationAvg - 1 : validationAvg / trainingAvg - 1;
+      return percentDiff > maxPercentDiff;
     }
   }