source: branches/2971_named_intervals/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/InteractiveSymbolicDataAnalysisSolutionSimplifierView.cs @ 17510

Last change on this file since 17510 was 17510, checked in by chaider, 3 months ago

#2971

  • Changed constraint violation table to ResultParameter
  • Changed symbol check to include DerivativeCalculator symbols
  • Moved SymbolicRegressionConstraintAnalyzer to plugins root
  • Added Power and Root to IntervalInterpreter
File size: 16.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Drawing;
25using System.Linq;
26using System.Threading;
27using System.Threading.Tasks;
28using System.Windows.Forms;
29using HeuristicLab.Common;
30using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
31using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
32using HeuristicLab.MainForm;
33using HeuristicLab.MainForm.WindowsForms;
34
35namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Views {
36  public abstract partial class InteractiveSymbolicDataAnalysisSolutionSimplifierView : AsynchronousContentView {
37    private readonly Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> foldedNodes = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>();
38    private readonly Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> changedNodes = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>();
39    private readonly Dictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = new Dictionary<ISymbolicExpressionTreeNode, Interval>();
40    private readonly Dictionary<ISymbolicExpressionTreeNode, double> nodeImpacts = new Dictionary<ISymbolicExpressionTreeNode, double>();
41
42    private readonly ISymbolicDataAnalysisSolutionImpactValuesCalculator impactCalculator;
43
44    private readonly Progress progress = new Progress();
45    private CancellationTokenSource cancellationTokenSource;
46
47    private enum TreeState { Valid, Invalid }
48    private TreeState treeState;
49
50    protected InteractiveSymbolicDataAnalysisSolutionSimplifierView(ISymbolicDataAnalysisSolutionImpactValuesCalculator impactCalculator) {
51      InitializeComponent();
52      this.Caption = "Interactive Solution Simplifier";
53      this.impactCalculator = impactCalculator;
54
55      // initialize the tree modifier that will be used to perform edit operations over the tree
56      treeChart.ModifyTree = Modify;
57    }
58
59    /// <summary>
60    /// Remove, Replace or Insert subtrees
61    /// </summary>
62    /// <param name="tree">The symbolic expression tree</param>
63    /// <param name="parent">The insertion point (ie, the parent node who will receive a new child)</param>
64    /// <param name="oldChild">The subtree to be replaced</param>
65    /// <param name="newChild">The replacement subtree</param>
66    /// <param name="removeSubtree">Flag used to indicate if whole subtrees should be removed (default behavior), or just the subtree root</param>
67    private void Modify(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode parent,
68      ISymbolicExpressionTreeNode oldChild, ISymbolicExpressionTreeNode newChild, bool removeSubtree = true) {
69      if (oldChild == null && newChild == null)
70        throw new ArgumentNullException("Cannot deduce operation type from the arguments. Please provide non null operands.");
71      if (oldChild == null) {
72        // insertion operation
73        parent.AddSubtree(newChild);
74        newChild.Parent = parent;
75      } else if (newChild == null) {
76        // removal operation
77        parent.RemoveSubtree(parent.IndexOfSubtree(oldChild));
78        if (!removeSubtree) {
79          for (int i = oldChild.SubtreeCount - 1; i >= 0; --i) {
80            var subtree = oldChild.GetSubtree(i);
81            oldChild.RemoveSubtree(i);
82            parent.AddSubtree(subtree);
83          }
84        }
85      } else {
86        // replacement operation
87        var replacementIndex = parent.IndexOfSubtree(oldChild);
88        parent.RemoveSubtree(replacementIndex);
89        parent.InsertSubtree(replacementIndex, newChild);
90        newChild.Parent = parent;
91        if (changedNodes.ContainsKey(oldChild)) {
92          changedNodes.Add(newChild, changedNodes[oldChild]); // so that on double click the original node is restored
93          changedNodes.Remove(oldChild);
94        } else {
95          changedNodes.Add(newChild, oldChild);
96        }
97      }
98      treeState = IsValid(tree) ? TreeState.Valid : TreeState.Invalid;
99      switch (treeState) {
100        case TreeState.Valid:
101          this.grpViewHost.Enabled = true;
102          UpdateModel(Content.Model.SymbolicExpressionTree);
103          break;
104        case TreeState.Invalid:
105          this.grpViewHost.Enabled = false;
106          break;
107      }
108    }
109
110    // the optimizer always assumes 2 children for multiplication and addition nodes
111    // thus, we enforce that the tree stays valid so that the constant optimization won't throw an exception
112    // by returning 2 as the minimum allowed arity for addition and multiplication symbols
113    private readonly Func<ISymbol, int> GetMinArity = symbol => {
114      var min = symbol.MinimumArity;
115      if (symbol is Multiplication || symbol is Division) return Math.Max(2, min);
116      return min;
117    };
118    private bool IsValid(ISymbolicExpressionTree tree) {
119      treeChart.Tree = tree;
120      treeChart.Repaint();
121      // check if all nodes have a legal arity
122      var nodes = tree.IterateNodesPostfix().ToList();
123      bool valid = !nodes.Any(node => node.SubtreeCount < GetMinArity(node.Symbol) || node.SubtreeCount > node.Symbol.MaximumArity);
124
125      if (valid) {
126        // check if all variables are contained in the dataset
127        var variables = new HashSet<string>(Content.ProblemData.Dataset.DoubleVariables);
128        valid = nodes.OfType<VariableTreeNode>().All(x => variables.Contains(x.VariableName));
129      }
130
131      if (valid) {
132        btnOptimizeConstants.Enabled = true;
133        btnSimplify.Enabled = true;
134        treeStatusValue.Visible = false;
135      } else {
136        btnOptimizeConstants.Enabled = false;
137        btnSimplify.Enabled = false;
138        treeStatusValue.Visible = true;
139      }
140      this.Refresh();
141      return valid;
142    }
143
144    public new ISymbolicDataAnalysisSolution Content {
145      get { return (ISymbolicDataAnalysisSolution)base.Content; }
146      set { base.Content = value; }
147    }
148
149    protected override void RegisterContentEvents() {
150      base.RegisterContentEvents();
151      Content.ModelChanged += Content_Changed;
152      Content.ProblemDataChanged += Content_Changed;
153      treeChart.Repainted += treeChart_Repainted;
154      Progress.ShowOnControl(grpSimplify, progress);
155      progress.StopRequested += progress_StopRequested;
156    }
157    protected override void DeregisterContentEvents() {
158      base.DeregisterContentEvents();
159      Content.ModelChanged -= Content_Changed;
160      Content.ProblemDataChanged -= Content_Changed;
161      treeChart.Repainted -= treeChart_Repainted;
162      Progress.HideFromControl(grpSimplify, false);
163      progress.StopRequested -= progress_StopRequested;
164    }
165
166    private void Content_Changed(object sender, EventArgs e) {
167      UpdateView();
168      SetEnabledStateOfControls();
169    }
170
171    protected override void OnContentChanged() {
172      base.OnContentChanged();
173      foldedNodes.Clear();
174      changedNodes.Clear();
175      nodeIntervals.Clear();
176      nodeImpacts.Clear();
177      UpdateView();
178      viewHost.Content = this.Content;
179    }
180
181    private void treeChart_Repainted(object sender, EventArgs e) {
182      if (nodeImpacts != null && nodeImpacts.Count > 0)
183        PaintNodeImpacts();
184    }
185
186    private void progress_StopRequested(object sender, EventArgs e) {
187      cancellationTokenSource.Cancel();
188    }
189
190    private async void UpdateView() {
191      if (Content == null || Content.Model == null || Content.ProblemData == null) return;
192      var tree = Content.Model.SymbolicExpressionTree;
193      treeChart.Tree = tree.Root.SubtreeCount > 1 ? new SymbolicExpressionTree(tree.Root) : new SymbolicExpressionTree(tree.Root.GetSubtree(0).GetSubtree(0));
194
195      progress.Start("Calculate Impact and Replacement Values ...");
196      cancellationTokenSource = new CancellationTokenSource();
197      progress.CanBeStopped = true;
198      try {
199        var impactAndReplacementValues = await Task.Run(() => CalculateImpactAndReplacementValues(tree));
200        try {
201          await Task.Delay(300, cancellationTokenSource.Token); // wait for progressbar to finish animation
202        } catch (OperationCanceledException) { }
203
204        var replacementValues = impactAndReplacementValues.ToDictionary(x => x.Key, x => x.Value.Item2);
205        foreach (var pair in replacementValues.Where(pair => !(pair.Key is ConstantTreeNode))) {
206          foldedNodes[pair.Key] = MakeConstantTreeNode(pair.Value);
207        }
208       
209        foreach (var pair in impactAndReplacementValues) {
210          nodeImpacts[pair.Key] = pair.Value.Item1;
211        }
212
213        if (IntervalInterpreter.IsCompatible(tree) && DerivativeCalculator.IsCompatible(tree)) {
214          var regressionProblemData = Content.ProblemData as IRegressionProblemData;
215          if (regressionProblemData != null) {
216            var interpreter = new IntervalInterpreter();
217            var variableRanges = regressionProblemData.VariableRanges.GetIntervals();
218            IDictionary<ISymbolicExpressionTreeNode, Interval> intervals;
219            interpreter.GetSymbolicExpressionTreeIntervals(tree, variableRanges, out intervals);
220            foreach (var kvp in intervals) {
221              nodeIntervals[kvp.Key] = kvp.Value;
222            }
223          }
224        }
225      } finally {
226        progress.Finish();
227      }
228
229      progress.CanBeStopped = false;
230      PaintNodeImpacts();
231    }
232
233    protected virtual Dictionary<ISymbolicExpressionTreeNode, Tuple<double, double>> CalculateImpactAndReplacementValues(ISymbolicExpressionTree tree) {
234      var impactAndReplacementValues = new Dictionary<ISymbolicExpressionTreeNode, Tuple<double, double>>();
235      foreach (var node in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
236        if (progress.ProgressState == ProgressState.StopRequested) continue;
237        double impactValue, replacementValue, newQualityForImpactsCalculation;
238        impactCalculator.CalculateImpactAndReplacementValues(Content.Model, node, Content.ProblemData, Content.ProblemData.TrainingIndices, out impactValue, out replacementValue, out newQualityForImpactsCalculation);
239        double newProgressValue = progress.ProgressValue + 1.0 / (tree.Length - 2);
240        progress.ProgressValue = Math.Min(newProgressValue, 1);
241        impactAndReplacementValues.Add(node, new Tuple<double, double>(impactValue, replacementValue));
242      }
243      return impactAndReplacementValues;
244    }
245
246    protected abstract void UpdateModel(ISymbolicExpressionTree tree);
247
248    protected virtual ISymbolicExpressionTree OptimizeConstants(ISymbolicExpressionTree tree, IProgress progress) {
249      return tree;
250    }
251
252    private static ConstantTreeNode MakeConstantTreeNode(double value) {
253      var constant = new Constant { MinValue = value - 1, MaxValue = value + 1 };
254      var constantTreeNode = (ConstantTreeNode)constant.CreateTreeNode();
255      constantTreeNode.Value = value;
256      return constantTreeNode;
257    }
258
259    private void treeChart_SymbolicExpressionTreeNodeDoubleClicked(object sender, MouseEventArgs e) {
260      if (treeState == TreeState.Invalid) return;
261      var visualNode = (VisualTreeNode<ISymbolicExpressionTreeNode>)sender;
262      if (visualNode.Content == null) { throw new Exception("VisualNode content cannot be null."); }
263      var symbExprTreeNode = (SymbolicExpressionTreeNode)visualNode.Content;
264      var tree = Content.Model.SymbolicExpressionTree;
265      var parent = symbExprTreeNode.Parent;
266      int indexOfSubtree = parent.IndexOfSubtree(symbExprTreeNode);
267      if (changedNodes.ContainsKey(symbExprTreeNode)) {
268        // undo node change
269        parent.RemoveSubtree(indexOfSubtree);
270        var originalNode = changedNodes[symbExprTreeNode];
271        parent.InsertSubtree(indexOfSubtree, originalNode);
272        changedNodes.Remove(symbExprTreeNode);
273      } else if (foldedNodes.ContainsKey(symbExprTreeNode)) {
274        // undo node folding
275        SwitchNodeWithReplacementNode(parent, indexOfSubtree);
276      }
277      UpdateModel(tree);
278    }
279
280    private void SwitchNodeWithReplacementNode(ISymbolicExpressionTreeNode parent, int subTreeIndex) {
281      ISymbolicExpressionTreeNode subTree = parent.GetSubtree(subTreeIndex);
282      if (foldedNodes.ContainsKey(subTree)) {
283        parent.RemoveSubtree(subTreeIndex);
284        var replacementNode = foldedNodes[subTree];
285        parent.InsertSubtree(subTreeIndex, replacementNode);
286        // exchange key and value
287        foldedNodes.Remove(subTree);
288        foldedNodes.Add(replacementNode, subTree);
289      }
290    }
291
292    private void PaintNodeImpacts() {
293      var impacts = nodeImpacts.Values;
294      double max = impacts.Max();
295      double min = impacts.Min();
296      foreach (ISymbolicExpressionTreeNode treeNode in Content.Model.SymbolicExpressionTree.IterateNodesPostfix()) {
297        VisualTreeNode<ISymbolicExpressionTreeNode> visualTree = treeChart.GetVisualSymbolicExpressionTreeNode(treeNode);
298
299        if (!(treeNode is ConstantTreeNode) && nodeImpacts.ContainsKey(treeNode)) {
300          visualTree.ToolTip = visualTree.Content.ToString();
301          double impact = nodeImpacts[treeNode];
302
303          // impact = 0 if no change
304          // impact < 0 if new solution is better
305          // impact > 0 if new solution is worse
306          if (impact < 0.0) {
307            // min is guaranteed to be < 0
308            visualTree.FillColor = Color.FromArgb((int)(impact / min * 255), Color.Red);
309          } else if (impact.IsAlmost(0.0)) {
310            visualTree.FillColor = Color.White;
311          } else {
312            // max is guaranteed to be > 0
313            visualTree.FillColor = Color.FromArgb((int)(impact / max * 255), Color.Green);
314          }
315          visualTree.ToolTip += Environment.NewLine + "Node impact: " + impact;
316          var constantReplacementNode = foldedNodes[treeNode] as ConstantTreeNode;
317          if (constantReplacementNode != null) {
318            visualTree.ToolTip += Environment.NewLine + "Replacement value: " + constantReplacementNode.Value;
319          }
320        }
321        if (visualTree != null) {
322          if (nodeIntervals.ContainsKey(treeNode))
323            visualTree.ToolTip += String.Format($"{Environment.NewLine}Intervals: [{nodeIntervals[treeNode].LowerBound:G5} ... {nodeIntervals[treeNode].UpperBound:G5}]");
324          if (changedNodes.ContainsKey(treeNode)) {
325            visualTree.LineColor = Color.DodgerBlue;
326          } else if (treeNode is ConstantTreeNode && foldedNodes.ContainsKey(treeNode)) {
327            visualTree.LineColor = Color.DarkOrange;
328          }
329        }
330      }
331      treeChart.RepaintNodes();
332    }
333
334    private void btnSimplify_Click(object sender, EventArgs e) {
335      var simplifiedExpressionTree = TreeSimplifier.Simplify(Content.Model.SymbolicExpressionTree);
336      UpdateModel(simplifiedExpressionTree);
337    }
338
339    private async void btnOptimizeConstants_Click(object sender, EventArgs e) {
340      progress.Start("Optimizing Constants ...");
341      cancellationTokenSource = new CancellationTokenSource();
342      progress.CanBeStopped = true;
343      try {
344        var tree = (ISymbolicExpressionTree)Content.Model.SymbolicExpressionTree.Clone();
345
346        var newTree = await Task.Run(() => OptimizeConstants(tree, progress));
347        try {
348          await Task.Delay(300, cancellationTokenSource.Token); // wait for progressbar to finish animation
349        } catch (OperationCanceledException) { }
350        UpdateModel(newTree); // triggers progress.Finish after calculating the node impacts when model is changed
351      } catch {
352        progress.Finish();
353      }
354    }
355  }
356}
Note: See TracBrowser for help on using the repository browser.