On Mon, Apr 29, 2013 at 5:09 PM, Aaron Meurer <[email protected]> wrote:
> On Mon, Apr 29, 2013 at 1:41 PM, Joseph Stradling > <[email protected]> wrote: > > Hello, > > My name is Joseph Stradling and I am a junior chemical cngineering > student > > transitioning into computer science at New Mexico Tech. > Welcome. > > > > I am interested in improving the pattern matching and recognition as a > > project for Google Summer of Code. I am currently trying to determine > which > > combination of possible project paths would be appropriately difficult > and > > useful. I am currently leaning towards: > > > > - Expression complexity measures > > As I understand it, this is determining the complexity of regular > > expressions. This seems challenging but fairly straightforward, and it > looks > > like there is pretty good literature on the subject > > The paper "Understanding expression simplification" by Jacques Carette > is a good introduction to these ideas (I can email you it if you can't > find it online). > > > > > - Expression tree similarity testing > > Basically make something to determine similarity in expression trees. It > > seems like something that can be solved with clever stacking, but I am > > probably missing a big piece of the challenge > > > > - Heuristic equivalence testing > > I assume this is just summing the two expressions and seeing if they > add to > > zero. > > > > - Semantic matching > > To be perfectly honest, I have no idea how to do this cleverly. Possibly > > with the heuristic equivalence testing? Also it says: > > > > implement semantic matching (e.g. expression: cos(x), pattern: sin(a*x) > + b) > > e.g by using power series for this purpose (improve series speed) > > I think there was some paper that described how to do this. > > > > > I don't really know how I would go about using series for semantic > matching. > > Bottom line: this seems very difficult and time consuming, but it could > just > > be that I am pretty clueless about it. It seems pretty useful so I > though it > > would be worth attempting > > > > Questions: > > What are expression signatures? > > I have no idea. This is probably referring to some idea from some > paper on the topic. My guess, based on the name, is some kind of > intelligent hash such that hash(a) != hash(b) means likely a != b and > hash(a) == hash(b) means likely a == b. > > > Is there anything that has been recently done in this area? > > I think Matthew's work with unify and logpy fits this, but he can give > you a more direct answer. > > You can also look at the recent work in the Fu trigsimp algorithm. > > Yup. I think that there are a lot of open and interesting problems in this idea. In the past Sympians have encoded many mathematical transformations into Python code. These are applied through a few functions like simplify, expand, factor which attempt to reduce expressions to a form that we believe is preferable (shorter, fewer terms, simpler terms, etc....) Exactly what we mean by preferable is unfortunately hard-coded into the source code - you can't specify what you want. The simplify function is one giant function, you can either call it or not call it but you can't use just a subset of the functionality. If you want a certain kind of expression (for example you don't want tangents but are fine with sines and cosines) there is no way to tell this to simplify so that it can use just the appropriate transformations. *The mathematical transformations are unnecessarily intertwined with a strategy and objective for their application.* I think it would be very interesting to break apart this connection so that Sympians define a set of valid transformations separately from how they're actually going to be called. The trigonometric simplification algorithms Aaron mentioned is an excellent example of a single module that does just this. I recommend taking a look at the introductory docstring of this code https://github.com/sympy/sympy/blob/master/sympy/simplify/fu.py There are many parts of SymPy that could be refactored to look more like this. I think that this would be a substantial improvement to our organization and would really open some door for future growth. The other ideas mentioned in this e-mail could be seen as a set of tools to guide a search for the optimal valid expression given an input and a set of transformation rules. That search is not a trivial one. > > Is there a student already doing this? I looked over the group posts but > I > > didn't see anything. > > Not that I know of. > > > Would this be enough to occupy the summer? > > Well, honestly you picked one of the ideas on the ideas list that is > rather open ended, in that the exact specifications of the problem are > not determined by us. Not to discourage you, but projects like these > will require a lot more from the applicant, because you will be > expected to take these vague ideas that honestly even we are not sure > about and make them concrete. > > If you do stick with this idea, one place to start would be to look at > other computer algebra systems and see if they implement anything > similar. That will give you some concrete ideas on what things work, > and how to do them There is certainly enough in the general topic to occupy the summer. The challenge will be to find a compelling-yet-achievable set of goals. -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy?hl=en-US. For more options, visit https://groups.google.com/groups/opt_out.
