In this paper a heuristic computer-based approach is described to vary cooking recipes by replacing ingredients. Conceptually, the approach is integrated in a speech dialogue system. The approach is based on a scoring system. The score value is used to rate di erent ingredients as candidates to substitute a speci c ingredient of a recipe. This substitution score depends on di erent factors: 1) rating of the similarity between the ingredient which has to be replaced and the substitution candidate 2) rating how well the substitution candidate ts the recipe 3) gustatory preferences of the user. The substitution candidate with the highest score is proposed to the user.
The task in the open challenge of the Computer Cooking Contest [
The computer-based variations of cooking recipes addresses topics of arti cial
intelligence and machine learning approaches. The task to derive the consequences
of the substitution of an ingredient on the textual description of the preparation
steps requires techniques of natural language understanding, e.g. [
The approach presented here addresses the replacement of ingredients.
Thereby, Idb is the set of all ingredients (I) of a speci c database. A subset Irc Idb
with ingredients, which belong to one recipe, is de ned as Irc = firc;1; : : : ; irc;mg
with maximum number m of ingredients. The subset Isb = fisb;1; : : : ; isb;hg with
h m and Isb Irc comprises all ingredients which will be substituted. The food
items which are candidates (C) to substitute one element of Isb belong to the set
Csb = fcsb;1; :::; csb;ng with maximum number n of known food items. The set of
the remaining ingredients of the recipe without the elements of Isb is de ned as
Irm = Irc nIsb. The approach is based on the computation of a substitution score
s ranging from 0 to 120 indicating the t of a speci c substitution pair isb;j 2 Isb
and csb;k 2 Csb. The substitution score is based on statistical information derived
from a recipe database and general food knowledge. The approach can also be
regarded as one module of a case-based reasoning process of a recipe advisor, as
it is described e.g. in [
The central task in the following two use cases is to propose a tasty recipe based on the user's input by replacing ingredients. The intention of the user di ers in the scenarios. Both use cases can be extended by including the question of undesired ingredients. In order to enlarge the number of possible recipe candidates, the proposed recipe variation approach can be applied in this case additionally to substitute undesired ingredients. Users di er in their gustatory preferences, one likes more traditional recipes, while the other is more open to new tastes. To adjust these individual preferences, two user parameters are introduced referred to as experimental levels. The experimental level ecd in uences how common or uncommon a substitution candidate should be. The level ecb regulates how common or uncommon the combination of a substitution candidate and all elements of Irm is. For both levels three adjustment steps can be chosen by the user, ranging from 1 = very common to 3 = very uncommon. 4.1
Based on one chosen recipe the user asks for a variation of this recipe. A similar scenario would be that the user realizes that one ingredient is missing but s/he still wants to cook the chosen recipe accepting variations. In both cases, CooCo can choose freely possible substitution candidates. In the rst case, the ingredient isb;j is not de ned by the user. In the second case, isb;j is the missing ingredient. 4.2
The user speci es some ingredients Ius, s/he wants to work with, but no recipe can be found in the database which uses all desired ingredients. The task for CooCo is now to propose one recipe which matches by replacing missing elements (Ims) of Irc with those of Ius. For this scenario, a plausibility check is necessary since not each combination of ingredients presents a suitable option for a recipe. 5
The central aim of the approach is to compute substitution scores s for di erent
substitution candidates of Csb in relation to one element isb;j of Isb. The
candidate csb;k with the highest score is nally proposed to the user. Considering the
abbreviations isb;j = i and csb;k = c the substitution score s(i; c) is derived as
s(i; c) = sb(i; c) + ssp(i; c) + sn(i; c) + scd(c) + scb(c; irmjirm 2 Irm);
(1)
with sb as basic substitution score, ssp as special substitution score, sn as
substitution score based on nutrition facts, and scd and scb as substitution scores
derived from a statistical analysis of the ingredients and their combination
frequency based on the recipe database. The derivation of each summand of Eq. 1
is explained in the following. The substitution of more than one ingredient can
be done by repeating the algorithm, up to now without considering the results
of subsequent substitution steps. As starting point a recipe database with 1.222
recipes is chosen [
Besides the parent-children constellation di erent properties of each food class are stored. These properties are grouped in (a) those properties considering only the class itself and (b) those properties related to other classes. For group (a), the following properties are introduced: nutrition facts ng; with g = fc; f; p; eg: Nutrition facts are stored for di erent food classes of level 2 or higher. In the rst version of CooCo, the variable nc contains carbohydrates, nf fat,np protein, and ne energy per 100 g. relative frequency fcd: For each food class its relative frequency is derived based on the recipe database. The number of recipes in which the class occurs as ingredient is divided by the total number of recipes. This frequency value describes how common or uncommon a certain ingredient is. substitution score scd: Based on the relative frequency fcd the score scd is derived, considering the experimental level ecd. The relative frequencies fcd are classi ed in ve categories. The rst category Dcd;1 contains rarely used and the last category Dcd;5 frequently used ingredients, assuming Dcd := [0 : : : 0:005 : : : 0:01 : : : 0:03 : : : 0:08 : : : 1:0]. The index of the category in combination with the experimental level ecd de nes the magnitude of the substitution score scd. This is implemented using a weighting matrix 2w11 w12 w13 w14 w153 W = 4w21 w22 w23 w24 w255 = 4 w31 w32 w33 w34 w35 2 2 1 0 1 23 0 0 0 0 05 2 1 0 1 2 and by taking one of its elements to derive scd = 10wecd;p; (2) (3) with row number ecd and column number p as index of Dcd;p.
The group (b) of properties considers the relation between two food classes to indicate how good they can substitute each other or how good they can be combined in one recipe. basic substitution score sb: It is assumed that food classes at a low semantic level (e.g. common mushrooms, morel or tru el in the class \mushrooms", level 2) are similar to each other. Therefore, the score sb is introduced depending on the level of class in the semantic net, cf. Fig. 1. special substitution score ssp: A few explicitly de ned scores ssp are stored (e.g. vegetables as substitution candidate for mushrooms or the milk product \tofu" as good substitution candidate for children of the class \meat"). substitution score based on nutrition facts sn: It is assumed that one food class of level 2 or higher is a good substitution candidate for another food class if they have similar nutrition facts. Therefore, the similarity factor fn of two ingredients iA and iB is derived based on their nutrition facts ng as fn;g(iA; iB) = jng(iA) ng(iB)j (ng(iA) + ng(iB)) ; (4) with g = fc; f; p; eg. The mean value fn and the standard deviation fn derived from all fn;g is used as measure of the similarity of the nutrition facts - being aware of the roughness and simplicity of this approach. The substitution score based on nutrition facts is derived as sn = min(2= fn ; 15) + min(2= fn ; 15): (5) relative combination frequency fcb: The frequency value fcb(iA; iB) expresses how often an ingredient iA is used in combination with a speci c ingredient iB of Idb. Therefore, the number of recipes nA&B, in which both ingredients iA and iB are included, is determined. This yields fcb(iA; iB) = nA&B=nA. As the denominator usually di ers numerically for fcb(iA; iB) and fcb(iB; iA), the frequencies di er correspondingly. Following this approach, it has to be considered that uncommon ingredients can get fcb values close to 1.0 as nA is close to nA&B. substitution score scb: The score scb is derived in a similar way as it is done for scd, but now considering the relative frequency fcb and the experimental level ecb. All frequencies fcb(c; i) of the substitution candidate c 2 Csb and the ingredients i 2 Irem have to be calculated rst. The mean value of all these frequencies is then derived as fcb(c; Irm). This value is nally assigned to one of the categories Bcb;1 up to Bcb;5, heuristically de ned as Bcb := [0 : : : 0:30 : : : 0:35 : : : 0:40 : : : 0:50 : : : 1:0]. Using the weighting matrix W from Eq. 2 the score is derived as scb = 10wecb;q; (6) with row number ecb and column number q as index of Bcb;q. The e ect is, that if the user wants uncommon combinations, expressed as ecb = 3, a set of ingredients with a low fcb(c; Irm) get a high score. 6
The knowledge base containing the recipe database and the semantic net are implemented in Prolog. Standard request functions are implemented, so that recipes including or excluding speci c ingredients can be looked up. The approach described above is conceptually tested, further implementation and evaluation is on going work. The procedures to handle both use cases (cf. Section 4) are described in the following based on one test example. The starting point is a simple mushroom soup recipe: 250 g common mushrooms, 40 g butter, 40 g our, 5 dl bouillon, 5 dl milk, 1 tb parsely, minced, - - salt, - - pepper 6.1
In the following description only some examples of the possible substitution candidates are listed. 1. Choose the ingredient with the largest proportion relative to all ingredients of Irc as isb [common mushrooms]. 2. Compute (sb + ssp) for all csb 2 Csb [class \mushrooms": yellow boletus, morel, tru e; extract of class \vegetables": red pepper, tomato, cucumber] 3. Compute sn for all pairs of csb and isb [listing parsley, cauli ower, morel, yellow boletus as the one with a high score sn]. 4. Derive scd for all csb. 5. Derive scb for all csb with respect to the elements of Irem. 6. Sum up s for each pair of csb and isb following Eq. 1.
Numerical results for the di erent experimental levels ecd and ecb are listed in Tab. 1. Parsley is left out as it is already part of the recipe. The results show, that a user with a low ecd of 1 and a medium or high ecb of 2 or 3 will be recommended a tomato soup. In case a very common combination of ingredients is wanted (s(1; 1)), morel soup is proposed instead. Reason for this is that the recipes with common mushrooms and morel often share the basic combination of ingredients. A user who wants uncommon ingredients in a uncommon combination gets tru e as substitution candidate (s(3; 3)). Elements of the class mushrooms are mostly preferred. A whole class like \mushrooms" could also be excluded, resulting in recommendations of cauli ower as substitution candidate as a less common ingredient than tomatoes. As the terms scd and scb are based on the statistical analysis of the recipe database, the result depends strongly on the size and the quality of the recipe database. 6.2
In use case 2 the user desires a recipe with the ingredient set Ius = fbutter, our, parsley, bouillon, red pepperg. Firstly, for all elements of Ius the frequencies fcb to each other are checked heuristically: If all fcb > 0 and the mean fcb > 0:1, then CooCo accepts the set Ius. Otherwise the dialogue with the user is reopened to ask for other set members. In the example, the set is accepted. The recipe that matches best Ius is mushroom soup, based on the simple rule to look for . those recipes with the smallest number of missing ingredients Ims = fimsj(ims 2 Irc) ^ (ims 2= Ius)g. However, red pepper is not part of the original recipe. The algorithm now attends to compute based on Eq. 1 as criteria whether red pepper is a suitable substitution candidate csb for one of the missing ingredients. Some of the missing ingredients fpepper, salt, bouillong are marked as standard ingredients in the database. CooCo assumes as rst guess that they are available also in case the user did not mentioned them explicitly. If this is con rmed by the user, the only missing ingredients left are Ims = fcommon mushrooms, milkg. Considering the experimental levels, the score s is derived for all pairs of csb with one of the elements of Ims. The computation result looking at the substitution pair red pepper - common mushrooms di ers slightly compared to the result of use case 1 because milk is left out in the computation of scb as it is missing. As consequence, fcb is classi ed here in Bcb;3 resulting in scb = 0, independently of ecb as the weight factor in Eq. 6 is zero. Therefore, for all ecb levels the score s is identical to s(j; 2) with ecd = j, cf. Tab. 1. The highest score s = 54 is reached for ecd = 1. Considering a threshold scheme of [120 : : : 80] (very good), ]80 : : : 40] (acceptable), ]40 : : : 0] (not recommended) for s, the substitution pair red pepper - common mushrooms is evaluated as "acceptable". In no case it is an option to replace milk with red pepper, the highest score is s = 29. This is reasonable, but a rule should be added in future versions to avoid the substitution of liquid and solid ingredients in any case. This is possible by adding an appropriate property in the semantic net. Milk remains here as missing candidate. Two di erent last options are possible: (1) Ask the user explicitly whether there is after all a potential substitution candidate. If yes, repeat the procedure. (2) Evaluate how well the missing ingredient could be omitted. Therefore, sb +ssp +sn is computed in relation to all ingredients of Irm to get a hint if one of them could make up for the omission by increasing its quantity. In this speci c example, the result of 17:5 for milk in relation to butter is not promising enough to propose this as solution. As nal step, the amount of liquid within the recipe ingredients is checked leading here to an increase of the amount of bouillon to recover the original amount of liquid. The nal solution with appropriate comments based on the score s is presented to the user. 7
A new feature of the currently developed application CooCo is presented. An approach to derive recipe variations by replacing ingredients is introduced. Two di erent use cases are addressed. The introduced examples provide reasonable results. This rst proposed version of the approach has to be further improved and expanded in future work. An evaluation of the substitution results is planned based on feedback of users integrated in the speech dialogue system. The mechanism how to choose the best starting recipe in use case 2 can be ameliorated, including e.g. more information of the gustatory preferences of the user. The present approach prefers recipes with a small number of ingredients. In summary, the approach is a rst step for computer-based tasty cooking recipe variations.
Acknowledgement. The authors would like to thank the anonymous reviewers for their helpful comments to improve the nal version of the paper and their suggestions for future work in this research eld.