There is no conception in man's mind
which hath not at first, totally or in parts,
been begotten upon by the organs of sense.
---Thomas Hobbes, Leviathan, 1651

Thursday, June 2, 2011

Graph Theory, Flavor Combinations and Menu Development

What is a food combination?  It could be flavor combinations as in flavored yogurts, or also as in ice cream toppings or add-ins, or toppings on a pizza.  I've had an interest in scientifically modelling such combination since I was at the CIA.  Flavor combinations are as much an art as a science.  Chefs spend years learning, developing and refining these combinations - this process is never finished.

What models do we have?  Well, there are methods to evaluate pairs of flavors.  For example, you can easily give people two flavors and ask them to give you a number from 1 to 10 on how well they go together.  But that is boring, and not predictive.

An early study that excited me about flavor combinations was the development of a novel scale by Margaret Cliff and Marjorie King.  In 2005[1] they investigated the quality of wine and cheese pairings.  Their scale starts with a 10cm horizontal line.  On the far left side are the words "cheese dominates."  On the far right side is the phrase "wine dominates."  In the middle is the phrase "ideal pairing."  A subject would taste the wine and cheese, and then mark a line on the scale indicating their perception.  By assigning numbers (after the fact) to intervals along this scale, quantitative comparisons can be made to evaluate the quality of the pairings.  Using a bit fancier statistics, you might even able to be predict the qualities of ideal wine or cheese to pair together to hit that "ideal point."

Though this method is great, how do you properly evaluate more than two combinations?  Well, extending the King and Cliff methodology, you could employ an isometric grid (e.g. triangular grid) to evaluate the quality of three items (wine, cheese and cracker for example), but I suspect the people doing the evaluations would go cross-eyed.

Initially I tried to use the Napping method to answer this problem.  However, the methodology was not the right model.  So I put the thought on the back-burner and continued my research in multivariate statistics.

Figure 1: Combinations of salad toppings
Sometime in the summer of 2009 I had an idea.  Using graph theory, the math behind social network analysis (e.g. Facebook) I could model food combinations.  Graph theory uses two simple constructs: nodes and edges.  By modeling different flavors, or foods, or menu items as "nodes" and what these items are connected to in a compatible combination as "edges" the problem of finding a suitable model for food combinations is solved.  In a collaboration with John and Danny Ennis at the Institute for Perception, we put together a research program to investigate the suitability of this graph theoretic approach.

Figure 1 on the left shows a visualization of a graph related to a single person's preference for salad toppings.  Here are 14 toppings, represented as nodes (the black circles) and their pairwise compatibility represented as lines.  For this individual, blue cheese and broccoli would go well on a salad, but blue cheese and corn would not.  (To get this information, we simply asked the subject about the binary (yes/no) compatibility of all possible pairwise combinations of these ingredients).  The magic occurs when we use this visualization to predict larger combinations.  For example, the trio of carrots, onions and tomatoes all have connections between them, so the prediction that this person would like a salad with these three toppings holds true (which we tested, its true).  The same holds true for predictions of four, five and six topping salads, as long as all possible connections are present.  The beauty of this method is that we don't actually have to ask people about all possible combinations of three, four, five and six toppings to get this information (that would be almost 6,500 potential salads for 14 possible toppings), yet we get information about all of them!

The power and potential of this methodology was so exciting to me that I switched my dissertation topic a year and a half before graduation.

Perhaps the greatest contribution made with this method was in regard to the Army Field Rations known as MREs.  MREs contain 11 different food components such as entree, side, snack, bread, spread, dessert, snack, etc.  The Combat Feeding Directorate has many available items within each of those 11 categories.  So many, in fact, there's over 22 billion potential MREs.  By employing this graph theoretic approach outlined above we surveyed soldiers and applied the techniques to MRE menu development.  In the end, we presented the Combat Feeding group with the best optimal MRE menus given the available combinations.  This project was the capstone of my dissertation.

Happy graduation!

[1] King, M., and Cliff, M. 2005. Evaluation of ideal wine and cheese pairs using a deviation-from-ideal scale with food and wine experts. Journal of Food Quality, 28(3), 245-256.