# Changeset 12024

Ignore:
Timestamp:
02/17/15 16:03:49 (7 years ago)
Message:

#2283: changed handling of inverse expressions in transformation of expressions to canonical form

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization
Files:
5 edited

Unmodified
Removed
• ## branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

 r12014 namespace HeuristicLab.Algorithms.Bandits { // helper to create canonical forms of expressions // NOTE: Not implemented yet (see unit test for divisions) // TODO: change symbolicregressionpoly10problem to use this class // this does not support expressions with constants (in transformations we assume constant opt is used) // supports the grammar // G(E): //     E -> V | V+E | V-E | V*E | V%E | V/E | (E) //     E -> V | V+E | V-E | V*E | V%E | (E) //     V -> //     "; // might produce expressions of the form |/x // might produce expressions of the form /x (= 1/x) // the pipe symbol | is used for the constant one (in comparison to other constants) private string sentence; InitLex(phrase); var e = CanonicalExpr(); return e.ToString(); return e.ToString(); } if (!f.IsSimpleFactor && f.Expr.Terms.Count == 1) { foreach (var invF in f.Expr.Terms.First().Factors) { if (invF.ToString() == "|") continue; if (invF.ToString() == "1") continue; invF.Invert(); factors.Add(invF); var results = new List(factors); foreach (var f in factorsArr) { if (f.ToString() == "|") results.Remove(f); if (f.ToString() == "|/(|)") results.Remove(f); if (f.ToString() == "1") results.Remove(f); if (f.ToString() == "1/(1)") results.Remove(f); if (f.IsInverse) { // find matching results.Remove(match); if (!results.Any()) results.Insert(idx, new Factor('|')); // when the factor is the last one then insert a one results.Insert(idx, new Factor('1')); // when the factor is the last one then insert a one // also mark as cancelled in the factorsArr idx = Array.IndexOf(factorsArr, match); factorsArr[idx] = new Factor('|'); factorsArr[idx] = new Factor('1'); } } } // remove all unnecessary "1* factors" if (results.Count == 0) results.Add(new Factor('|')); if (results.Count == 0) results.Add(new Factor('1')); return results; } var countComp = Factors.Count().CompareTo(other.Factors.Count()); if (countComp != 0) return countComp; return string.Join("", Factors).CompareTo(string.Join("", other.Factors)); foreach (var pair in Factors.Zip(other.Factors, Tuple.Create)) { var fComp = pair.Item1.CompareTo(pair.Item2); if (fComp != 0) return fComp; } return 0; } } var s = Expr == null ? symbol.ToString() : "(" + expr.ToString() + ")"; if (IsInverse) { return "|/" + s; return "/" + s; } else return s; } public override string ToString() { // if (Inverse && Terms.Count > 1) //   return "(" + string.Join("+", Terms) + ")"; // else if (Inverse && Terms.Count == 1) { //   return Terms.First().ToString().Replace("%", "#").Replace("*", "%").Replace("#", "*"); // } else return string.Join("+", Terms); }
• ## branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs

 r12014 if (f != null) factors.Add(f); var curSy = CurSy(); while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way while (curSy == '*' || curSy == '%') { // division and protected division symbols are handled in the same way if (curSy == '*') { NewSy(); r = variables[varIdx]; NewSy(); } else if (curSy == '|') { // pipe symbol is used in the expressionextender to represent constant one (|/x). } else if (curSy == '/') { // /-symbol used in the expressionextender to represent inverse (1/x). // this is necessary because we also use symbols 0..9 as indices for ERCs r = 1.0; NewSy(); r = 1.0 / Fact(variables, constants); } else if (curSy >= '0' && curSy <= '9') { int o = (byte)curSy - (byte)'0';
• ## branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

 r12014 public double Evaluate(string sentence) { var extender = new ExpressionExtender(); sentence = extender.CanonicalRepresentation(sentence); if (useConstantOpt) return OptimizeConstantsAndEvaluate(sentence); else { var extender = new ExpressionExtender(); Debug.Assert(SimpleEvaluate(sentence) == SimpleEvaluate(extender.CanonicalRepresentation(sentence))); public IEnumerable GetFeatures(string phrase) { // throw new NotImplementedException(); phrase = CanonicalRepresentation(phrase); return new Feature[] { new Feature(phrase, 1.0) }; return phrase.Split('+').Distinct().Select(t => new Feature(t, 1.0)); // return new Feature[] { new Feature(phrase, 1.0) }; }
• ## branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs

 r12014 r = Fact(d, erc); var curSy = CurSy(); while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way while (curSy == '*' || curSy == '%') { if (curSy == '*') { NewSy(); r = d[o]; NewSy(); } else if (curSy == '|') { // pipe symbol is used in the expressionextender to represent constant one (|/x). } else if (curSy == '/') { // /-symbol is used in the expressionextender to represent inverse (1/x). // this is necessary because we also use symbols 0..9 as indices for ERCs r = 1.0; NewSy(); r = 1.0 / Fact(d, erc); } else /* if (curSy >= '0' && curSy <= '9') */ { int o = (byte)curSy - (byte)'0';
• ## branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs

 r12014 Assert.AreEqual("a*b+b*c", extender.CanonicalRepresentation("b*(c-a)")); Assert.AreEqual("a*b+a*d+b*c+c*d", extender.CanonicalRepresentation("(b-d)*(c-a)")); Assert.AreEqual("|/(a+b)", extender.CanonicalRepresentation("c%c%(a+b)")); Assert.AreEqual("/(a+b)", extender.CanonicalRepresentation("c%c%(a+b)")); } [TestMethod] public void TestDivisionExpansion() { var extender = new ExpressionExtender(); Assert.AreEqual("a*|/c+b*|/c", extender.CanonicalRepresentation("(b+a)%c")); Assert.AreEqual("a*|/c*|/d+b*|/c*|/d", extender.CanonicalRepresentation("(b+a)%(d*c)")); Assert.AreEqual("a*|/(c+d)+b*|/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)")); Assert.AreEqual("a*b*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)")); Assert.AreEqual("a*/c+b*/c", extender.CanonicalRepresentation("(b+a)%c")); Assert.AreEqual("a*/c*/d+b*/c*/d", extender.CanonicalRepresentation("(b+a)%(d*c)")); Assert.AreEqual("a*/(c+d)+b*/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)")); Assert.AreEqual("a*b*/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)")); Assert.AreEqual("a*b*|/(a+b)*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)")); Assert.AreEqual("a*b*|/(c+d)*|/(a*|/e+b*|/e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)")); Assert.AreEqual("a*b*/(a+b)*/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)")); Assert.AreEqual("a*b*/(c+d)*/(a*/e+b*/e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)")); // a*b*e%(c+d)%(a+b) } public void TestDivisionCancellation() { var extender = new ExpressionExtender(); Assert.AreEqual("|", extender.CanonicalRepresentation("a%a")); Assert.AreEqual("1", extender.CanonicalRepresentation("a%a")); Assert.AreEqual("a", extender.CanonicalRepresentation("a*a%a")); Assert.AreEqual("|/a", extender.CanonicalRepresentation("(a%a)%a")); Assert.AreEqual("|/a", extender.CanonicalRepresentation("a%a%a")); Assert.AreEqual("/a", extender.CanonicalRepresentation("(a%a)%a")); Assert.AreEqual("/a", extender.CanonicalRepresentation("a%a%a")); Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)")); Assert.AreEqual("|", extender.CanonicalRepresentation("(a+b)%(b+a)")); Assert.AreEqual("|/a+|/b", extender.CanonicalRepresentation("(a+b)%(a*b)")); Assert.AreEqual("a*|/(a*c*|/b+e*|/d*|/f)+b*|/(a*c*|/b+e*|/d*|/f)", extender.CanonicalRepresentation("(a+b)%(a%b*c+e%f%d)")); Assert.AreEqual("|", extender.CanonicalRepresentation("(a%a%a+b%b%b)%(a%a*a%a%a+b%b*b%b%b)")); Assert.AreEqual("|", extender.CanonicalRepresentation("(a%(a%a)+b%(b%b))%(a+b)")); Assert.AreEqual("1", extender.CanonicalRepresentation("(a+b)%(b+a)")); Assert.AreEqual("/a+/b", extender.CanonicalRepresentation("(a+b)%(a*b)")); Assert.AreEqual("a*/(a*c*/b+e*/d*/f)+b*/(a*c*/b+e*/d*/f)", extender.CanonicalRepresentation("(a+b)%(a%b*c+e%f%d)")); Assert.AreEqual("1", extender.CanonicalRepresentation("(a%a%a+b%b%b)%(a%a*a%a%a+b%b*b%b%b)")); Assert.AreEqual("1", extender.CanonicalRepresentation("(a%(a%a)+b%(b%b))%(a+b)")); }
Note: See TracChangeset for help on using the changeset viewer.