How can one manage thousands of IF…THEN…ELSE rules? • Hacker News Board

Re: How can one manage thousands of IF…THEN…ELSE rules?

#61

Post by pjscott » Mon, Sep 17, 2012, 4:44 AM UTC

wickedchicken wrote: post #11

Mildly unrelated, but I wanted to point out the awesomeness of the K-map[1] for handling simple minimization problems like these. Unfortunately, once your dimensions get large it becomes difficult for humans to visualize the optimizations, which is where Espresso[2][3] comes in handy. [1] http://en.wikipedia.org/wiki/Karnaugh_map [2] http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/in... [3] ftp://ftp.cs.man…

Ooh, espresso. There was also a tool called eqntott for converting boolean logic expressions in a human-readable form into the truth tables that Espresso takes as input. The source code was written in an archaic dialect of C, but here's a resurrected version that should compile on modern compilers:

http://code.google.com/p/eqntott/

I haven't touched this code since 2008, so beware of grues, but I remember it being a really slick system for minimizing boolean logic when you combine eqntott with espresso. Just the thing for an electrical engineering student who's sick of doing K-maps, which described me nicely at the time.

Re: How can one manage thousands of IF…THEN…ELSE rules?

#62

Post by sandGorgon » Mon, Sep 17, 2012, 5:11 AM UTC

I have an axiom "any sufficiently complex if-then-else ruleset can be modeled as a search problem with boosts".

I have modeled a logistics lookup system (assign "best" courier for an ecommerce setup) using a search solution. The rules were modeled as documents in a search index and looked up using weights. Fundamentally, what I did was flatten an if-then-else hierarchy and assign weights based on (roughly) level of nesting.

The con of this model is obvious - it is at best a heuristic. However, with clever overrides built in (as a separate search index?), you can get pretty close to the ideal solution.

The pro of this model is scalability - when your rules are in millions, this system scales beautifully.

Re: How can one manage thousands of IF…THEN…ELSE rules?

#63

Post by wickedchicken » Mon, Sep 17, 2012, 5:22 AM UTC

pjscott wrote: post #61

wickedchicken wrote: post #11

Mildly unrelated, but I wanted to point out the awesomeness of the K-map[1] for handling simple minimization problems like these. Unfortunately, once your dimensions get large it becomes difficult for humans to visualize the optimizations, which is where Espresso[2][3] comes in handy. [1] http://en.wikipedia.org/wiki/Karnaugh_map [2] http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/in... [3] ftp://ftp.cs.man…

Ooh, espresso. There was also a tool called eqntott for converting boolean logic expressions in a human-readable form into the truth tables that Espresso takes as input. The source code was written in an archaic dialect of C, but here's a resurrected version that should compile on modern compilers: http://code.google.com/p/eqntott/ I haven't touched this code since 2008, so beware of grues, but I remember it being a…

"This program was originally written at Berkeley in the early 80s"

This phrase gives me the same feeling I'd get from finding an old Thomas Bangalter track or something.

Re: How can one manage thousands of IF…THEN…ELSE rules?

#64

Post by antman » Mon, Sep 17, 2012, 6:57 AM UTC

SeanLuke wrote: post #13

Dn_Ab wrote: post #4

Such a great question. Want to predict cow movement while taking into consideration sudden events, food and sun, using thousands of if then rules? Sounds like the perfect problem for one of the following tree learners that not only manage themselves but build the model for you, in order of suitability to the problem* : Genetic Programming ADTree Random Forest Decision Tree Most of the work would be in figuring out th…

All machine learning techniques build models for you. ADTrees, Random Forests, and Decision trees are all classifiers, so they serve this guy's needs. Genetic Programming is not a machine learning technique: it is an optimization method for a very specific task and is quite unsuited for his purposes.

For all we know he could have produced the thousand ifs from the solution of a decision tree.

Re: How can one manage thousands of IF…THEN…ELSE rules?

#65

Post by mmcnickle » Mon, Sep 17, 2012, 9:06 AM UTC

instakill wrote: post #21

The question is an interesting one but it's futile in its context. You can't build a prediction engine for cattle movement. Adding factors like weather, food etc. seems well and dandy but there's hundreds if not thousands of other factors that are definitely going to be missing and that will render the prediction events pointless. Never mind the fact that you can throw in black swan type of events into the mix or jus…

You can't predict how an individual cow will move, but it's perfectly acceptable to use models to predict how cattle generally move. Similar to the way we use models to predict how humans navigate hallways and find paths across grass.[1] When you have a bulk of interacting particles, it tends to remove the "personality" of the individual, leaving you with how the group as a whole will move.

Philip Ball's (former editor of Nature) book Critical Mass[2] is an excellent read about the interesting effects that happen when you look at large number of complex interacting actors. He discusses the effects in traffic, pedestrian models, finance, plant growth etc. I highly recommend it.

[1]http://www.youtube.com/watch?v=8SmRBTJ-jeU This is just a video I picked out quickly, there are much better resources, I just can't find them on my phone.

[2]http://www.amazon.co.uk/Critical-Mass-Thing-Leads-Another/dp...

Re: How can one manage thousands of IF…THEN…ELSE rules?

#66

Post by StavrosK » Mon, Sep 17, 2012, 9:16 AM UTC

Retric wrote: post #42

StavrosK wrote: post #24

Earlier quoted context omitted.

As SeanLuke said, genetic programming is an optimization method. I don't see a function being optimized here, so what would you run it on?

If you had samples of cow behavior such as videos, you could then simulate behavior at each step and optimize for a genetic algorithm that produces similar behaviors. In this case it's probably not the right solution, but it's not that hard to swap out different learning algorithms when things don't seem to jell.

Maybe, but classification and optimization are two different problems. There's no function for the poster to optimize here.

Re: How can one manage thousands of IF…THEN…ELSE rules?

#67

Post by [deleted] » Mon, Sep 17, 2012, 9:16 AM UTC

Retric wrote: post #42

StavrosK wrote: post #24

Earlier quoted context omitted.

As SeanLuke said, genetic programming is an optimization method. I don't see a function being optimized here, so what would you run it on?

If you had samples of cow behavior such as videos, you could then simulate behavior at each step and optimize for a genetic algorithm that produces similar behaviors. In this case it's probably not the right solution, but it's not that hard to swap out different learning algorithms when things don't seem to jell.

[deleted]

Re: How can one manage thousands of IF…THEN…ELSE rules?

#68

Post by flyinRyan » Mon, Sep 17, 2012, 9:22 AM UTC

seanmcdirmid wrote: post #58

kamaal wrote: post #57

Earlier quoted context omitted.

How do video games solve it? Do you have any material one can read to learn more about this?

Often through physics engines. You express a bunch of constraints then let a physics engine solve them on each time step (and sometimes across multiple time steps). Custom (non-physics) solutions involve declarative sets of constraints being solved by some sort of engine; such solutions often start to resemble physics engines even if the physical rules even if the constraints are not exactly physical. Learning how to…

What would be a good place to start learning about what you're describing here?

Re: How can one manage thousands of IF…THEN…ELSE rules?

#69

Post by seanmcdirmid » Mon, Sep 17, 2012, 9:33 AM UTC

flyinRyan wrote: post #68

seanmcdirmid wrote: post #58

Earlier quoted context omitted.

Often through physics engines. You express a bunch of constraints then let a physics engine solve them on each time step (and sometimes across multiple time steps). Custom (non-physics) solutions involve declarative sets of constraints being solved by some sort of engine; such solutions often start to resemble physics engines even if the physical rules even if the constraints are not exactly physical. Learning how to…

What would be a good place to start learning about what you're describing here?

I would start with Erin Catto's Box2D.

http://box2d.org/

There are C#, Flash, Java versions if you aren't into C++. Lots of documentation on the web, but the getting started guide is good enough.

Re: How can one manage thousands of IF…THEN…ELSE rules?

#70

Post by exDM69 » Mon, Sep 17, 2012, 9:51 AM UTC

I suggested using Prolog in the comments. His problem description was not quite good enough for me to assess whether or not Prolog will be a good choice, but at least it's a candidate.

A Prolog program is essentially a list of rules that are written as an implication. Something like:

  moves_to(Cow, Location) :-
    hungry(Cow),
    current_location(Cow, OldLoc),
    food_in(OldLoc, OldFood), food_in(Location, Food),
    Food > OldFood.

In human language: a cow moves to a location if it's hungry and there's more food in that location than in current location.

I should probably write a proper answer.

edit: Added a proper answer to the stackoverflow with an almost complete introductory Prolog example. It's waiting for your upvotes :)