This paper presents the participation of the Taaable team to the 2015 Computer Cooking Contest. The Taaable system addresses the mixology and the sandwich challenges. For the mixology challenge, the 2014 Taaable system was extended in two ways. First, a formal concept analysis approach is used to improve the ingredient substitution, which must take into account a limited set of available foods. Second, the adaptation of the ingredient quantities has also been improved in order to be more realistic with a real cooking setting. The adaptation of the ingredient quantities is based on a mixed linear optimization. The team also applied Taaable to the sandwich challenge.
to the sandwich challenges of the 2015 Computer Cooking Contest (CCC). The
edge representation, knowledge management and natural language processing [1].
case-based reasoning (CBR) system over RDFS [2] which allows reasoning over knowledge stored in a RDF store, as the one provided by the contest.
the ingredient substitution procedure which must manage unavailable foods. An approach based on formal concept analysis (FCA) allows improving ingredient substitutions. Moreover, the adaptation of the ingredient quantities has also been improved in order to be more realistic with a real cooking setting. The adaptation of the ingredient quantities is based on mixed linear optimization.
Copyright © 2015 for this paper by its authors. Copying permitted for private and academic purposes. In Proceedings of the ICCBR 2015 Workshops. Frankfurt, Germany. 0:02 Citrus Fruit
Juice 0:10 OrangeJuice
FruitJuice 0:14 0:14 Apple Pineapple Juice Juice 0:11 LemonJuice
Liquid
according to a set of initial recipes, one or more recipes matching a user query composed of a set of wanted ingredients and a set of unwanted ingredients. The
Tuuurbine is a generic CBR system over RDFS . The domain knowledge is represented by an RDFS base DK consisting of a set of triples of the form hC subClassOf Di where C and D are classes which belong to a same hierarchy (e.g, the food hierachy). Fig. 1 represents the domain knowledge for the running examples by a hierarchy whose edges C x! D represent the triples hC subClassOf Di. The retrieval knowledge is encoded by a cost function: cost(hC subClassOf Di) = x for an edge C x! D. This cost can be understood intuitively as the measure of \the generalization e ort" from C to D. How this cost is computed is detailed in [1].
A Tuuurbine case case is described by a set of triples of the form hU RIcase prop vali, where U RIcase is the URI of case, val is either a resource representing a class of the ontology or a value and prop is an RDF property linking case to a hierarchy class or to the value. For simpli cation, in this paper, we represent a case by a conjunction of expressions only of the form prop : val. For example, the \Rainbow" recipe is represented by the following index R, which means that \Rainbow" is a cocktail recipe made from vodka, orange juice, grenadine and curacao (ing stands for ingredient ).
R = dishType : CocktailDish
^ ing : Vodka ^ ing : OrangeJuice ^ ing : Grenadine ^ ing : Curacao
(
hU RIR dishType CocktailDishi belongs to the knowledge base.
where sign 2 f ; +; !; g, val is a resource representing a class of the ontology and prop is an RDF property belonging to the set of properties used to represent cases. For example,
Q = +dishType : CocktailDish
^ ing : Vodka ^ ing : Grenadine ^ !ing : Whiskey
(
that the requested case must have. + indicates that this feature must also occur in the source case whereas indicates that the source case may not have this feature, thus the adaptation phase has to make it appear in the nal case.
given in (
A one step-generalization is denoted by = prop : A prop : B, where A and B are classes belonging to the same hierarchy with A v B, and prop is a property used in the case de nition. This one step-generalization can be applied only if A is pre xed by or ! in Q. If A is pre xed by !, thus B is necessarily the top class of the hierarchy. For example, the generalization of !ing : Rum is ing : Food, meaning that if rum is not wanted, it has to be replaced by some other food. Classes of the query pre xed by + and cannot be generalized.
. . . n: = n : : : 1, with cost( ) = Pin=1 cost( i). For example, for:
Q = +dishType : CocktailDish
^ ing : Vodka ^ ing : PineappleJuice ^ ing : Grenadine ^ !ing : Whiskey
PineappleJuice is relaxed to FruitJuice according to the domain
knowledge of Fig. 1. At this rst step of generalization, (Q) =
(
PineappleJuice in R because FruitJuice of (Q) subsumes both OrangeJuice and PineappleJuice. Tuuurbine implements also an adaptation based on rules where some ingredients are replaced with others in a given context [4].
with PineappleJuice and Grenadine is an example of an adaptation rule. This rule-based adaptation is directly integrated in the retrieval process by searching cases indexed by the substituted ingredients for a query about the replacing ingredients, for example by searching recipes containing OrangeJuice and StrawberrySyrup for a query about PineappleJuice and Grenadine.
The Taaable knowledge base is WikiTaaable (http://wikitaaable.loria.
fr/), the knowledge base made available for this CCC edition. WikiTaaable is
composed of the four classical knowledge containers: (
tation rules) is encoded in a triple store, because WikiTaaable uses Semantic
3
The mixology challenge consists in retrieving a cocktail that matches a user query according to a set of available foods given by the CCC organizers (white rum, whiskey, vodka, orange juice, pineapple juice, sparkling water, coca-cola, beer grenadine syrup, lemon juice, mint leaves, lime, ice cube, brown sugar, salt, and pepper). Tuuurbine queries can express this kind of request using the and ! pre xes. Section 3.1 explains how the user query is transformed to take into account only the available foods, before being submitted to Tuuurbine . Two additionnal processes have been implemented to improve the Tuuurbine adaptation result. The rst process searches, when some ingredients of the source recipe are not available, the best way to replace them, or in some cases, to remove them (see Section 3.2). The second process uses Revisor/CLC (see Section 3.4) to adapt quantities. A new formalization of the quantity adaptation problem is proposed to obtain more realistic quantity values, taking into account the type of unit given in the source case (see Section 3.4).
food, the query may be built by adding to the initial user query the minimal set of classes of the food hierarchy that subsume the set of foods which are not available, each class being negatively pre xed by !. For example, let us assume that OrangeJuice and PineappleJuice are the only available fruit juices, that
Q = +dishType : CocktailDish ^ ing : Vodka ^ !ing : SugarCane. According to Fig. 1, LemonJuice, AppleJuice, Curacao, and StrawberrySyrup will be added to this initial query with a ! for expressing that the result cannot contain one of these non available classes of food, which includes their descendant classes. The extended query EQ submitted to Tuuurbine will be:
EQ = Q ^ !ing : LemonJuice ^ !ing : AppleJuice
^ !ing : StrawberrySyrup ^ !ing : Curacao
tation \replace Curacao with Food", due to !ing : Curacao.
When ingredients of the source case must be replaced because these pieces of food are not available, we choose FCA to exploit ingredient combination in cocktail recipes in order to search which ingredient(s) is/are the most used with the ones already used in the recipe that must be adapted. FCA is a classi cation method allowing object grouping according to the properties they share [5]. FCA takes as input a binary context, i.e. a table in which objects are described by properties. Table 1 shows an example of binary context with 7 objects (which are cocktails), described by two kinds of properties: the ingredients they use, and some more generic ingredient classes: Alcohol, the generic class of recipes with at least one alcohol, and Sugar, the generic class of recipes with at least one sweet ingredient, like sugar or syrup. These generic classes are pre xed by to be distinguished from the concrete ingredients. For example, the object
in this cocktail), and Alcohol, because Vodka is an alcohol.
AlcohVooldka White TreuqmuilCaachacBalue cOurcaancgaeoCojcuai-cceLoilmae SugarWhite CsaungearsGurgeanrasdyirnuep
Screwdriver
Rainbow
Tequila sunrise
Ti0Punch
Daiquiri
Caipirinha
Cuba libre
and the extent of the formal concept, such that (
To search a replacing ingredient in a given recipe or in a recipe according to pieces of food that will be kept, the idea is to exploit the lattice which captures concept similarities and organization. For example, concept #7, which intent is f Alcohol; Lime; Sugarg, allows an access to 3 cocktails containing at least one alcohol, at least one sugar, and lime. Adapting a cocktail can be based on the closeness between concepts. For example, when a replacing ingredient is searched for Cachaca in the Caipirinha cocktail (in the intent of concept #11), some similar concepts (i.e. sharing a same super-concept) can be used. In the lattice given in example, concept #11 can be generalized to concept number #7, which extent contains cocktails with some alcohol, lime and some sugar. The cocktails in the extent of concept #12 are similar to the one of concept #11, because they share the Alcohol, Lime, and Sugar properties. When removing\Cachaca" from the Caipirinha, a possible ingredient for substitution, given by the lattice, could be White rum.
using FCA for information retrieval. In Carpineto and Romano [6], the documents which are good answers to a query are searched in the lattice built from the document properties and from the query, around the concept representing the query. The same authors use this neighbour relation between concepts in a lattice for ordering documents returned by an information retrieval system [7].
Let CR be the formal concept such that Er(CR) = fRg. A formal concept
its intent I(C) does not contain the substituting ingredient (Curacao in the example) and maximizes jEr(C)j. First, C is searched in the ascendants of CR, then in its siblings, and nally in the descendants of the siblings. The ingredient to be substituted is replaced by I(C) n I(CR).
recipes has been collected. For this, we queried Yummly (http://www.yummly. com/). 16 queries were submitted; each query was composed of one ingredient (one available food) and was parametered to return all the Yummly cocktails and beverage recipes containing this ingredient. 9791 recipes have been collected.
satisfying the query. So, the results are ltered, only to keep recipes that use at least one available food. Afterwards, the remaining recipes are deduplicated.
with PineappleJuice and StrawberrySyrup with Grenadine in R, Taaable searches to replace Curacao which is not in the set of available foods. A part of the lattice resulting from the binary table containing recipes with
sponds to R, the recipe that must be adapted, and which has been added in the binary table to appear in the lattice. The most similar ingredient combination which includes PineappleJuice, Grenadine and Vodka is given by concept #7.
contains Amaretto which is not an available food. Concept #5 intent contains
concept #7, according to the selection procedure based on the maximal number of objects of Er. 3.4
Source = 10 c` of armagnac, 25 c` of rum, half a liter of milk,
Q = \I want a cocktail recipe with cream but without egg or armagnac."
for which Tuuurbine produces the following ingredient substitution:
substitute egg and armagnac with banana and kirsch
(
Formalization. Numerical variables are introduced to represent the ingredient quantities in a recipe. For the example, the following variables are introduced, for each food class C: alcoholC, massC, numberC, sugarC and volumeC, which represent, respectively, the quantity (in grams) of alcohol in the ingredient C of the recipe, its mass (in grams), its number, its quantity (in grams) of sugar and its volume (in centiliters).1 Therefore, the retrieved recipe can be expressed in this formalism by:
Source = (volumeArmagnac = 10) ^ (volumeRum = 25) ^ (volumeMilk = 50)
^ (numberEgg = 5) ^ (massGranulatedSugar = 125)
^ (volumeFreshCream = 25)
(
numbers). However, this can lead to adapted cases with, e.g., numberEgg = 1:7, which is avoided in most recipe books! For this reason, some variables v are declared as integer (denoted by (v) = integer), the other ones as real numbers (denoted by (v) = real).
The domain knowledge DK consists of a conjunction of conversion equations, conservation equations and sign constraints. The following conversion equations state that one egg without its shell has (on the average) a mass of 50 g, a volume of 5:2 c`, a quantity of sugar of 0:77 g and no alcohol:
massEgg = 50 sugarEgg = 0:77 numberEgg numberEgg
volumeEgg = 5:2
alcoholEgg = 0:
numberEgg
(
The following equations are also conjuncts of DK and represent the
conservation of masses, volumes, etc.:
massEggOrEquivalent = massEgg + massBanana
(
chy, thanks to some additional information. For instance, if C is a class of the hierarchy and fD1; D2; : : : ; Dpg is a set of subclasses of C forming a partition of C (i.e., for each individual x of C, there is exactly one i 2 f1; 2; : : : ; pg such that x belongs to Di), then massC (resp., volumeC , numberC , etc.) is equal to the sum of the massDi 's (resp., of the volumeDi 's, of the numberDi 's, etc.).
in the adapted recipe. By contrast, there should be some bananas and kirsch but this piece of information can be entailed by the conservation equations.
Q = (massEgg = 0) ^ (massArmagnac = 0)
(
The adaptation problem is now formalized: the source case is formalized
by (
The principle of revision-based adaptation consists in a minimal modi cation of DK ^ Source so that it becomes consistent with DK ^ Q. Such a minimal modi cation can be computed thanks to a belief revision operator based on a distance function d on , meaning that the modi cation from an x 2 to an y 2 is measured by d(x; y). Let S = M(DK ^ Source) and Q = M(DK ^ Q). The minimal modi cation from the source case to the query is therefore measured by d = d(S; Q) = infx2S;y2Q d(x; y). Thus, AdaptedCase is such that
M(AdaptedCase) = fy 2 Q j d(S; y) = d g where d(S; y) = infx2S d(x; y).
Now, d is assumed to be a Manhattan distance function:
n d(x; y) = X wijyi i=1 xij where wi > 0 is a weight associated to the variable vi. Such a weight captures the e ort of change for this variable. For example, if vi = volumeLemonJuice and vj = volumeVodka, then wi < wj means that the adaptation process is less \reluctant" to change the volume of lemon juice than to change the volume of vodka.
Under this assumption, M(AdaptedCase) is the solution of the following
optimization problem in y:
x 2 M(DK ^ Source) y 2 M(DK ^ Q)
minimize d(x; y)
(
yi n minimize X wizi i=1 which is linear, and thus can be solved with classical operational research techniques. It is noteworthy that if every variable is continuous, then this optimization problem is polynomial, otherwise, it is a mixed integer linear optimization, known to be an NP-hard problem. In practice, the more variables are integers, the more it will require computing time; thus, if a variable range is big enough, it may be more appropriate to consider it as real. The heuristic we have chosen is as follows. If, for a type of food F , it appears in all the recipes of the case base as units, then (numberF ) = integer.
pressed with all the n variables. From a human-interface viewpoint, some of these variables should not be displayed. For example, if an ingredient is given by its volume in the source recipe, then it should not be given as a mass in the adapted case. Since DK relates masses to volumes, there is no loss of information.
AdaptedCase
DK ^ (volumeKirsch = 9) ^ (volumeRum = 25) ^ (volumeMilk = 50) ^ (numberBanana = 2) ^ (massGranulatedSugar = 96) ^ (volumeFreshCream = 290) It can be noticed that AdaptedCase entails DK ^ Q, which was expected. For this example, the following weights have been chosen assuming that more a variable correponds to a general concept more its associated weight has to be large: wvolumeFood = 100 wvolumeBrandy = 5
wsugarFood = 50 wmassEggOrEquivalent = 10
walcoholFood = 50 and wv = 1 for any other variable v
AdaptedCase = 9 c` of kirsch, 25 c` of rum, half a liter of milk,
4
The sandwich challenge is addressed with the 2014 Taaable system [9], which is e cient for the ingredient susbtitution step. The preparation procedure of the adapted recipe uses, in the same order, the steps used in the source recipe, because the ontology-based substitution procedure of Taaable favors the substitution of ingredients of the same type (e.g., a sauce by a sauce). So, the order of the ingredients in the adapted recipe will be the same as in the source recipe. To adapt the textual preparation of the recipe, the text occurrences of the replaced ingredients are substituted with the replacing ingredients. A set of rules allows to identify plurals of the removed ingredient in the text, and replace them with the plural form of the replacing ingredients. For example, when replacing mayo with mustard, \Apply mayo on one slice, tomato sauce on the other." is adapted to \Apply mustard on one slice, tomato sauce on the other."
This paper has presented the two systems developed by the Taaable team for its participation to the 2015 CCC. The two systems are based on the previous version of Taaable, extended with two new approaches: a FCA approach to guide ingredient substitution, and an adaptation of the ingredient quantities based on a mixed linear optimization. The work presented here still needs a thorough evaluation: ongoing work addresses this issue, following the methodology introduced in [2].