Changeset 17742


Ignore:
Timestamp:
09/13/20 22:35:58 (10 days ago)
Author:
chaider
Message:

#3073 Added smart splitting method to interpreter

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IntervalInterpreter.cs

    r17650 r17742  
    2626using System.Collections.ObjectModel;
    2727using System.Linq;
    28 using System.Runtime.Remoting.Contexts;
    2928using HEAL.Attic;
    3029using HeuristicLab.Common;
     
    8079    private IntervalInterpreter(IntervalInterpreter original, Cloner cloner)
    8180      : base(original, cloner) { }
    82    
     81
    8382    public IntervalInterpreter()
    8483      : base("IntervalInterpreter", "Interpreter for calculation of intervals of symbolic models.") {
    8584      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
    8685        "A counter for the total number of solutions the interpreter has evaluated", new IntValue(0)));
    87       Parameters.Add(new FixedValueParameter<IntValue>(MinSplittingWidthParameterName, "Minimum interval width until splitting is stopped", new IntValue(0)));
    88       Parameters.Add(new FixedValueParameter<IntValue>(MaxSplittingDepthParameterName, "Maximum recursion depth of the splitting", new IntValue(5)));
     86      Parameters.Add(new FixedValueParameter<IntValue>(MinSplittingWidthParameterName,
     87        "Minimum interval width until splitting is stopped", new IntValue(0)));
     88      Parameters.Add(new FixedValueParameter<IntValue>(MaxSplittingDepthParameterName,
     89        "Maximum recursion depth of the splitting", new IntValue(5)));
    8990      Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName, "", new BoolValue(false)));
    9091    }
    91    
     92
    9293    public override IDeepCloneable Clone(Cloner cloner) {
    9394      return new IntervalInterpreter(this, cloner);
     
    108109    public Interval GetSymbolicExpressionTreeInterval(
    109110      ISymbolicExpressionTree tree, IDataset dataset,
    110       IEnumerable<int> rows = null) {
     111      IEnumerable<int> rows = null, int splitDirection = 0) {
    111112      var variableRanges = DatasetUtil.GetVariableRanges(dataset, rows);
    112113      return GetSymbolicExpressionTreeInterval(tree, variableRanges);
     
    116117      ISymbolicExpressionTree tree, IDataset dataset,
    117118      out IDictionary<ISymbolicExpressionTreeNode, Interval>
    118         nodeIntervals, IEnumerable<int> rows = null) {
     119        nodeIntervals, IEnumerable<int> rows = null, int splitDirection = 0) {
    119120      var variableRanges = DatasetUtil.GetVariableRanges(dataset, rows);
    120121      return GetSymbolicExpressionTreeIntervals(tree, variableRanges, out nodeIntervals);
     
    123124    public Interval GetSymbolicExpressionTreeInterval(
    124125      ISymbolicExpressionTree tree,
    125       IReadOnlyDictionary<string, Interval> variableRanges) {
     126      IReadOnlyDictionary<string, Interval> variableRanges, int splitDirection = 0) {
    126127      lock (syncRoot) {
    127128        EvaluatedSolutions++;
     
    149150      IReadOnlyDictionary<string, Interval> variableRanges,
    150151      out IDictionary<ISymbolicExpressionTreeNode, Interval>
    151         nodeIntervals) {
     152        nodeIntervals, int splitDirection = 0) {
    152153      lock (syncRoot) {
    153154        EvaluatedSolutions++;
     
    163164        var containsDependencyProblem = ContainsVariableMultipleTimes(tree);
    164165
    165         if (variables.Count > 1 && containsDependencyProblem) {
     166        if (containsDependencyProblem) {
    166167          var currIndex = 0;
    167168          var currDepth = 0;
    168           IDictionary<string, Interval> writeableVariableRanges = variableRanges.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
    169           outputInterval = EvaluateRecursive(instructions, intervals, writeableVariableRanges, variables, MinSplittingWidth, MaxSplittingDepth,
    170             ref currIndex, ref currDepth, tree);
     169          IDictionary<string, Interval> writeableVariableRanges =
     170            variableRanges.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
     171          //outputInterval = EvaluateRecursive(instructions, intervals, writeableVariableRanges, variables, MinSplittingWidth, MaxSplittingDepth,
     172          //  ref currIndex, ref currDepth, tree);
     173          outputInterval = EvaluateWithSplitting(instructions, intervals, writeableVariableRanges, splitDirection);
    171174        } else {
    172175          var instructionCount = 0;
     
    202205
    203206      //Check if all variables used in the tree are present in the dataset
    204       foreach (var variable in tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(n => n.VariableName).Distinct())
     207      foreach (var variable in tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(n => n.VariableName)
     208                                   .Distinct())
    205209        if (!variableRanges.ContainsKey(variable))
    206210          throw new InvalidOperationException($"No ranges for variable {variable} is present");
     
    215219    }
    216220
    217 
     221    public static Interval EvaluateWithSplitting(Instruction[] instructions,
     222                                                 IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals,
     223                                                 IDictionary<string, Interval> variableIntervals,
     224                                                 int splitDirection = 0) {
     225      if (splitDirection == 0) {
     226        var savedIntervals = variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value);
     227        var minimization = PerformSplitting(instructions, nodeIntervals, variableIntervals, -1);
     228        var maximization = PerformSplitting(instructions, nodeIntervals, savedIntervals, 1);
     229
     230        return new Interval(minimization.LowerBound, maximization.UpperBound);
     231      }
     232
     233      return PerformSplitting(instructions, nodeIntervals, variableIntervals, splitDirection);
     234    }
     235
     236    private static Interval PerformSplitting(Instruction[] instructions,
     237                                             IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals,
     238                                             IDictionary<string, Interval> variableIntervals, int splitDirection) {
     239      SortedList<Tuple<double, List<Interval>>, Interval> priorityList = null;
     240      priorityList = splitDirection == -1 ? new SortedList<Tuple<double, List<Interval>>, Interval>(new BoxMinimizer()) : new SortedList<Tuple<double, List<Interval>>, Interval>(new BoxMaximizer());
     241      var ic = 0;
     242      //Calculate full box
     243      IReadOnlyDictionary<string, Interval> readonlyRanges = variableIntervals.ToDictionary(k => k.Key, k => k.Value);
     244      var fullbox = Evaluate(instructions, ref ic, nodeIntervals, readonlyRanges);
     245      var box = variableIntervals.Keys.Select(k => variableIntervals[k]).ToList();
     246      priorityList.Add(
     247        splitDirection == -1
     248          ? new Tuple<double, List<Interval>>(fullbox.LowerBound, box)
     249          : new Tuple<double, List<Interval>>(fullbox.UpperBound, box), fullbox);
     250
     251      for (var depth = 0; depth < 200; ++depth) {
     252        var firstBox = priorityList.First();
     253        priorityList.RemoveAt(0);
     254
     255        var boxes = Split(firstBox.Key.Item2);
     256
     257        foreach (var b in boxes) {
     258          var i = 0;
     259          foreach (var k in readonlyRanges.Keys) {
     260            variableIntervals[k] = b.ToList()[i];
     261            ++i;
     262          }
     263
     264          ic = 0;
     265          var res = Evaluate(instructions, ref ic, nodeIntervals,
     266            new ReadOnlyDictionary<string, Interval>(variableIntervals));
     267          priorityList.Add(
     268            splitDirection == -1
     269              ? new Tuple<double, List<Interval>>(res.LowerBound, b.ToList())
     270              : new Tuple<double, List<Interval>>(res.UpperBound, b.ToList()), res);
     271        }
     272      }
     273
     274      //Calculate final interval
     275      var final = new Interval(0, 0);
     276
     277      return priorityList.Aggregate(final, (current, b) => current | b.Value);
     278    }
     279
     280    private static IEnumerable<IEnumerable<Interval>> Split(List<Interval> box) {
     281      var boxes = box.Select(region => region.Split()).Select(split => new List<Interval> {split.Item1, split.Item2})
     282                     .ToList();
     283
     284      return boxes.CartesianProduct();
     285    }
     286
     287    private class BoxMinimizer : IComparer<Tuple<double, List<Interval>>> {
     288      public int Compare(Tuple<double, List<Interval>> x, Tuple<double, List<Interval>> y) {
     289        var result = x.Item1.CompareTo(y.Item1);
     290
     291        if (result == 0) {
     292          var sizeBox2 = y.Item2.Aggregate(1.0, (current, region) => current * region.Width);
     293          var sizeBox1 = x.Item2.Aggregate(1.0, (current, region) => current * region.Width);
     294
     295          if (sizeBox2 < sizeBox1) return -1;
     296
     297          return 1;
     298        }
     299
     300        return result;
     301      }
     302    }
     303
     304    private class BoxMaximizer : IComparer<Tuple<double, List<Interval>>> {
     305      public int Compare(Tuple<double, List<Interval>> x, Tuple<double, List<Interval>> y) {
     306        var result = y.Item1.CompareTo(x.Item1);
     307
     308        if (result == 0) {
     309          var sizeBox2 = y.Item2.Aggregate(1.0, (current, region) => current * region.Width);
     310          var sizeBox1 = x.Item2.Aggregate(1.0, (current, region) => current * region.Width);
     311
     312          if (sizeBox2 > sizeBox1) return -1;
     313
     314          return 1;
     315        }
     316
     317        return result;
     318      }
     319    }
    218320
    219321    public static Interval EvaluateRecursive(
     
    225327      Interval evaluate() {
    226328        var ic = 0;
    227         IReadOnlyDictionary<string, Interval> readonlyRanges = new ReadOnlyDictionary<string, Interval>(variableIntervals);
     329        IReadOnlyDictionary<string, Interval> readonlyRanges =
     330          new ReadOnlyDictionary<string, Interval>(variableIntervals);
    228331        return Evaluate(instructions, ref ic, nodeIntervals, readonlyRanges);
    229332      }
     
    249352      }
    250353
    251       var t  = x.Split();
     354      var t = x.Split();
    252355      var xa = t.Item1;
    253356      var xb = t.Item2;
    254       var d  = currDepth;
    255       currDepth            = d + 1;
     357      var d = currDepth;
     358      currDepth = d + 1;
    256359      variableIntervals[v] = xa;
    257360      var ya = recurse(ref currIndex, ref currDepth);
    258       currDepth            = d + 1;
     361      currDepth = d + 1;
    259362      variableIntervals[v] = xb;
    260363      var yb = recurse(ref currIndex, ref currDepth);
     
    277380        case OpCodes.Variable: {
    278381          var variableTreeNode = (VariableTreeNode) currentInstr.dynamicNode;
    279           var weightInterval   = new Interval(variableTreeNode.Weight, variableTreeNode.Weight);
     382          var weightInterval = new Interval(variableTreeNode.Weight, variableTreeNode.Weight);
    280383          //var variableInterval = (Interval)currentInstr.data;
    281384
     
    436539    private static bool MultipleTimes(ISymbolicExpressionTree tree, string variable) {
    437540      var varlist = tree.IterateNodesPrefix().OfType<VariableTreeNode>().GroupBy(x => x.VariableName);
    438       var group   = varlist.Select(x => x.Key == variable).Count();
     541      var group = varlist.Select(x => x.Key == variable).Count();
    439542
    440543      return group > 1;
     
    443546    private static bool ContainsVariableMultipleTimes(ISymbolicExpressionTree tree) {
    444547      var varlist = tree.IterateNodesPrefix().OfType<VariableTreeNode>().GroupBy(x => x.VariableName);
    445       return varlist.Any(@group => @group.Count() > 1);
     548      return varlist.Any(group => group.Count() > 1);
    446549    }
    447550
Note: See TracChangeset for help on using the changeset viewer.