Changeset 17768 for branches/3073_IA_constraint_splitting

Timestamp:

10/02/20 11:36:34 (4 years ago)

Author:

chaider

Message:

#3073

• Removed Region class and used IntervallCollection instead
• Changed Parser to work with IntervalColletions
• Moved CheckConstraint methods from Analyzer to IntervalUtil class
• Added CheckConstraint method to interface to check if an interval is in a given constraint
• Added possibility to stop splitting as soon as a constraint is fulfiled

Location:

branches/3073_IA_constraint_splitting

Files:

• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interfaces/IBoundsEstimator.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IABoundsEstimator.cs (modified) (15 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/IntervalUtil.cs (added)
• HeuristicLab.Problems.DataAnalysis/3.4/HeuristicLab.Problems.DataAnalysis-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Interval/IntervalConstraint.cs (modified) (5 diffs)
• HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Interval/IntervalConstraintsParser.cs (modified) (3 diffs)
• HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Interval/Region.cs (deleted)

branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -242 +242 @@
     <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs" />
     <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs" />
+    <Compile Include="IntervalUtil.cs" />
     <Compile Include="Selectors\DiversitySelector.cs" />
     <Compile Include="SymbolicDataAnalysisExpressionTreeAverageSimilarityCalculator.cs" />

branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interfaces/IBoundsEstimator.cs

@@ -16 +16 @@
       ISymbolicExpressionTree tree, IntervalCollection variableRanges);
 
+    double CheckConstraint(
+      ISymbolicExpressionTree tree, IntervalCollection variableRanges, IntervalConstraint constraint);
+
+    bool IsCompatible(ISymbolicExpressionTree tree);
+
     int EvaluatedSolutions { get; set; }
-  }
+    }
 }

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

@@ -3 +3 @@
 using System.Collections.ObjectModel;
 using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
 using HEAL.Attic;
 using HeuristicLab.Common;
@@ -15 +13 @@
   [StorableType("C8539434-6FB0-47D0-9F5A-2CAE5D8B8B4F")]
   [Item("IA Bounds Estimator", "Interpreter for calculation of intervals of symbolic models.")]
-  public sealed class IABoundsEstimator : ParameterizedNamedItem, IBoundsEstimator{
+  public sealed class IABoundsEstimator : ParameterizedNamedItem, IBoundsEstimator {
     #region Parameters
 
@@ -54 +52 @@
       set => SplittingWidthParameter.Value.Value = value;
     }
+
     #endregion
 
@@ -60 +59 @@
     [StorableConstructor]
     private IABoundsEstimator(StorableConstructorFlag _) : base(_) { }
-        
+
     private IABoundsEstimator(IABoundsEstimator original, Cloner cloner) : base(original, cloner) { }
 
-    public IABoundsEstimator() : base("IA Bounds Estimator", "Estimates the bounds of the model with interval arithmetic") {
-      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName, "A counter for the total number of solutions the estimator has evaluated.", new IntValue(0)));
-      Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName, "Defines whether interval splitting is activated or not.", new BoolValue(false)));
-      Parameters.Add(new FixedValueParameter<IntValue>(SplittingIterationsParameterName, "Defines the number of iterations of splitting.", new IntValue(200)));
-      Parameters.Add(new FixedValueParameter<DoubleValue>(SplittingWidthParameterName, "Width of interval, after the splitting should stop.", new DoubleValue(0.0)));
+    public IABoundsEstimator() : base("IA Bounds Estimator",
+      "Estimates the bounds of the model with interval arithmetic") {
+      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
+        "A counter for the total number of solutions the estimator has evaluated.", new IntValue(0)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName,
+        "Defines whether interval splitting is activated or not.", new BoolValue(false)));
+      Parameters.Add(new FixedValueParameter<IntValue>(SplittingIterationsParameterName,
+        "Defines the number of iterations of splitting.", new IntValue(200)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(SplittingWidthParameterName,
+        "Width of interval, after the splitting should stop.", new DoubleValue(0.0)));
     }
 
@@ -74 +78 @@
     }
 
-        #endregion
+    #endregion
 
     #region IStatefulItem Members
@@ -86 +90 @@
     public void ClearState() { }
 
-        #endregion
+    #endregion
 
     #region Evaluation
@@ -261 +265 @@
     }
 
-        #endregion
+    #endregion
 
     #region Helpers
 
-    private static IDictionary<string, Interval> GetOccurringVariableRanges(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
+    private static IDictionary<string, Interval> GetOccurringVariableRanges(
+      ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
       var variables = tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(v => v.VariableName).Distinct()
                           .ToList();
@@ -321 +326 @@
     public static Interval EvaluateWithSplitting(Instruction[] instructions,
                                                  IDictionary<string, Interval> variableIntervals,
-                                                 List<string> multipleOccurenceVariables, int splittingIterations, double splittingWidth, IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null) {
-      var savedIntervals = variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value);
-      var min = FindBound(instructions, variableIntervals, multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
+                                                 List<string> multipleOccurenceVariables, int splittingIterations,
+                                                 double splittingWidth,
+                                                 IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals =
+                                                   null) {
+      var min = FindBound(instructions, variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value),
+        multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
         minimization: true);
-      var max = FindBound(instructions, savedIntervals,  multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
+      var max = FindBound(instructions, variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value),
+        multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
         minimization: false);
 
@@ -333 +342 @@
     private static double FindBound(Instruction[] instructions,
                                     IDictionary<string, Interval> variableIntervals,
-                                    List<string> multipleOccurenceVariables, int splittingIterations, double splittingWidth, IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null, bool minimization = true) {
+                                    List<string> multipleOccurenceVariables, int splittingIterations,
+                                    double splittingWidth,
+                                    IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null,
+                                    bool minimization = true, bool stopAtLimit = false, double limit = 0) {
       SortedSet<BoxBound> prioQ = new SortedSet<BoxBound>();
-
       var ic = 0;
+      var stop = false;
       //Calculate full box
-      //IReadOnlyDictionary<string, Interval> readonlyRanges =
-      //  variableIntervals.ToDictionary(k => k.Key, k => k.Value);
-      var interval = Evaluate(instructions, ref ic, nodeIntervals, variableIntervals:variableIntervals);
+      var interval = Evaluate(instructions, ref ic, nodeIntervals, variableIntervals: variableIntervals);
       // the order of keys in a dictionary is guaranteed to be the same order as values in a dictionary
       // https://docs.microsoft.com/en-us/dotnet/api/system.collections.idictionary.keys?view=netcore-3.1#remarks
@@ -348 +358 @@
       if (minimization) {
         prioQ.Add(new BoxBound(box, interval.LowerBound));
+        if (stopAtLimit && interval.LowerBound >= limit) stop = true;
       } else {
         prioQ.Add(new BoxBound(box, -interval.UpperBound));
+        if (stopAtLimit && interval.UpperBound <= limit) stop = true;
       }
 
       var discardedBound = double.MaxValue;
       var runningBound = double.MaxValue;
-      for (var depth = 0; depth < splittingIterations && prioQ.Count > 0; ++depth) {
+      for (var depth = 0; depth < splittingIterations && prioQ.Count > 0 && !stop; ++depth) {
         var currentBound = prioQ.Min;
         prioQ.Remove(currentBound);
@@ -382 +394 @@
           var res = Evaluate(instructions, ref ic, nodeIntervals,
             new ReadOnlyDictionary<string, Interval>(variableIntervals));
-          //if (minimization) {
-          //  prioQ.Add(new BoxBound(newBox, res.LowerBound));
-          //} else {
-          //  prioQ.Add(new BoxBound(newBox, -res.UpperBound));
-          //}
+
           var boxBound = new BoxBound(newBox, minimization ? res.LowerBound : -res.UpperBound);
           prioQ.Add(boxBound);
@@ -394 +402 @@
         runningBound = innerBound;
 
+        if (minimization) {
+          if (stopAtLimit && innerBound >= limit)
+            stop = true;
+        } else {
+          if (stopAtLimit && innerBound <= limit)
+            stop = true;
+        }
       }
 
@@ -413 +428 @@
 
     private static IEnumerable<IEnumerable<Interval>> Split(List<Interval> box, double minWidth) {
-      List<Interval> toList(Tuple<Interval, Interval> t) => new List<Interval>{t.Item1, t.Item2};
+      List<Interval> toList(Tuple<Interval, Interval> t) => new List<Interval> {t.Item1, t.Item2};
       var boxes = box.Select(region => region.Width > minWidth ? toList(region.Split()) : new List<Interval> {region})
                      .ToList();
@@ -435 +450 @@
       } else {
         var vars = ContainsVariableMultipleTimes(tree, out var variables);
-        resultInterval = EvaluateWithSplitting(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth);
+        resultInterval = EvaluateWithSplitting(instructions, occuringVariableRanges, variables, SplittingIterations,
+          SplittingWidth);
       }
 
@@ -445 +461 @@
     }
 
-    public IDictionary<ISymbolicExpressionTreeNode, Interval> GetModelNodesBounds(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
+    public IDictionary<ISymbolicExpressionTreeNode, Interval> GetModelNodesBounds(
+      ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
       throw new NotImplementedException();
     }
 
-    
+    public double CheckConstraint(
+      ISymbolicExpressionTree tree, IntervalCollection variableRanges, IntervalConstraint constraint) {
+      var occuringVariableRanges = GetOccurringVariableRanges(tree, variableRanges);
+      var instructions = PrepareInterpreterState(tree, occuringVariableRanges);
+      if (!UseIntervalSplitting) {
+        var instructionCounter = 0;
+        var modelBound = Evaluate(instructions, ref instructionCounter, variableIntervals: occuringVariableRanges);
+        if (constraint.Interval.Contains(modelBound)) return 0.0;
+        return Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound) +
+               Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
+      }
+
+      if (double.IsNegativeInfinity(constraint.Interval.LowerBound) &&
+          double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
+        return 0.0;
+      }
+
+      ContainsVariableMultipleTimes(tree, out var variables);
+
+      var upperBound = 0.0;
+      var lowerBound = 0.0;
+      if (double.IsNegativeInfinity(constraint.Interval.LowerBound)) {
+        upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
+          minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
+
+        return upperBound <= constraint.Interval.UpperBound
+          ? 0.0
+          : Math.Abs(upperBound - constraint.Interval.UpperBound);
+      }
+
+      if (double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
+        lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
+          minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
+
+        return lowerBound <= constraint.Interval.LowerBound
+          ? 0.0
+          : Math.Abs(lowerBound - constraint.Interval.LowerBound);
+      }
+
+      upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
+        minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
+      lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
+        minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
+
+
+      var res = 0.0;
+
+      res += upperBound <= constraint.Interval.UpperBound ? 0.0 : Math.Abs(upperBound - constraint.Interval.UpperBound);
+      res += lowerBound <= constraint.Interval.LowerBound ? 0.0 : Math.Abs(lowerBound - constraint.Interval.LowerBound);
+
+      return res;
+    }
+
+
+    public bool IsCompatible(ISymbolicExpressionTree tree) {
+      var containsUnknownSymbols = (
+        from n in tree.Root.GetSubtree(0).IterateNodesPrefix()
+        where
+          !(n.Symbol is Variable) &&
+          !(n.Symbol is Constant) &&
+          !(n.Symbol is StartSymbol) &&
+          !(n.Symbol is Addition) &&
+          !(n.Symbol is Subtraction) &&
+          !(n.Symbol is Multiplication) &&
+          !(n.Symbol is Division) &&
+          !(n.Symbol is Sine) &&
+          !(n.Symbol is Cosine) &&
+          !(n.Symbol is Tangent) &&
+          !(n.Symbol is HyperbolicTangent) &&
+          !(n.Symbol is Logarithm) &&
+          !(n.Symbol is Exponential) &&
+          !(n.Symbol is Square) &&
+          !(n.Symbol is SquareRoot) &&
+          !(n.Symbol is Cube) &&
+          !(n.Symbol is CubeRoot) &&
+          !(n.Symbol is Absolute) &&
+          !(n.Symbol is AnalyticQuotient)
+        select n).Any();
+      return !containsUnknownSymbols;
+    }
   }
 }

branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis/3.4/HeuristicLab.Problems.DataAnalysis-3.4.csproj

@@ -192 +192 @@
     <Compile Include="Implementation\Interval\IntervalConstraint.cs" />
     <Compile Include="Implementation\Interval\IntervalConstraintsParser.cs" />
-    <Compile Include="Implementation\Interval\Region.cs" />
     <Compile Include="Implementation\Regression\ConfidenceBoundRegressionSolution.cs" />
     <Compile Include="Implementation\Regression\ConstantRegressionModel.cs" />

branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Interval/IntervalConstraint.cs

@@ -115 +115 @@
     }
 
-    [Storable] private IEnumerable<Region> regions;
-    public IEnumerable<Region> Regions {
+    [Storable] private IntervalCollection regions;
+    public IntervalCollection Regions {
       get => regions;
       set {
@@ -146 +146 @@
                               Interval interval, double weight, bool enabled)
       : this(expression, variable, target, numberOfDerivations,
-             interval, Enumerable.Empty<Region>(), weight, enabled) { }
+             interval, new IntervalCollection(), weight, enabled) { }
 
     public IntervalConstraint(string expression, string variable, string target, int numberOfDerivations,
-                              Interval interval, IEnumerable<Region> regions, double weight, bool enabled) {
+                              Interval interval, IntervalCollection regions, double weight, bool enabled) {
       this.regions = regions;
       this.weight = weight;
@@ -166 +166 @@
     private IntervalConstraint(IntervalConstraint original, Cloner cloner)
       : base(original, cloner) {
-      Regions = new List<Region>(original.Regions?.Select(r => cloner.Clone(r)) ?? Enumerable.Empty<Region>());
+      Regions = original.Regions;
       Expression = original.Expression;
       Variable = original.Variable;
@@ -207 +207 @@
                                    "]");
         if(Regions != null) {
-          foreach (var region in Regions)
-            expression += $", {region.VariableName}=({region.Interval.LowerBound} .. {region.Interval.UpperBound})";
+          foreach (var region in Regions.GetReadonlyDictionary())
+            expression += $", {region.Key}=({region.Value.LowerBound} .. {region.Value.UpperBound})";
         }
         
@@ -224 +224 @@
                                  GetDerivationString(numberOfDerivations));
       if (Regions != null) {
-        foreach (var region in Regions)
-          expression += $", {region.VariableName}=({region.Interval.LowerBound} .. {region.Interval.UpperBound})";
+        foreach (var region in Regions.GetReadonlyDictionary())
+          expression += $", {region.Key}=({region.Value.LowerBound} .. {region.Value.UpperBound})";
       }
       Expression = expression;

branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Interval/IntervalConstraintsParser.cs

@@ -93 +93 @@
             if (match.Groups[10].Success)
             {
-              IList<Region> regions = new List<Region>();
+              IntervalCollection regions = new IntervalCollection();
               // option variables found
               for(int idx = 0; idx < match.Groups[10].Captures.Count; ++idx)
               {
-                Region region = ParseRegion(
+                KeyValuePair<string, Interval> region = ParseRegion(
                   match.Groups[11].Captures[idx].Value,
                   match.Groups[13].Captures[idx].Value,
                   match.Groups[15].Captures[idx].Value);
-                if(!regions.Any(r => r.VariableName == region.VariableName))
-                  regions.Add(region);
+                if (regions.GetReadonlyDictionary().All(r => r.Key != region.Key))
+                  regions.AddInterval(region.Key, region.Value);
                 else
                   throw new ArgumentException("A constraint cannot contain multiple regions of the same variable.");
@@ -184 +184 @@
             if(match.Groups[17].Success)
             {
-              IList<Region> regions = new List<Region>();
+              IntervalCollection regions = new IntervalCollection();
               // option variables found
               for (int idx = 0; idx < match.Groups[17].Captures.Count; ++idx)
               {
-                Region region = ParseRegion(
+                KeyValuePair<string, Interval> region = ParseRegion(
                   match.Groups[18].Captures[idx].Value,
                   match.Groups[20].Captures[idx].Value,
                   match.Groups[22].Captures[idx].Value);
-                if (!regions.Any(r => r.VariableName == region.VariableName))
-                  regions.Add(region);
+                if (regions.GetReadonlyDictionary().All(r => r.Key != region.Key))
+                  regions.AddInterval(region.Key, region.Value);
                 else
                   throw new ArgumentException("A constraint cannot contain multiple regions of the same variable.");
@@ -217 +217 @@
     }
 
-    private static Region ParseRegion(string variable, string lb, string ub)
+    private static KeyValuePair<string, Interval> ParseRegion(string variable, string lb, string ub)
     {
       var regionLb = ParseIntervalBounds(lb);
       var regionUb = ParseIntervalBounds(ub);
-      return new Region(variable, new Interval(regionLb, regionUb));
+      return new KeyValuePair<string, Interval>(variable, new Interval(regionLb, regionUb));
+      //return new Region(variable, new Interval(regionLb, regionUb));
     }