Changeset 15131 for stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimplifier.cs

Timestamp:

07/06/17 10:19:37 (7 years ago)

Author:

gkronber

Message:

#2650: merged r14826 from trunk to stable. The only remaining conflict is DataTableControl and ScatterPlotControl which have been renamed within r14982 (-> tree conflict).

Location:

stable

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimplifier.cs (modified) (49 diffs)

stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimplifier.cs

@@ -1 +1 @@
 #region License Information
+
 /* HeuristicLab
  * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
@@ -18 +19 @@
  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
  */
+
 #endregion
 
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using HeuristicLab.Common;
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
@@ -32 +36 @@
   public class SymbolicDataAnalysisExpressionTreeSimplifier {
     private Addition addSymbol = new Addition();
-    private Subtraction subSymbol = new Subtraction();
     private Multiplication mulSymbol = new Multiplication();
     private Division divSymbol = new Division();
@@ -62 +65 @@
       ISymbolicExpressionTreeNode rootNode = (new ProgramRootSymbol()).CreateTreeNode();
       rootNode.AddSubtree(GetSimplifiedTree(macroExpandedTree));
+
+#if DEBUG
+      // check that each node is only referenced once
+      var nodes = rootNode.IterateNodesPrefix().ToArray();
+      foreach(var n in nodes) if(nodes.Count(ni => ni == n) > 1) throw new InvalidOperationException();
+#endif
       return new SymbolicExpressionTree(rootNode);
     }
 
     // the argumentTrees list contains already expanded trees used as arguments for invocations
-    private ISymbolicExpressionTreeNode MacroExpand(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode node, IList<ISymbolicExpressionTreeNode> argumentTrees) {
+    private ISymbolicExpressionTreeNode MacroExpand(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode node,
+      IList<ISymbolicExpressionTreeNode> argumentTrees) {
       List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
       while (node.SubtreeCount > 0) node.RemoveSubtree(0);
@@ -98 +108 @@
     }
 
-
     #region symbol predicates
+
     // arithmetic
     private bool IsDivision(ISymbolicExpressionTreeNode node) {
@@ -120 +130 @@
       return node.Symbol is Average;
     }
+
     // exponential
     private bool IsLog(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Logarithm;
     }
+
     private bool IsExp(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Exponential;
     }
+
     private bool IsRoot(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Root;
     }
+
     private bool IsSquare(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Square;
     }
+
     private bool IsSquareRoot(ISymbolicExpressionTreeNode node) {
       return node.Symbol is SquareRoot;
     }
+
     private bool IsPower(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Power;
     }
+
     // trigonometric
     private bool IsSine(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Sine;
     }
+
     private bool IsCosine(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Cosine;
     }
+
     private bool IsTangent(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Tangent;
     }
+
     // boolean
     private bool IsIfThenElse(ISymbolicExpressionTreeNode node) {
       return node.Symbol is IfThenElse;
     }
+
     private bool IsAnd(ISymbolicExpressionTreeNode node) {
       return node.Symbol is And;
     }
+
     private bool IsOr(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Or;
     }
+
     private bool IsNot(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Not;
     }
+
     // comparison
     private bool IsGreaterThan(ISymbolicExpressionTreeNode node) {
       return node.Symbol is GreaterThan;
     }
+
     private bool IsLessThan(ISymbolicExpressionTreeNode node) {
       return node.Symbol is LessThan;
@@ -183 +208 @@
     }
 
+    private bool IsVariableBase(ISymbolicExpressionTreeNode node) {
+      return node is VariableTreeNodeBase;
+    }
+
+    private bool IsFactor(ISymbolicExpressionTreeNode node) {
+      return node is FactorVariableTreeNode;
+    }
+
+    private bool IsBinFactor(ISymbolicExpressionTreeNode node) {
+      return node is BinaryFactorVariableTreeNode;
+    }
+
     private bool IsConstant(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Constant;
@@ -191 +228 @@
       return node.Symbol is TimeLag;
     }
+
     private bool IsIntegral(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Integral;
@@ -203 +241 @@
     /// <returns></returns>
     public ISymbolicExpressionTreeNode GetSimplifiedTree(ISymbolicExpressionTreeNode original) {
-      if (IsConstant(original) || IsVariable(original)) {
+      if (IsConstant(original) || IsVariableBase(original)) {
         return (ISymbolicExpressionTreeNode)original.Clone();
       } else if (IsAddition(original)) {
@@ -254 +292 @@
     }
 
-
     #region specific simplification routines
+
     private ISymbolicExpressionTreeNode SimplifyAny(ISymbolicExpressionTreeNode original) {
       // can't simplify this function but simplify all subtrees 
@@ -303 +341 @@
         var remaining = original.Subtrees.Skip(2);
         return
-          MakeProduct(GetSimplifiedTree(first), Invert(remaining.Aggregate(GetSimplifiedTree(second), (a, b) => MakeProduct(a, GetSimplifiedTree(b)))));
+          MakeProduct(GetSimplifiedTree(first),
+            Invert(remaining.Aggregate(GetSimplifiedTree(second), (a, b) => MakeProduct(a, GetSimplifiedTree(b)))));
       }
     }
@@ -344 +383 @@
       return MakeNot(GetSimplifiedTree(original.GetSubtree(0)));
     }
+
     private ISymbolicExpressionTreeNode SimplifyOr(ISymbolicExpressionTreeNode original) {
       return original.Subtrees
@@ -349 +389 @@
         .Aggregate(MakeOr);
     }
+
     private ISymbolicExpressionTreeNode SimplifyAnd(ISymbolicExpressionTreeNode original) {
       return original.Subtrees
@@ -354 +395 @@
         .Aggregate(MakeAnd);
     }
+
     private ISymbolicExpressionTreeNode SimplifyLessThan(ISymbolicExpressionTreeNode original) {
       return MakeLessThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
     }
+
     private ISymbolicExpressionTreeNode SimplifyGreaterThan(ISymbolicExpressionTreeNode original) {
       return MakeGreaterThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
     }
+
     private ISymbolicExpressionTreeNode SimplifyIfThenElse(ISymbolicExpressionTreeNode original) {
-      return MakeIfThenElse(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)), GetSimplifiedTree(original.GetSubtree(2)));
-    }
+      return MakeIfThenElse(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)),
+        GetSimplifiedTree(original.GetSubtree(2)));
+    }
+
     private ISymbolicExpressionTreeNode SimplifyTangent(ISymbolicExpressionTreeNode original) {
       return MakeTangent(GetSimplifiedTree(original.GetSubtree(0)));
     }
+
     private ISymbolicExpressionTreeNode SimplifyCosine(ISymbolicExpressionTreeNode original) {
       return MakeCosine(GetSimplifiedTree(original.GetSubtree(0)));
     }
+
     private ISymbolicExpressionTreeNode SimplifySine(ISymbolicExpressionTreeNode original) {
       return MakeSine(GetSimplifiedTree(original.GetSubtree(0)));
     }
+
     private ISymbolicExpressionTreeNode SimplifyExp(ISymbolicExpressionTreeNode original) {
       return MakeExp(GetSimplifiedTree(original.GetSubtree(0)));
     }
+
     private ISymbolicExpressionTreeNode SimplifySquare(ISymbolicExpressionTreeNode original) {
       return MakeSquare(GetSimplifiedTree(original.GetSubtree(0)));
     }
+
     private ISymbolicExpressionTreeNode SimplifySquareRoot(ISymbolicExpressionTreeNode original) {
       return MakeSquareRoot(GetSimplifiedTree(original.GetSubtree(0)));
@@ -385 +436 @@
       return MakeLog(GetSimplifiedTree(original.GetSubtree(0)));
     }
+
     private ISymbolicExpressionTreeNode SimplifyRoot(ISymbolicExpressionTreeNode original) {
       return MakeRoot(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
@@ -392 +444 @@
       return MakePower(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
     }
+
     private ISymbolicExpressionTreeNode SimplifyTimeLag(ISymbolicExpressionTreeNode original) {
       var laggedTreeNode = original as ILaggedTreeNode;
@@ -401 +454 @@
       }
     }
+
     private ISymbolicExpressionTreeNode SimplifyIntegral(ISymbolicExpressionTreeNode original) {
       var laggedTreeNode = original as ILaggedTreeNode;
@@ -414 +468 @@
 
     #region low level tree restructuring
+
     private ISymbolicExpressionTreeNode MakeTimeLag(ISymbolicExpressionTreeNode subtree, int lag) {
       if (lag == 0) return subtree;
@@ -444 +499 @@
       } else if (!IsBoolean(t)) {
         var gtNode = gtSymbol.CreateTreeNode();
-        gtNode.AddSubtree(t); gtNode.AddSubtree(MakeConstant(0.0));
+        gtNode.AddSubtree(t);
+        gtNode.AddSubtree(MakeConstant(0.0));
         var notNode = notSymbol.CreateTreeNode();
         notNode.AddSubtree(gtNode);
@@ -484 +540 @@
       }
     }
+
     private ISymbolicExpressionTreeNode MakeAnd(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
       if (IsConstant(a) && IsConstant(b)) {
@@ -513 +570 @@
       }
     }
-    private ISymbolicExpressionTreeNode MakeLessThan(ISymbolicExpressionTreeNode leftSide, ISymbolicExpressionTreeNode rightSide) {
+
+    private ISymbolicExpressionTreeNode MakeLessThan(ISymbolicExpressionTreeNode leftSide,
+      ISymbolicExpressionTreeNode rightSide) {
       if (IsConstant(leftSide) && IsConstant(rightSide)) {
         var lsConst = leftSide as ConstantTreeNode;
@@ -526 +585 @@
       }
     }
-    private ISymbolicExpressionTreeNode MakeGreaterThan(ISymbolicExpressionTreeNode leftSide, ISymbolicExpressionTreeNode rightSide) {
+
+    private ISymbolicExpressionTreeNode MakeGreaterThan(ISymbolicExpressionTreeNode leftSide,
+      ISymbolicExpressionTreeNode rightSide) {
       if (IsConstant(leftSide) && IsConstant(rightSide)) {
         var lsConst = leftSide as ConstantTreeNode;
@@ -539 +600 @@
       }
     }
-    private ISymbolicExpressionTreeNode MakeIfThenElse(ISymbolicExpressionTreeNode condition, ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch) {
+
+    private ISymbolicExpressionTreeNode MakeIfThenElse(ISymbolicExpressionTreeNode condition,
+      ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch) {
       if (IsConstant(condition)) {
         var constT = condition as ConstantTreeNode;
@@ -550 +613 @@
         } else {
           var gtNode = gtSymbol.CreateTreeNode();
-          gtNode.AddSubtree(condition); gtNode.AddSubtree(MakeConstant(0.0));
+          gtNode.AddSubtree(condition);
+          gtNode.AddSubtree(MakeConstant(0.0));
           ifNode.AddSubtree(gtNode);
         }
@@ -563 +627 @@
         var constT = node as ConstantTreeNode;
         return MakeConstant(Math.Sin(constT.Value));
+      } else if (IsFactor(node)) {
+        var factor = node as FactorVariableTreeNode;
+        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Sin));
+      } else if (IsBinFactor(node)) {
+        var binFactor = node as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sin(binFactor.Weight));
       } else {
         var sineNode = sineSymbol.CreateTreeNode();
@@ -569 +639 @@
       }
     }
+
     private ISymbolicExpressionTreeNode MakeTangent(ISymbolicExpressionTreeNode node) {
       if (IsConstant(node)) {
         var constT = node as ConstantTreeNode;
         return MakeConstant(Math.Tan(constT.Value));
+      } else if (IsFactor(node)) {
+        var factor = node as FactorVariableTreeNode;
+        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Tan));
+      } else if (IsBinFactor(node)) {
+        var binFactor = node as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Tan(binFactor.Weight));
       } else {
         var tanNode = tanSymbol.CreateTreeNode();
@@ -579 +656 @@
       }
     }
+
     private ISymbolicExpressionTreeNode MakeCosine(ISymbolicExpressionTreeNode node) {
       if (IsConstant(node)) {
         var constT = node as ConstantTreeNode;
         return MakeConstant(Math.Cos(constT.Value));
+      } else if (IsFactor(node)) {
+        var factor = node as FactorVariableTreeNode;
+        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Cos));
+      } else if (IsBinFactor(node)) {
+        var binFactor = node as BinaryFactorVariableTreeNode;
+        // cos(0) = 1 see similar case for Exp(binfactor)
+        return MakeSum(MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Cos(binFactor.Weight) - 1),
+          MakeConstant(1.0));
       } else {
         var cosNode = cosineSymbol.CreateTreeNode();
@@ -589 +675 @@
       }
     }
+
     private ISymbolicExpressionTreeNode MakeExp(ISymbolicExpressionTreeNode node) {
       if (IsConstant(node)) {
         var constT = node as ConstantTreeNode;
         return MakeConstant(Math.Exp(constT.Value));
+      } else if (IsFactor(node)) {
+        var factNode = node as FactorVariableTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Exp(w)));
+      } else if (IsBinFactor(node)) {
+        // exp( binfactor w val=a) = if(val=a) exp(w) else exp(0) = binfactor( (exp(w) - 1) val a) + 1
+        var binFactor = node as BinaryFactorVariableTreeNode;
+        return
+          MakeSum(MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Exp(binFactor.Weight) - 1), MakeConstant(1.0));
       } else if (IsLog(node)) {
         return node.GetSubtree(0);
@@ -605 +700 @@
       }
     }
+    private ISymbolicExpressionTreeNode MakeLog(ISymbolicExpressionTreeNode node) {
+      if (IsConstant(node)) {
+        var constT = node as ConstantTreeNode;
+        return MakeConstant(Math.Log(constT.Value));
+      } else if (IsFactor(node)) {
+        var factNode = node as FactorVariableTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Log(w)));
+      } else if (IsExp(node)) {
+        return node.GetSubtree(0);
+      } else if (IsSquareRoot(node)) {
+        return MakeFraction(MakeLog(node.GetSubtree(0)), MakeConstant(2.0));
+      } else {
+        var logNode = logSymbol.CreateTreeNode();
+        logNode.AddSubtree(node);
+        return logNode;
+      }
+    }
 
     private ISymbolicExpressionTreeNode MakeSquare(ISymbolicExpressionTreeNode node) {
@@ -610 +722 @@
         var constT = node as ConstantTreeNode;
         return MakeConstant(constT.Value * constT.Value);
+      } else if (IsFactor(node)) {
+        var factNode = node as FactorVariableTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w * w));
+      } else if (IsBinFactor(node)) {
+        var binFactor = node as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, binFactor.Weight * binFactor.Weight);
       } else if (IsSquareRoot(node)) {
         return node.GetSubtree(0);
@@ -618 +736 @@
       }
     }
+
     private ISymbolicExpressionTreeNode MakeSquareRoot(ISymbolicExpressionTreeNode node) {
       if (IsConstant(node)) {
         var constT = node as ConstantTreeNode;
         return MakeConstant(Math.Sqrt(constT.Value));
+      } else if (IsFactor(node)) {
+        var factNode = node as FactorVariableTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Sqrt(w)));
+      } else if (IsBinFactor(node)) {
+        var binFactor = node as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(binFactor.Weight));
       } else if (IsSquare(node)) {
         return node.GetSubtree(0);
@@ -631 +756 @@
     }
 
-    private ISymbolicExpressionTreeNode MakeLog(ISymbolicExpressionTreeNode node) {
-      if (IsConstant(node)) {
-        var constT = node as ConstantTreeNode;
-        return MakeConstant(Math.Log(constT.Value));
-      } else if (IsExp(node)) {
-        return node.GetSubtree(0);
-      } else if (IsSquareRoot(node)) {
-        return MakeFraction(MakeLog(node.GetSubtree(0)), MakeConstant(2.0));
-      } else {
-        var logNode = logSymbol.CreateTreeNode();
-        logNode.AddSubtree(node);
-        return logNode;
-      }
-    }
     private ISymbolicExpressionTreeNode MakeRoot(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
       if (IsConstant(a) && IsConstant(b)) {
@@ -650 +761 @@
         var constB = b as ConstantTreeNode;
         return MakeConstant(Math.Pow(constA.Value, 1.0 / Math.Round(constB.Value)));
+      } else if (IsFactor(a) && IsConstant(b)) {
+        var factNode = a as FactorVariableTreeNode;
+        var constNode = b as ConstantTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName,
+          factNode.Weights.Select(w => Math.Pow(w, 1.0 / Math.Round(constNode.Value))));
+      } else if (IsBinFactor(a) && IsConstant(b)) {
+        var binFactor = a as BinaryFactorVariableTreeNode;
+        var constNode = b as ConstantTreeNode;
+        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, 1.0 / Math.Round(constNode.Value)));
+      } else if (IsConstant(a) && IsFactor(b)) {
+        var constNode = a as ConstantTreeNode;
+        var factNode = b as FactorVariableTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, 1.0 / Math.Round(w))));
+      } else if (IsConstant(a) && IsBinFactor(b)) {
+        var constNode = a as ConstantTreeNode;
+        var factNode = b as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, 1.0 / Math.Round(factNode.Weight)));
+      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
+        var node0 = a as FactorVariableTreeNode;
+        var node1 = b as FactorVariableTreeNode;
+        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, 1.0 / Math.Round(v))));
       } else if (IsConstant(b)) {
         var constB = b as ConstantTreeNode;
@@ -677 +809 @@
       }
     }
+
+
     private ISymbolicExpressionTreeNode MakePower(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
       if (IsConstant(a) && IsConstant(b)) {
@@ -682 +816 @@
         var constB = b as ConstantTreeNode;
         return MakeConstant(Math.Pow(constA.Value, Math.Round(constB.Value)));
+      } else if (IsFactor(a) && IsConstant(b)) {
+        var factNode = a as FactorVariableTreeNode;
+        var constNode = b as ConstantTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(w, Math.Round(constNode.Value))));
+      } else if (IsBinFactor(a) && IsConstant(b)) {
+        var binFactor = a as BinaryFactorVariableTreeNode;
+        var constNode = b as ConstantTreeNode;
+        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, Math.Round(constNode.Value)));
+      } else if (IsConstant(a) && IsFactor(b)) {
+        var constNode = a as ConstantTreeNode;
+        var factNode = b as FactorVariableTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, Math.Round(w))));
+      } else if (IsConstant(a) && IsBinFactor(b)) {
+        var constNode = a as ConstantTreeNode;
+        var factNode = b as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, Math.Round(factNode.Weight)));
+      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
+        var node0 = a as FactorVariableTreeNode;
+        var node1 = b as FactorVariableTreeNode;
+        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, Math.Round(v))));
       } else if (IsConstant(b)) {
         var constB = b as ConstantTreeNode;
@@ -716 +870 @@
         // fold constants
         return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
-      } if (IsConstant(a) && !((ConstantTreeNode)a).Value.IsAlmost(1.0)) {
+      } else if ((IsConstant(a) && !((ConstantTreeNode)a).Value.IsAlmost(1.0))) {
         return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
-      } else if (IsVariable(a) && IsConstant(b)) {
+      } else if (IsVariableBase(a) && IsConstant(b)) {
         // merge constant values into variable weights
         var constB = ((ConstantTreeNode)b).Value;
-        ((VariableTreeNode)a).Weight /= constB;
+        ((VariableTreeNodeBase)a).Weight /= constB;
         return a;
-      } else if (IsVariable(a) && IsVariable(b) && AreSameVariable(a, b)) {
-        // cancel variables
+      } else if (IsFactor(a) && IsConstant(b)) {
+        var factNode = a as FactorVariableTreeNode;
+        var constNode = b as ConstantTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w / constNode.Value));
+      } else if (IsBinFactor(a) && IsConstant(b)) {
+        var factNode = a as BinaryFactorVariableTreeNode;
+        var constNode = b as ConstantTreeNode;
+        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, factNode.Weight / constNode.Value);
+      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
+        var node0 = a as FactorVariableTreeNode;
+        var node1 = b as FactorVariableTreeNode;
+        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u / v));
+      } else if (IsFactor(a) && IsBinFactor(b) && ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
+        var node0 = a as FactorVariableTreeNode;
+        var node1 = b as BinaryFactorVariableTreeNode;
+        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
+        var wi = Array.IndexOf(varValues, node1.VariableValue);
+        if (wi < 0) throw new ArgumentException();
+        var newWeighs = new double[varValues.Length];
+        node0.Weights.CopyTo(newWeighs, 0);
+        for (int i = 0; i < newWeighs.Length; i++)
+          if (wi == i) newWeighs[i] /= node1.Weight;
+          else newWeighs[i] /= 0.0;
+        return MakeFactor(node0.Symbol, node0.VariableName, newWeighs);
+      } else if (IsFactor(a)) {
+        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
+      } else if (IsVariableBase(a) && IsVariableBase(b) && AreSameTypeAndVariable(a, b) && !IsBinFactor(b)) {
+        // cancel variables (not allowed for bin factors because of division by zero)
         var aVar = a as VariableTreeNode;
         var bVar = b as VariableTreeNode;
@@ -731 +911 @@
         return a.Subtrees
           .Select(x => GetSimplifiedTree(x))
-         .Select(x => MakeFraction(x, b))
-         .Aggregate((c, d) => MakeSum(c, d));
+          .Select(x => MakeFraction(x, GetSimplifiedTree(b)))
+          .Aggregate((c, d) => MakeSum(c, d));
       } else if (IsMultiplication(a) && IsConstant(b)) {
         return MakeProduct(a, Invert(b));
@@ -767 +947 @@
         // x + 0 => x
         return a;
+      } else if (IsFactor(a) && IsConstant(b)) {
+        var factNode = a as FactorVariableTreeNode;
+        var constNode = b as ConstantTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select((w) => w + constNode.Value));
+      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
+        var node0 = a as FactorVariableTreeNode;
+        var node1 = b as FactorVariableTreeNode;
+        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u + v));
+      } else if (IsBinFactor(a) && IsFactor(b)) {
+        return MakeSum(b, a);
+      } else if (IsFactor(a) && IsBinFactor(b) &&
+        ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
+        var node0 = a as FactorVariableTreeNode;
+        var node1 = b as BinaryFactorVariableTreeNode;
+        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
+        var wi = Array.IndexOf(varValues, node1.VariableValue);
+        if (wi < 0) throw new ArgumentException();
+        var newWeighs = new double[varValues.Length];
+        node0.Weights.CopyTo(newWeighs, 0);
+        newWeighs[wi] += node1.Weight;
+        return MakeFactor(node0.Symbol, node0.VariableName, newWeighs);
       } else if (IsAddition(a) && IsAddition(b)) {
         // merge additions
@@ -829 +1030 @@
 
     // makes sure variable symbols in sums are combined
-    // possible improvement: combine sums of products where the products only reference the same variable
     private void MergeVariablesInSum(ISymbolicExpressionTreeNode sum) {
       var subtrees = new List<ISymbolicExpressionTreeNode>(sum.Subtrees);
       while (sum.Subtrees.Any()) sum.RemoveSubtree(0);
-      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
-                            let lag = (node is LaggedVariableTreeNode) ? ((LaggedVariableTreeNode)node).Lag : 0
-                            group node by node.VariableName + lag into g
+      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
+                            where node.SubtreeCount == 0
+                            group node by GroupId(node) into g
                             select g;
-      var unchangedSubtrees = subtrees.Where(t => !(t is VariableTreeNode));
+      var constant = (from node in subtrees.OfType<ConstantTreeNode>()
+                      select node.Value).DefaultIfEmpty(0.0).Sum();
+      var unchangedSubtrees = subtrees.Where(t => t.SubtreeCount > 0 || !(t is IVariableTreeNode) && !(t is ConstantTreeNode));
 
       foreach (var variableNodeGroup in groupedVarNodes) {
-        var weightSum = variableNodeGroup.Select(t => t.Weight).Sum();
-        var representative = variableNodeGroup.First();
-        representative.Weight = weightSum;
-        sum.AddSubtree(representative);
+        var firstNode = variableNodeGroup.First();
+        if (firstNode is VariableTreeNodeBase) {
+          var representative = firstNode as VariableTreeNodeBase;
+          var weightSum = variableNodeGroup.Cast<VariableTreeNodeBase>().Select(t => t.Weight).Sum();
+          representative.Weight = weightSum;
+          sum.AddSubtree(representative);
+        } else if (firstNode is FactorVariableTreeNode) {
+          var representative = firstNode as FactorVariableTreeNode;
+          foreach (var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
+            for (int j = 0; j < representative.Weights.Length; j++) {
+              representative.Weights[j] += node.Weights[j];
+            }
+          }
+          for (int j = 0; j < representative.Weights.Length; j++) {
+            representative.Weights[j] += constant;
+          }
+          sum.AddSubtree(representative);
+        }
       }
       foreach (var unchangedSubtree in unchangedSubtrees)
         sum.AddSubtree(unchangedSubtree);
+      if (!constant.IsAlmost(0.0)) {
+        sum.AddSubtree(MakeConstant(constant));
+      }
+    }
+
+    // nodes referencing variables can be grouped if they have
+    private string GroupId(IVariableTreeNode node) {
+      var binaryFactorNode = node as BinaryFactorVariableTreeNode;
+      var factorNode = node as FactorVariableTreeNode;
+      var variableNode = node as VariableTreeNode;
+      var laggedVarNode = node as LaggedVariableTreeNode;
+      if (variableNode != null) {
+        return "var " + variableNode.VariableName;
+      } else if (binaryFactorNode != null) {
+        return "binfactor " + binaryFactorNode.VariableName + " " + binaryFactorNode.VariableValue;
+      } else if (factorNode != null) {
+        return "factor " + factorNode.VariableName;
+      } else if (laggedVarNode != null) {
+        return "lagged " + laggedVarNode.VariableName + " " + laggedVarNode.Lag;
+      } else {
+        throw new NotSupportedException();
+      }
     }
 
@@ -853 +1091 @@
       if (IsConstant(a) && IsConstant(b)) {
         // fold constants
-        ((ConstantTreeNode)a).Value *= ((ConstantTreeNode)b).Value;
-        return a;
+        return MakeConstant(((ConstantTreeNode)a).Value * ((ConstantTreeNode)b).Value);
       } else if (IsConstant(a)) {
         // a * $ => $ * a
         return MakeProduct(b, a);
+      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
+        var node0 = a as FactorVariableTreeNode;
+        var node1 = b as FactorVariableTreeNode;
+        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u * v));
+      } else if (IsBinFactor(a) && IsBinFactor(b) && AreSameTypeAndVariable(a, b)) {
+        var node0 = a as BinaryFactorVariableTreeNode;
+        var node1 = b as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Weight);
+      } else if (IsFactor(a) && IsConstant(b)) {
+        var node0 = a as FactorVariableTreeNode;
+        var node1 = b as ConstantTreeNode;
+        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Select(w => w * node1.Value));
+      } else if (IsBinFactor(a) && IsConstant(b)) {
+        var node0 = a as BinaryFactorVariableTreeNode;
+        var node1 = b as ConstantTreeNode;
+        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Value);
+      } else if (IsBinFactor(a) && IsFactor(b)) {
+        return MakeProduct(b, a);
+      } else if (IsFactor(a) && IsBinFactor(b) &&
+        ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
+        var node0 = a as FactorVariableTreeNode;
+        var node1 = b as BinaryFactorVariableTreeNode;
+        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
+        var wi = Array.IndexOf(varValues, node1.VariableValue);
+        if (wi < 0) throw new ArgumentException();
+        return MakeBinFactor(node1.Symbol, node1.VariableName, node1.VariableValue, node1.Weight * node0.Weights[wi]);
       } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(1.0)) {
         // $ * 1.0 => $
         return a;
-      } else if (IsConstant(b) && IsVariable(a)) {
+      } else if (IsConstant(b) && IsVariableBase(a)) {
         // multiply constants into variables weights
-        ((VariableTreeNode)a).Weight *= ((ConstantTreeNode)b).Value;
+        ((VariableTreeNodeBase)a).Weight *= ((ConstantTreeNode)b).Value;
         return a;
-      } else if (IsConstant(b) && IsAddition(a)) {
+      } else if (IsConstant(b) && IsAddition(a) ||
+          IsFactor(b) && IsAddition(a) ||
+          IsBinFactor(b) && IsAddition(a)) {
         // multiply constants into additions
-        return a.Subtrees.Select(x => MakeProduct(x, b)).Aggregate((c, d) => MakeSum(c, d));
+        return a.Subtrees.Select(x => MakeProduct(GetSimplifiedTree(x), GetSimplifiedTree(b))).Aggregate((c, d) => MakeSum(c, d));
       } else if (IsDivision(a) && IsDivision(b)) {
         // (a1 / a2) * (b1 / b2) => (a1 * b1) / (a2 * b2)
@@ -888 +1153 @@
       } else if (IsMultiplication(a)) {
         // a is already an multiplication => append b
-        a.AddSubtree(b);
+        a.AddSubtree(GetSimplifiedTree(b));
         MergeVariablesAndConstantsInProduct(a);
         return a;
@@ -899 +1164 @@
       }
     }
+
     #endregion
 
-
     #region helper functions
+
     private bool ContainsVariableCondition(ISymbolicExpressionTreeNode node) {
       if (node.Symbol is VariableCondition) return true;
@@ -932 +1198 @@
     }
 
-    private bool AreSameVariable(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
-      var aLaggedVar = a as LaggedVariableTreeNode;
-      var bLaggedVar = b as LaggedVariableTreeNode;
-      if (aLaggedVar != null && bLaggedVar != null) {
-        return aLaggedVar.VariableName == bLaggedVar.VariableName &&
-          aLaggedVar.Lag == bLaggedVar.Lag;
-      }
-      var aVar = a as VariableTreeNode;
-      var bVar = b as VariableTreeNode;
-      if (aVar != null && bVar != null) {
-        return aVar.VariableName == bVar.VariableName;
-      }
-      return false;
+    private bool AreSameTypeAndVariable(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
+      return GroupId((IVariableTreeNode)a) == GroupId((IVariableTreeNode)b);
     }
 
@@ -951 +1206 @@
       var subtrees = new List<ISymbolicExpressionTreeNode>(prod.Subtrees);
       while (prod.Subtrees.Any()) prod.RemoveSubtree(0);
-      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
-                            let lag = (node is LaggedVariableTreeNode) ? ((LaggedVariableTreeNode)node).Lag : 0
-                            group node by node.VariableName + lag into g
+      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
+                            where node.SubtreeCount == 0
+                            group node by GroupId(node) into g
                             orderby g.Count()
                             select g;
-      var constantProduct = (from node in subtrees.OfType<VariableTreeNode>()
+      var constantProduct = (from node in subtrees.OfType<VariableTreeNodeBase>()
                              select node.Weight)
-                            .Concat(from node in subtrees.OfType<ConstantTreeNode>()
-                                    select node.Value)
-                            .DefaultIfEmpty(1.0)
-                            .Aggregate((c1, c2) => c1 * c2);
+        .Concat(from node in subtrees.OfType<ConstantTreeNode>()
+                select node.Value)
+        .DefaultIfEmpty(1.0)
+        .Aggregate((c1, c2) => c1 * c2);
 
       var unchangedSubtrees = from tree in subtrees
-                              where !(tree is VariableTreeNode)
-                              where !(tree is ConstantTreeNode)
+                              where tree.SubtreeCount > 0 || !(tree is IVariableTreeNode) && !(tree is ConstantTreeNode)
                               select tree;
 
       foreach (var variableNodeGroup in groupedVarNodes) {
-        var representative = variableNodeGroup.First();
-        representative.Weight = 1.0;
-        if (variableNodeGroup.Count() > 1) {
-          var poly = mulSymbol.CreateTreeNode();
-          for (int p = 0; p < variableNodeGroup.Count(); p++) {
-            poly.AddSubtree((ISymbolicExpressionTreeNode)representative.Clone());
+        var firstNode = variableNodeGroup.First();
+        if (firstNode is VariableTreeNodeBase) {
+          var representative = (VariableTreeNodeBase)firstNode;
+          representative.Weight = 1.0;
+          if (variableNodeGroup.Count() > 1) {
+            var poly = mulSymbol.CreateTreeNode();
+            for (int p = 0; p < variableNodeGroup.Count(); p++) {
+              poly.AddSubtree((ISymbolicExpressionTreeNode)representative.Clone());
+            }
+            prod.AddSubtree(poly);
+          } else {
+            prod.AddSubtree(representative);
           }
-          prod.AddSubtree(poly);
-        } else {
+        } else if (firstNode is FactorVariableTreeNode) {
+          var representative = (FactorVariableTreeNode)firstNode;
+          foreach (var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
+            for (int j = 0; j < representative.Weights.Length; j++) {
+              representative.Weights[j] *= node.Weights[j];
+            }
+          }
+          for (int j = 0; j < representative.Weights.Length; j++) {
+            representative.Weights[j] *= constantProduct;
+          }
+          constantProduct = 1.0;
+          // if the product already contains a factor it is not necessary to multiply a constant below
           prod.AddSubtree(representative);
         }
@@ -993 +1263 @@
     /// <summary>
     /// x => x * -1
-    /// Doesn't create new trees and manipulates x
+    /// Is only used in cases where it is not necessary to create new tree nodes. Manipulates x directly.
     /// </summary>
     /// <param name="x"></param>
@@ -1000 +1270 @@
       if (IsConstant(x)) {
         ((ConstantTreeNode)x).Value *= -1;
-      } else if (IsVariable(x)) {
-        var variableTree = (VariableTreeNode)x;
+      } else if (IsVariableBase(x)) {
+        var variableTree = (VariableTreeNodeBase)x;
         variableTree.Weight *= -1.0;
+      } else if (IsFactor(x)) {
+        var factorNode = (FactorVariableTreeNode)x;
+        for (int i = 0; i < factorNode.Weights.Length; i++) factorNode.Weights[i] *= -1;
+      } else if (IsBinFactor(x)) {
+        var factorNode = (BinaryFactorVariableTreeNode)x;
+        factorNode.Weight *= -1;
       } else if (IsAddition(x)) {
         // (x0 + x1 + .. + xn) * -1 => (-x0 + -x1 + .. + -xn)        
@@ -1024 +1300 @@
     /// <summary>
     /// x => 1/x
-    /// Doesn't create new trees and manipulates x
+    /// Must create new tree nodes
     /// </summary>
     /// <param name="x"></param>
@@ -1031 +1307 @@
       if (IsConstant(x)) {
         return MakeConstant(1.0 / ((ConstantTreeNode)x).Value);
+      } else if (IsFactor(x)) {
+        var factorNode = (FactorVariableTreeNode)x;
+        return MakeFactor(factorNode.Symbol, factorNode.VariableName, factorNode.Weights.Select(w => 1.0 / w));
       } else if (IsDivision(x)) {
         return MakeFraction(x.GetSubtree(1), x.GetSubtree(0));
@@ -1045 +1324 @@
     }
 
-    private ISymbolicExpressionTreeNode MakeVariable(double weight, string name) {
-      var tree = (VariableTreeNode)varSymbol.CreateTreeNode();
+    private ISymbolicExpressionTreeNode MakeFactor(FactorVariable sy, string variableName, IEnumerable<double> weights) {
+      var tree = (FactorVariableTreeNode)sy.CreateTreeNode();
+      tree.VariableName = variableName;
+      tree.Weights = weights.ToArray();
+      return tree;
+    }
+    private ISymbolicExpressionTreeNode MakeBinFactor(BinaryFactorVariable sy, string variableName, string variableValue, double weight) {
+      var tree = (BinaryFactorVariableTreeNode)sy.CreateTreeNode();
+      tree.VariableName = variableName;
+      tree.VariableValue = variableValue;
       tree.Weight = weight;
-      tree.VariableName = name;
       return tree;
     }
+
+
     #endregion
   }