Changeset 17742

Timestamp:

09/13/20 22:35:58 (4 years ago)

Author:

chaider

Message:

#3073 Added smart splitting method to interpreter

File:

• branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IntervalInterpreter.cs (modified) (14 diffs)

branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IntervalInterpreter.cs

@@ -26 +26 @@
 using System.Collections.ObjectModel;
 using System.Linq;
-using System.Runtime.Remoting.Contexts;
 using HEAL.Attic;
 using HeuristicLab.Common;
@@ -80 +79 @@
     private IntervalInterpreter(IntervalInterpreter original, Cloner cloner)
       : base(original, cloner) { }
-    
+
     public IntervalInterpreter()
       : base("IntervalInterpreter", "Interpreter for calculation of intervals of symbolic models.") {
       Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
         "A counter for the total number of solutions the interpreter has evaluated", new IntValue(0)));
-      Parameters.Add(new FixedValueParameter<IntValue>(MinSplittingWidthParameterName, "Minimum interval width until splitting is stopped", new IntValue(0)));
-      Parameters.Add(new FixedValueParameter<IntValue>(MaxSplittingDepthParameterName, "Maximum recursion depth of the splitting", new IntValue(5)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MinSplittingWidthParameterName,
+        "Minimum interval width until splitting is stopped", new IntValue(0)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaxSplittingDepthParameterName,
+        "Maximum recursion depth of the splitting", new IntValue(5)));
       Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName, "", new BoolValue(false)));
     }
-    
+
     public override IDeepCloneable Clone(Cloner cloner) {
       return new IntervalInterpreter(this, cloner);
@@ -108 +109 @@
     public Interval GetSymbolicExpressionTreeInterval(
       ISymbolicExpressionTree tree, IDataset dataset,
-      IEnumerable<int> rows = null) {
+      IEnumerable<int> rows = null, int splitDirection = 0) {
       var variableRanges = DatasetUtil.GetVariableRanges(dataset, rows);
       return GetSymbolicExpressionTreeInterval(tree, variableRanges);
@@ -116 +117 @@
       ISymbolicExpressionTree tree, IDataset dataset,
       out IDictionary<ISymbolicExpressionTreeNode, Interval>
-        nodeIntervals, IEnumerable<int> rows = null) {
+        nodeIntervals, IEnumerable<int> rows = null, int splitDirection = 0) {
       var variableRanges = DatasetUtil.GetVariableRanges(dataset, rows);
       return GetSymbolicExpressionTreeIntervals(tree, variableRanges, out nodeIntervals);
@@ -123 +124 @@
     public Interval GetSymbolicExpressionTreeInterval(
       ISymbolicExpressionTree tree,
-      IReadOnlyDictionary<string, Interval> variableRanges) {
+      IReadOnlyDictionary<string, Interval> variableRanges, int splitDirection = 0) {
       lock (syncRoot) {
         EvaluatedSolutions++;
@@ -149 +150 @@
       IReadOnlyDictionary<string, Interval> variableRanges,
       out IDictionary<ISymbolicExpressionTreeNode, Interval>
-        nodeIntervals) {
+        nodeIntervals, int splitDirection = 0) {
       lock (syncRoot) {
         EvaluatedSolutions++;
@@ -163 +164 @@
         var containsDependencyProblem = ContainsVariableMultipleTimes(tree);
 
-        if (variables.Count > 1 && containsDependencyProblem) {
+        if (containsDependencyProblem) {
           var currIndex = 0;
           var currDepth = 0;
-          IDictionary<string, Interval> writeableVariableRanges = variableRanges.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
-          outputInterval = EvaluateRecursive(instructions, intervals, writeableVariableRanges, variables, MinSplittingWidth, MaxSplittingDepth,
-            ref currIndex, ref currDepth, tree);
+          IDictionary<string, Interval> writeableVariableRanges =
+            variableRanges.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
+          //outputInterval = EvaluateRecursive(instructions, intervals, writeableVariableRanges, variables, MinSplittingWidth, MaxSplittingDepth,
+          //  ref currIndex, ref currDepth, tree);
+          outputInterval = EvaluateWithSplitting(instructions, intervals, writeableVariableRanges, splitDirection);
         } else {
           var instructionCount = 0;
@@ -202 +205 @@
 
       //Check if all variables used in the tree are present in the dataset
-      foreach (var variable in tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(n => n.VariableName).Distinct())
+      foreach (var variable in tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(n => n.VariableName)
+                                   .Distinct())
         if (!variableRanges.ContainsKey(variable))
           throw new InvalidOperationException($"No ranges for variable {variable} is present");
@@ -215 +219 @@
     }
 
-
+    public static Interval EvaluateWithSplitting(Instruction[] instructions,
+                                                 IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals,
+                                                 IDictionary<string, Interval> variableIntervals,
+                                                 int splitDirection = 0) {
+      if (splitDirection == 0) {
+        var savedIntervals = variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value);
+        var minimization = PerformSplitting(instructions, nodeIntervals, variableIntervals, -1);
+        var maximization = PerformSplitting(instructions, nodeIntervals, savedIntervals, 1);
+
+        return new Interval(minimization.LowerBound, maximization.UpperBound);
+      }
+
+      return PerformSplitting(instructions, nodeIntervals, variableIntervals, splitDirection);
+    }
+
+    private static Interval PerformSplitting(Instruction[] instructions,
+                                             IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals,
+                                             IDictionary<string, Interval> variableIntervals, int splitDirection) {
+      SortedList<Tuple<double, List<Interval>>, Interval> priorityList = null;
+      priorityList = splitDirection == -1 ? new SortedList<Tuple<double, List<Interval>>, Interval>(new BoxMinimizer()) : new SortedList<Tuple<double, List<Interval>>, Interval>(new BoxMaximizer());
+      var ic = 0;
+      //Calculate full box
+      IReadOnlyDictionary<string, Interval> readonlyRanges = variableIntervals.ToDictionary(k => k.Key, k => k.Value);
+      var fullbox = Evaluate(instructions, ref ic, nodeIntervals, readonlyRanges);
+      var box = variableIntervals.Keys.Select(k => variableIntervals[k]).ToList();
+      priorityList.Add(
+        splitDirection == -1
+          ? new Tuple<double, List<Interval>>(fullbox.LowerBound, box)
+          : new Tuple<double, List<Interval>>(fullbox.UpperBound, box), fullbox);
+
+      for (var depth = 0; depth < 200; ++depth) {
+        var firstBox = priorityList.First();
+        priorityList.RemoveAt(0);
+
+        var boxes = Split(firstBox.Key.Item2);
+
+        foreach (var b in boxes) {
+          var i = 0;
+          foreach (var k in readonlyRanges.Keys) {
+            variableIntervals[k] = b.ToList()[i];
+            ++i;
+          }
+
+          ic = 0;
+          var res = Evaluate(instructions, ref ic, nodeIntervals,
+            new ReadOnlyDictionary<string, Interval>(variableIntervals));
+          priorityList.Add(
+            splitDirection == -1
+              ? new Tuple<double, List<Interval>>(res.LowerBound, b.ToList())
+              : new Tuple<double, List<Interval>>(res.UpperBound, b.ToList()), res);
+        }
+      }
+
+      //Calculate final interval
+      var final = new Interval(0, 0);
+
+      return priorityList.Aggregate(final, (current, b) => current | b.Value);
+    }
+
+    private static IEnumerable<IEnumerable<Interval>> Split(List<Interval> box) {
+      var boxes = box.Select(region => region.Split()).Select(split => new List<Interval> {split.Item1, split.Item2})
+                     .ToList();
+
+      return boxes.CartesianProduct();
+    }
+
+    private class BoxMinimizer : IComparer<Tuple<double, List<Interval>>> {
+      public int Compare(Tuple<double, List<Interval>> x, Tuple<double, List<Interval>> y) {
+        var result = x.Item1.CompareTo(y.Item1);
+
+        if (result == 0) {
+          var sizeBox2 = y.Item2.Aggregate(1.0, (current, region) => current * region.Width);
+          var sizeBox1 = x.Item2.Aggregate(1.0, (current, region) => current * region.Width);
+
+          if (sizeBox2 < sizeBox1) return -1;
+
+          return 1;
+        }
+
+        return result;
+      }
+    }
+
+    private class BoxMaximizer : IComparer<Tuple<double, List<Interval>>> {
+      public int Compare(Tuple<double, List<Interval>> x, Tuple<double, List<Interval>> y) {
+        var result = y.Item1.CompareTo(x.Item1);
+
+        if (result == 0) {
+          var sizeBox2 = y.Item2.Aggregate(1.0, (current, region) => current * region.Width);
+          var sizeBox1 = x.Item2.Aggregate(1.0, (current, region) => current * region.Width);
+
+          if (sizeBox2 > sizeBox1) return -1;
+
+          return 1;
+        }
+
+        return result;
+      }
+    }
 
     public static Interval EvaluateRecursive(
@@ -225 +327 @@
       Interval evaluate() {
         var ic = 0;
-        IReadOnlyDictionary<string, Interval> readonlyRanges = new ReadOnlyDictionary<string, Interval>(variableIntervals);
+        IReadOnlyDictionary<string, Interval> readonlyRanges =
+          new ReadOnlyDictionary<string, Interval>(variableIntervals);
         return Evaluate(instructions, ref ic, nodeIntervals, readonlyRanges);
       }
@@ -249 +352 @@
       }
 
-      var t  = x.Split();
+      var t = x.Split();
       var xa = t.Item1;
       var xb = t.Item2;
-      var d  = currDepth;
-      currDepth            = d + 1;
+      var d = currDepth;
+      currDepth = d + 1;
       variableIntervals[v] = xa;
       var ya = recurse(ref currIndex, ref currDepth);
-      currDepth            = d + 1;
+      currDepth = d + 1;
       variableIntervals[v] = xb;
       var yb = recurse(ref currIndex, ref currDepth);
@@ -277 +380 @@
         case OpCodes.Variable: {
           var variableTreeNode = (VariableTreeNode) currentInstr.dynamicNode;
-          var weightInterval   = new Interval(variableTreeNode.Weight, variableTreeNode.Weight);
+          var weightInterval = new Interval(variableTreeNode.Weight, variableTreeNode.Weight);
           //var variableInterval = (Interval)currentInstr.data;
 
@@ -436 +539 @@
     private static bool MultipleTimes(ISymbolicExpressionTree tree, string variable) {
       var varlist = tree.IterateNodesPrefix().OfType<VariableTreeNode>().GroupBy(x => x.VariableName);
-      var group   = varlist.Select(x => x.Key == variable).Count();
+      var group = varlist.Select(x => x.Key == variable).Count();
 
       return group > 1;
@@ -443 +546 @@
     private static bool ContainsVariableMultipleTimes(ISymbolicExpressionTree tree) {
       var varlist = tree.IterateNodesPrefix().OfType<VariableTreeNode>().GroupBy(x => x.VariableName);
-      return varlist.Any(@group => @group.Count() > 1);
+      return varlist.Any(group => group.Count() > 1);
     }