The task in the open challenge of the Computer Cooking Contest [1] is a computerbased adaptation of cooking recipes. The present contribution proposes an approach to substitute ingredients of recipes. The approach is integrated in a speech dialogue system, called CooCo (Cooking Coach), introduced in [13]. CooCo is currently being further developed. A speech dialogue system is a suitable framework for this task:
-Speech input and output is a natural and convenient way to interact with technical devices or systems. -A speech dialogue system is particularly suitable in scenarios in which the user cannot use his or her hands for interaction. Keyboard, mouse or touchscreen are not convenient user interfaces while cooking. -Assuming a flexible dialogue management, spontaneous utterance of the user (like e.g. Oops, I do not have ... ) can be processed. -The user can be involved in a unobtrusive manner to improve the recipe variation result and tailor the recipe to her/his personal gusto. steps while cooking. Both tasks require a context-based dialogue system including modules for interpreting, planning and re-planning, as well as memorizing and learning. Different approaches to realize a speech dialogue manager exist, e.g. [9]. Lison distinguishes between hand-crafted and statistical approaches and proposes the toolkit OpenDial to combine both [8]. The dialogue manager of CooCo is based on OpenDial [10]. CooCo's assistance while cooking is conceptually based on a dynamic planning module to actively manage the cooking process. This goes beyond simply reading out the cooking steps aloud when the user asks for this [11]. CooCo formulates an action plan considering active and passive time of the user (e.g. cutting vs. simmering) and dependencies of the cooking steps [13]. The recipe advice mode includes generic models of gustatory preferences (e.g. hot or sweet depending on typical amount of ingredients like chili or sugar) which will be adapted based on the feedback of the user. A new feature, presented in this paper, is the variation of the cooking recipes.
The computer-based variations of cooking recipes addresses topics of artificial 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. [2]. Other approaches aim at replacing ingredients, e.g. by randomizing recipe items [3], by using cognitive super computing (based on IBM's computer system WATSON, [6]) or by just enlarging the database (by the help of a community) to find a matching recipe for every combination of ingredients [12]. The approach presented here addresses the replacement of ingredients. Thereby, I db is the set of all ingredients (I) of a specific database. A subset I rc ⊆ I db with ingredients, which belong to one recipe, is defined as I rc = {i rc,1 , . . . , i rc,m } with maximum number m of ingredients. The subset I sb = {i sb,1 , . . . , i sb,h } with h ≤ m and I sb ⊆ I rc comprises all ingredients which will be substituted. The food items which are candidates (C) to substitute one element of I sb belong to the set C sb = {c sb,1 , ..., c sb,n } with maximum number n of known food items. The set of the remaining ingredients of the recipe without the elements of I sb is defined as I rm = I rc \I sb . The approach is based on the computation of a substitution score s ranging from 0 to 120 indicating the fit of a specific substitution pair i sb,j ∈ I sb and c sb,k ∈ C sb . 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 [7], to include the substitution of ingredients.
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 differs 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 differ 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 e cd influences how common or uncommon a substitution candidate should be. The level e cb regulates how common or uncommon the combination of a substitution candidate and all elements of I rm is. For both levels three adjustment steps can be chosen by the user, ranging from 1 = very common to 3 = very uncommon.
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 first case, the ingredient i sb,j is not defined by the user. In the second case, i sb,j is the missing ingredient.
The user specifies some ingredients I us , 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 (I ms ) of I rc with those of I us . For this scenario, a plausibility check is necessary since not each combination of ingredients presents a suitable option for a recipe.
The central aim of the approach is to compute substitution scores s for different substitution candidates of C sb in relation to one element i sb,j of I sb . The candidate c sb,k with the highest score is finally proposed to the user. Considering the abbreviations i sb,j = i and c sb,k = c the substitution score s(i, c) is derived as
with s b as basic substitution score, s sp as special substitution score, s n as substitution score based on nutrition facts, and s cd and s cb 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 [5]. Additionally, a semantic net is created representing food
and by taking one of its elements to derive
with row number e cd and column number p as index of D cd,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 s b : It is assumed that food classes at a low semantic level (e.g. common mushrooms, morel or truffel in the class "mushrooms", level 2) are similar to each other. Therefore, the score s b is introduced depending on the level of class in the semantic net, cf. Fig. 1. special substitution score s sp : A few explicitly defined scores s sp 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 s n : 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 f n of two ingredients i A and i B is derived based on their nutrition facts n g as
with g = {c, f, p, e}. The mean value µ fn and the standard deviation σ fn derived from all f n,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
with row number e cb and column number q as index of B cb,q . The effect is, that if the user wants uncommon combinations, expressed as e cb = 3, a set of ingredients with a low f cb (c, I rm ) get a high score.
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 specific 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 flour, 5 dl bouillon, 5 dl milk, 1 tb parsely, minced, --salt, --pepper 6.1 Procedure for use case 1: Surprise me.
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 I rc as i sb [common mushrooms]. 2. Compute (s b + s sp ) for all c sb ∈ C sb [class "mushrooms": yellow boletus, morel, truffle; extract of class "vegetables": red pepper, tomato, cucumber] 3. Compute s n for all pairs of c sb and i sb [listing parsley, cauliflower, morel, yellow boletus as the one with a high score s n ]. 4. Derive s cd for all c sb . 5. Derive s cb for all c sb with respect to the elements of I rem . 6. Sum up s for each pair of c sb and i sb following Eq. 1.
Numerical results for the different experimental levels e cd and e cb 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 e cd of 1 and a medium or high e cb 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 truffle 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 cauliflower as substitution candidate as a less common ingredient than tomatoes. As the terms s cd and s cb are based on the statistical analysis of the recipe database, the result depends strongly on the size and the quality of the recipe database. In use case 2 the user desires a recipe with the ingredient set I us = {butter, flour, parsley, bouillon, red pepper}. Firstly, for all elements of I us the frequencies f cb to each other are checked heuristically: If all f cb > 0 and the mean µ f cb > 0.1, then CooCo accepts the set I us . 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 I us is mushroom soup, based on the simple rule to look for those recipes with the smallest number of missing ingredients I ms = {i ms |(i ms ∈ I rc ) ∧ (i ms / ∈ I us )}. 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 c sb for one of the missing ingredients. Some of the missing ingredients {pepper, salt, bouillon} are marked as standard ingredients in the database. CooCo assumes as first guess that they are available also in case the user did not mentioned them explicitly. If this is confirmed by the user, the only missing ingredients left are I ms = {common mushrooms, milk}. Considering the experimental levels, the score s is derived for all pairs of c sb with one of the elements of I ms . The computation result looking at the substitution pair red pepper -common mushrooms differs slightly compared to the result of use case 1 because milk is left out in the computation of s cb as it is missing. As consequence, f cb is classified here in B cb,3 resulting in s cb = 0, independently of e cb as the weight factor in Eq. 6 is zero. Therefore, for all e cb levels the score s is identical to s(j, 2) with e cd = j, cf. Tab. 1. The highest score s = 54 is reached for e cd = 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 different 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, s b +s sp +s n is computed in relation to all ingredients of I rm to get a hint if one of them could make up for the omission by increasing its quantity. In this specific example, the result of 17.5 for milk in relation to butter is not promising enough to propose this as solution. As final 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 final solution with appropriate comments based on the score s is presented to the user.
A new feature of the currently developed application CooCo is presented. An approach to derive recipe variations by replacing ingredients is introduced. Two different use cases are addressed. The introduced examples provide reasonable results. This first 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 first 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 final version of the paper and their suggestions for future work in this research field.