Changeset 8557 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic

Timestamp:

09/03/12 15:26:04 (12 years ago)

Author:

bburlacu

Message:

#1772: Introduced base class and interface for tracing operators. Introduced SymbolicExpressionTreeNodeComparer interface to be implemented by node matching operators. Fixed bug in the TracingSymbolicExpressionTreeManipulator where nodes modified by the Full- and OnePoint tree shakers were not correctly detected. The SymbolicExpressionTreeNodeSimilarityComparer is now injected in the tracing genetic operators as a parameter.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

Files:

• HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)
• SymbolicDataAnalysisExpressionTreeMatching.cs (modified) (6 diffs)
• SymbolicDataAnalysisProblem.cs (modified) (1 diff)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -169 +169 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="Analyzers\SymbolicDataAnalysisComplexityAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveValidationParetoBestSolutionAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveTrainingParetoBestSolutionAnalyzer.cs" />

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeMatching.cs

@@ -1 @@
-using System.Collections.Generic;
+using System;
+using System.Collections.Generic;
+using System.IO;
 using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  public class SymbolicExpressionTreeNodeSimilarityComparer : IEqualityComparer<ISymbolicExpressionTreeNode> {
-
-    public SymbolicExpressionTreeNodeSimilarityComparer(int similarityLevel) {
-      _similarityLevel = similarityLevel;
+  public enum SimilarityLevel {
+    Exact,   // everything is matched bit by bit (functions and terminals)
+    High,    // symbols are matched. leaf node types are matched
+    Relaxed  // only symbols are matched, leafs count as wildcards
+  }
+  [Item("SymbolicExpressionTreeNodeSimilarityComparer", "A comparison operator that checks node equality based on different similarity measures.")]
+  [StorableClass]
+  public class SymbolicExpressionTreeNodeSimilarityComparer : Item, ISymbolicExpressionTreeNodeComparer {
+    [StorableConstructor]
+    private SymbolicExpressionTreeNodeSimilarityComparer(bool deserializing) : base(deserializing) { }
+    private SymbolicExpressionTreeNodeSimilarityComparer(SymbolicExpressionTreeNodeSimilarityComparer original, Cloner cloner) : base(original, cloner) { }
+    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeNodeSimilarityComparer(this, cloner); }
+
+    private SimilarityLevel similarityLevel;
+    public SimilarityLevel SimilarityLevel {
+      get { return similarityLevel; }
+      set { similarityLevel = value; }
+    }
+
+    public SymbolicExpressionTreeNodeSimilarityComparer() {
+      this.similarityLevel = SimilarityLevel.Exact;
+    }
+
+    public SymbolicExpressionTreeNodeSimilarityComparer(SimilarityLevel similarityLevel) {
+      this.similarityLevel = similarityLevel;
     }
 
@@ -15 +41 @@
 
     public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
-      if (a.SubtreeCount != b.SubtreeCount) { return false; }
-      if (a.SubtreeCount > 0) { return a.Symbol.ToString().Equals(b.Symbol.ToString()); }
-      // compare leaf nodes according to desired similarity level
-      switch (_similarityLevel) {
-        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact):
-          if (a is ConstantTreeNode && b is ConstantTreeNode) {
-            return ((ConstantTreeNode)a).Value.Equals(((ConstantTreeNode)b).Value);
-          }
-          if (a is VariableTreeNode && b is VariableTreeNode) {
-            return (a as VariableTreeNode).Weight.Equals((b as VariableTreeNode).Weight);
-          }
+      var ca = a as ConstantTreeNode;
+      var cb = b as ConstantTreeNode;
+      var va = a as VariableTreeNode;
+      var vb = b as VariableTreeNode;
+
+      var aIsConstant = ca != null;
+      var aIsVariable = va != null;
+      var bIsConstant = cb != null;
+      var bIsVariable = vb != null;
+      var aIsFunction = (!(aIsConstant | aIsVariable));
+      var bIsFunction = (!(bIsConstant | bIsVariable));
+
+      if (aIsFunction)
+        return bIsFunction && a.Symbol.Name.Equals(b.Symbol.Name);
+      if (bIsFunction) // one is function and the other is not, return false
+        return false;
+
+      switch (similarityLevel) {
+        case (SimilarityLevel.Exact):
+          if (aIsConstant & bIsConstant)
+            return ca.Value.Equals(cb.Value);
+          if (aIsVariable & bIsVariable)
+            return va.Weight.Equals(vb.Weight);
           return false;
-
-        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.High):
-          return (a is ConstantTreeNode && b is ConstantTreeNode) || (a is VariableTreeNode && b is VariableTreeNode);
-
-        case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed):
+        case (SimilarityLevel.High):
+          return ((aIsConstant & bIsConstant) || (aIsVariable & bIsVariable));
+        case (SimilarityLevel.Relaxed):
           return true;
-
         default:
           return false;
@@ -39 +74 @@
     }
 
-    private readonly int _similarityLevel;
+    public static bool ExactlySimilar(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
+      return Similar(a, b, SimilarityLevel.Exact);
+    }
+
+    public static bool Similar(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SimilarityLevel level) {
+      var comp = new SymbolicExpressionTreeNodeSimilarityComparer(level);
+      return comp.Equals(a, b);
+    }
   }
 
   public class SymbolicExpressionTreeNodeOrderingComparer : IComparer<ISymbolicExpressionTreeNode> {
     public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
-      if (a is ConstantTreeNode) {
-        if (b is ConstantTreeNode)
-          return a.Symbol.ToString().Equals(b.Symbol.ToString()) ?
-            (a as ConstantTreeNode).Value.CompareTo((b as ConstantTreeNode).Value) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
-        return -1; // if b is not constant then we consider a < b because by convention Constant < Variable < Function
-      }
-      if (a is VariableTreeNode) {
-        if (b is ConstantTreeNode)
-          return 1;
-        if (b is VariableTreeNode)
-          return a.Symbol.ToString().Equals(b.Symbol.ToString()) ?
-            (a as VariableTreeNode).Weight.CompareTo((b as VariableTreeNode).Weight) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
-        return -1;
-      }
-      if (b is ConstantTreeNode || b is VariableTreeNode)
-        return 1; // a is a Function node and is greater than Constants or Variables
-
-      return a.Symbol.ToString().Equals(b.Symbol.ToString()) ? a.SubtreeCount.CompareTo(b.SubtreeCount) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
+      var ca = a as ConstantTreeNode;
+      var cb = b as ConstantTreeNode;
+      var va = a as VariableTreeNode;
+      var vb = b as VariableTreeNode;
+
+      var aIsConstant = ca != null;
+      var aIsVariable = va != null;
+      var bIsConstant = cb != null;
+      var bIsVariable = vb != null;
+      var aIsFunction = (!(aIsConstant | aIsVariable));
+      var bIsFunction = (!(bIsConstant | bIsVariable));
+
+      if (aIsFunction)
+        return bIsFunction ? a.Symbol.Name.CompareTo(b.Symbol.Name) : -1;
+      if (bIsFunction) // a is Constant or Variables
+        return 1;
+      if (aIsVariable)
+        return bIsVariable ? va.Weight.CompareTo(vb.Weight) : -1;
+      return
+        bIsVariable ? 1 : ca.Value.CompareTo(cb.Value);
     }
   }
@@ -68 +112 @@
   public class SymbolicExpressionTreeEqualityComparer : IEqualityComparer<ISymbolicExpressionTree> {
     public bool Equals(ISymbolicExpressionTree a, ISymbolicExpressionTree b) {
-      return SymbolicExpressionTreeMatching.FindMatch(a, b, _mode) == 0;
+      return SymbolicExpressionTreeMatching.FindMatch(a, b, similarityLevel) == 0;
     }
 
     public int GetHashCode(ISymbolicExpressionTree tree) {
-      return tree.Length;
-    }
-
-    private int _mode;
-    public void SetComparisonMode(int mode) {
-      _mode = mode;
+      return (tree.Length << 8) % 12345;
+    }
+
+    private SimilarityLevel similarityLevel;
+    public void SetComparisonMode(SimilarityLevel simLevel) {
+      similarityLevel = simLevel;
     }
   }
 
   public static class SymbolicExpressionTreeMatching {
-    public enum SimilarityLevel {
-      Exact,   // everything is matched bit by bit (functions and terminals)
-      High,    // symbols are matched. leaf node types are matched
-      Relaxed  // only symbols are matched, leafs count as wildcards
-    }
-
-    public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, int mode) {
+    public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, SimilarityLevel mode) {
       return FindMatch(t1, t2, mode) == 0;
     }
-    public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, int mode) {
+
+    public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, SimilarityLevel mode) {
       return FindMatch(t1, t2, mode) == 0;
     }
 
-    public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, int mode) {
-      var nodes = tree.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
-      var fragments = fragment.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
-      return FindMatch(nodes, fragments, mode) != -1;
+    public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, SimilarityLevel mode) {
+      var matches = FindMatches(tree, fragment, mode);
+      return matches.Count > 0;
     }
 
@@ -106 +144 @@
 
     public static void SortSubtrees(this ISymbolicExpressionTreeNode node) {
-      if (node.SubtreeCount > 0) {
-        var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode>;
-        if (subtrees == null) return;
-        subtrees.Sort(new SymbolicExpressionTreeNodeOrderingComparer());
-        foreach (var subtree in subtrees)
-          subtree.SortSubtrees();
-      }
-    }
-
-    public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, int mode) {
+      if (node.SubtreeCount == 0) return;
+      var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode>;
+      if (subtrees == null) return;
+      var comparer = new SymbolicExpressionTreeNodeOrderingComparer();
+      subtrees.Sort(comparer);
+      foreach (var subtree in subtrees)
+        subtree.SortSubtrees();
+    }
+
+    // return child that is the same as node
+    public static ISymbolicExpressionTreeNode FindChild(this ISymbolicExpressionTreeNode parent, ISymbolicExpressionTreeNode node) {
+      var subtrees = parent.Subtrees as List<ISymbolicExpressionTreeNode>;
+      var comparer = new SymbolicExpressionTreeNodeSimilarityComparer(SimilarityLevel.Exact);
+      return subtrees.Find(x => comparer.Equals(x, node));
+    }
+
+    public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, SimilarityLevel similarityLevel) {
       var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
       var nodesB = b.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
-      return FindMatch(nodesA, nodesB, mode);
-    }
-    public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, int mode) {
+      return FindMatch(nodesA, nodesB, similarityLevel);
+    }
+
+    public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SimilarityLevel similarityLevel) {
       var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
       var nodesB = b.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
-      return FindMatch(nodesA, nodesB, mode);
-    }
+      return FindMatch(nodesA, nodesB, similarityLevel);
+    }
+
     // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
     // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
-    public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, int mode) {
+    public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, SimilarityLevel similarityLevel) {
       int patlen = pat.Count;
       int seqlen = seq.Count;
       if (patlen == 0 || seqlen == 0) return -1;
-      var comparer = new SymbolicExpressionTreeNodeSimilarityComparer(mode);
+      var comparer = new SymbolicExpressionTreeNodeSimilarityComparer(similarityLevel);
       if (patlen == seqlen) return seq.SequenceEqual(pat, comparer) ? 0 : -1;
       for (int i = patlen; i <= seqlen; ++i) {
@@ -140 +187 @@
       return -1;
     }
+
+    public static List<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, SimilarityLevel similarityLevel) {
+      var comp = new SymbolicExpressionTreeNodeSimilarityComparer(similarityLevel);
+      return FindMatches(tree.Root, fragment, comp);
+    }
+
+    public static List<ISymbolicExpressionTreeNode>
+    FindMatches(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode fragment, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+      var matches = new List<ISymbolicExpressionTreeNode>();
+      root.ForEachNodePostfix(node => {
+        if (Match(node, fragment, comp) == fragment.GetLength()) matches.Add(node);
+      });
+      return matches;
+    }
+
+    ///<summary>
+    /// Finds the longest common subsequence in quadratic time and linear space
+    /// Variant of:
+    /// D . S. Hirschberg. A linear space algorithm for or computing maximal common subsequences. 1975.
+    /// http://dl.acm.org/citation.cfm?id=360861
+    /// </summary>
+    /// <returns>Number of pairs that were matched</returns>
+    public static int
+    Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+      if (!comp.Equals(a, b))
+        return 0;
+
+      int m = a.SubtreeCount;
+      int n = b.SubtreeCount;
+      if (m == 0 || n == 0) return 1;
+
+      var matrix = new int[m + 1, n + 1];
+      for (int i = 1; i <= m; ++i)
+        for (int j = 1; j <= n; ++j) {
+          var ai = a.GetSubtree(i - 1);
+          var bj = b.GetSubtree(j - 1);
+          int match = Match(ai, bj, comp);
+          matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + match);
+        }
+      return matrix[m, n] + 1;
+    }
+
+    public static int
+    LCS(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+      var nodesA = a.IterateNodesPrefix().ToList();
+      var nodesB = b.IterateNodesPrefix().ToList();
+      int m = nodesA.Count;
+      int n = nodesB.Count;
+      var matrix = new int[m + 1, n + 1];
+      for (int i = 1; i <= m; ++i) {
+        for (int j = 1; j <= n; ++j) {
+          int w = comp.Equals(a, b) ? 1 : 0;
+          matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + w);
+        }
+      }
+      return matrix[m, n];
+    }
+
+    public static void RenderTree(TextWriter writer, ISymbolicExpressionTree tree) {
+      RenderNode(writer, tree.Root, string.Empty);
+    }
+
+    public static void RenderNode(TextWriter writer, ISymbolicExpressionTreeNode node, string prefix) {
+      string label;
+      if (node is VariableTreeNode) {
+        var variable = node as VariableTreeNode;
+        label = string.Concat(string.Format("{0:0.000}", variable.Weight), '·', variable.VariableName);
+      } else if (node is ConstantTreeNode) {
+        var constant = node as ConstantTreeNode;
+        label = string.Format("{0:0.000}", constant.Value);
+      } else {
+        label = node.Symbol.ToString();
+      }
+
+      writer.Write(label);
+      if (node.SubtreeCount > 0) {
+        char connector, extender = ' ';
+        var padding = prefix + new string(' ', label.Length);
+        for (int i = 0; i != node.SubtreeCount; ++i) {
+          if (i == 0) {
+            if (node.SubtreeCount > 1) {
+              connector = RenderChars.JunctionDown;
+              extender = RenderChars.VerticalLine;
+            } else {
+              connector = RenderChars.HorizontalLine;
+              extender = ' ';
+            }
+          } else {
+            writer.Write(padding);
+            if (i == node.SubtreeCount - 1) {
+              connector = RenderChars.CornerRight;
+              extender = ' ';
+            } else {
+              connector = RenderChars.JunctionRight;
+              extender = RenderChars.VerticalLine;
+            }
+          }
+          writer.Write(string.Concat(connector, RenderChars.HorizontalLine));
+          var newPrefix = string.Concat(padding, extender, ' ');
+          RenderNode(writer, node.GetSubtree(i), newPrefix);
+        }
+      } else
+        writer.WriteLine();
+    }
+  }
+
+  // helper class providing characters for displaying a tree in the console
+  public static class RenderChars {
+    public const char JunctionDown = '┬';
+    public const char HorizontalLine = '─';
+    public const char VerticalLine = '│';
+    public const char JunctionRight = '├';
+    public const char CornerRight = '└';
   }
 }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs

@@ -319 +319 @@
         op.EvaluatorParameter.ActualName = EvaluatorParameter.Name;
       }
+      var comparers = ApplicationManager.Manager.GetInstances<ISymbolicExpressionTreeNodeComparer>().ToList();
+      if (comparers.Count > 0)
+        foreach (var op in operators.OfType<ITracingSymbolicExpressionTreeOperator>()) {
+          op.SymbolicExpressionTreeNodeComparerParameter.ActualValue = comparers.First();
+        }
     }