Changeset 4224

Timestamp:

08/16/10 10:02:12 (14 years ago)

Author:

gkronber

Message:

Added experimental anti-overfitting code to dynamic operator equalizer to prevent code growth when the current validation quality is below the best validation quality. #1142.

File:

• branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis/3.3/Operators/DynOpEqComparator.cs (modified) (7 diffs)

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

@@ -68 +68 @@
     public ILookupParameter<ItemList<IntValue>> TotalCountsParameter {
       get { return (ILookupParameter<ItemList<IntValue>>)Parameters["TotalCounts"]; }
+    }
+    public IValueLookupParameter<BoolValue> AntiOverfitParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["AntiOverfit"]; }
+    }
+    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)"]; }
     }
 
@@ -83 +92 @@
       Parameters.Add(new LookupParameter<ItemList<IntValue>>("AcceptedCounts"));
       Parameters.Add(new LookupParameter<ItemList<IntValue>>("TotalCounts"));
+      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)"));
     }
 
@@ -91 +103 @@
         int bin = GetBinIndexForSize(size);
         if (LeftSideParameter.ActualValue == null) {
+          // not yet evaluated
+          #region debugging
           ItemList<IntValue> totalCounts = TotalCountsParameter.ActualValue;
           while (bin >= totalCounts.Count) totalCounts.Add(new IntValue(0));
           totalCounts[bin].Value = totalCounts[bin].Value + 1;
-
-          if (!Exists(bin)) ResultParameter.ActualValue = new BoolValue(true);
-          else ResultParameter.ActualValue = new BoolValue(IsNotFull(bin));
+          #endregion
+          if (!Exists(bin)) {
+
+            if (AntiOverfitParameter.ActualValue.Value) {
+              // reject more complex solutions if the current validation quality is worse than the best so far
+              ResultParameter.ActualValue = new BoolValue(!IsOverfitting());
+            } else {
+              // new bin -> evaluate and check later
+              ResultParameter.ActualValue = new BoolValue(true);
+            }
+          } else {
+            // bin exists: 
+            // if bin is full -> reject
+            // otherwise -> evaluate and check success criterion
+            ResultParameter.ActualValue = new BoolValue(IsNotFull(bin));
+          }
         } else {
           double leftQuality = LeftSideParameter.ActualValue.Value;
-
-
           ResultParameter.ActualValue = new BoolValue(Accept(size, bin, leftQuality));
         }
@@ -107 +132 @@
     }
 
+    private bool IsOverfitting() {
+      bool maximization = MaximizationParameter.ActualValue.Value;
+      if (CurrentBestValidationQualityParameter.ActualValue != null && BestValidationQualityParameter.ActualValue != null) {
+        double currentValidationQuality = CurrentBestValidationQualityParameter.ActualValue.Value;
+        double bestValidationQuality = BestValidationQualityParameter.ActualValue.Value;
+        return maximization ? currentValidationQuality < bestValidationQuality : currentValidationQuality > bestValidationQuality;
+      } else 
+        return false;
+    }
+
     private int GetBinIndexForSize(int size) {
       return (int)Math.Floor((size - 3.0) / BinSizeParameter.ActualValue.Value);
@@ -114 +149 @@
       bool accept = false;
       if (Exists(binIndex)) {
-        if (IsNotFull(binIndex) ||
-          NewBestOfBin(solutionQuality, binIndex)) {
-          AddToBin(solutionQuality, binIndex);
+        //if (IsNotFull(binIndex) /*||
+          //NewBestOfBin(solutionQuality, binIndex)*/) {        
+        AddToBin(solutionQuality, binIndex);
           accept = true;
-        }
+        //}
       } else if (NewBestOfRun(solutionQuality)) {
         CreateNewBin(binIndex);
@@ -130 +165 @@
       ItemList<DoubleValue> acceptedBinQualities = AcceptedBinQualitiesParameter.ActualValue[binIndex];
       ItemList<IntValue> acceptedCounts = AcceptedCountsParameter.ActualValue;
-      if (acceptedBinQualities.Count == 0) {
-        acceptedBinQualities.Add(new DoubleValue(solutionQuality));
-        acceptedCounts[binIndex].Value = acceptedCounts[binIndex].Value + 1;
-      } else {
-        // insert at beginning if it is a new best or add at end
-        bool maximization = MaximizationParameter.ActualValue.Value;
-        if ((maximization && solutionQuality > acceptedBinQualities[0].Value) ||
-          (!maximization && solutionQuality < acceptedBinQualities[0].Value)) {
-          acceptedBinQualities.Insert(0, new DoubleValue(solutionQuality));
-        } else {
-          acceptedBinQualities.Add(new DoubleValue(solutionQuality));
-        }
-        acceptedCounts[binIndex].Value = acceptedCounts[binIndex].Value + 1;
-      }
+      acceptedBinQualities.Add(new DoubleValue(solutionQuality));
+      acceptedCounts[binIndex].Value = acceptedCounts[binIndex].Value + 1;
     }
 
@@ -165 +188 @@
     }
 
-    private bool NewBestOfBin(double solutionQuality, int binIndex) {
-      ItemList<ItemList<DoubleValue>> acceptedQualities = AcceptedBinQualitiesParameter.ActualValue;
-      if (acceptedQualities[binIndex].Count == 0) return true;
-      bool maximization = MaximizationParameter.ActualValue.Value;
-      IEnumerable<double> binQualities = acceptedQualities[binIndex].Select(x => x.Value);
-      // binQualities are always sorted so that the best is in bin 0
-      return maximization ? solutionQuality > binQualities.First() :
-        solutionQuality < binQualities.First();
-    }
+    //private bool NewBestOfBin(double solutionQuality, int binIndex) {
+    //  ItemList<ItemList<DoubleValue>> acceptedQualities = AcceptedBinQualitiesParameter.ActualValue;
+    //  if (acceptedQualities[binIndex].Count == 0) return true;
+    //  bool maximization = MaximizationParameter.ActualValue.Value;
+    //  IEnumerable<double> binQualities = acceptedQualities[binIndex].Select(x => x.Value);
+    //  // binQualities are always sorted so that the best is in bin 0
+    //  return maximization ? solutionQuality > binQualities.First() :
+    //    solutionQuality < binQualities.First();
+    //}
 
     private bool IsNotFull(int binIndex) {