Hello, this is 
Following the previous article - Defining the optimization problem in meal planning: first step toward AI application, we will take a closer look at how to find the optimum meal from the perspective of defined optimization problem for meal planning.
Previously, I explained the ultimate key is to find the set “x” of the meal that maximizes “f” based on the limiting conditions “h” and “g” from the meal preference function “f.”
And such conditions can differ depending on individuals and how to set the limiting conditions is ultimately the crucial condition that reflects each person’s position.
Ontology
To transfer knowledge and such knowledge structure so that a computer can process them, the concept of ontology must often be borrowed.
This is because the knowledge we have is ultimately related to each factor and also has a hierarchical relationship.
Ontology can largely be divided into 4 composing factors.
- Class: refers to the concept of naming something.
For example, it can define side dishes, main dishes, desserts, and teas. - Instance: expresses something more practical than class.
For example, it expresses kimchi, seaweed soup, carrot cake, and black tea. However, an instance can also become a class. That’s because kimchi can also be subdivided into radish kimchi, young radish kimchi, fresh kimchi, etc... - Property: connects a class or instance to a certain number (value).
For example, kimchi (defined here) has the weight of 100g. It has so many grams of sodium. Like so, a property can be defined. - Relation: can define the relationship between each class or instance.
For example, radish kimchi is a kimchi. (isA) As it expresses an inclusion relation, it can hierarchically connect and express each class/instance.
When such ontology is defined, small changes can be given when calculating the value.
For example, the value can be calculated by substituting with side dishes (sliced radish kimchi, pickled radish) that have the same hierarchical depth as kimchi.
Ultimately, because how fast can we perform calculation for finding the optimum meal and how efficiently can we search within the scope of value become important, such substitution becomes an important factor.
Especially, because finding the optimum menu doesn’t mean we are going to eat the same food every day, such variations are rather appropriate for meal recommendation.
Algorithm for finding the optimal menu
If the “f, g, x” in the optimization problem for menu recommendation have been previously defined for the algorithm for finding the optimum menu, now it is important to find the actual “x”. In fact, various methodologies can be applied, but here I will mainly present 3 methodologies.
- Linear Programming
- Case-based Reasoning
- Genetic Algorithm)
1. Linear Programming
Linear programming is the method of finding the optimum value by linearly laying out all the functions related to object function and limiting conditions. Such linear combination is possible if the foregoing meal preference function “f” is defined as the sum of food preferences included in each meal and a type of weighted value is given to each food.
The advantage of linear programming is that it can find the value relatively quickly. Here, quickly means the time complexity of the algorithm is not very high. In fact, solving it linearly has several advantages. Through the duality principle), the primal problem can be solved by changing it to a dual problem and the bound can be observed to see in which scope the value will exist.
Figure 1. Limiting conditions of linear programming and feasible value set
As you can see from the figure above, the addition of limiting conditions trims the scope of feasible values. Now, we have to find the “x” that maximizes “f” within the scope of feasible value.
2. Case-based Reasoning
In summary, it refers to the method of using or modifying/improving existing cases for a new problem based on the previously stored cases to learn new cases again and continuously storing such cases. In order to apply this to meal planning, it is important to have a certain amount of sets of diets that have been already well designed for people with certain conditions (including normal people) in a databased in advance. Based on this, it is possible to directly output or modify existing cases when a new person or new conditions emerge.
Here, how to store the format of knowledge becomes an important issue. To resolve the issue of how to identify and find similar cases, the similar and non-similar among each property must be well defined and the hierarchical structure between property/instance/class must be well defined. Here, in the process of determining whether the extracted case is a sound case or not, the intervention and reflection of (diet/nutrition) expert knowledge/opinion should be considered other than the help of the algorithm. This is similar to adding a type of limiting condition per case.
3. Genetic Algorithm
Figure 2. Example of cut and splice among genetic algorithm
The function “f” that we define may not always be linear or convex shaped. As such, in terms of finding the value that maximizes such function, the local optimum solution can be found but we cannot know if this is the global optimum solution. Nevertheless, we need to find the value that satisfies the given function “f” through the combination of each menu. Here, genetic algorithm assumes various genetic transformation mechanism that we all have heard before.
It performs methods such as exchanging parts of two given menus or suddenly changing (mutating) parts of existing menus. When each of the various menus go through such transformation, a menu that satisfies a certain standard can be found. Then, you can output the menu.
In my opinion, the advantages of genetic algorithm are that
- finding several local optimums is favorable for people because it expresses menu diversity in a situation where diverse menus should be provided anyway, and
- you can find new menus or food combinations by chance.
Today, we have looked at the methods and characteristics of finding the optimum menu through menu recommendation algorithm. Besides the algorithms presented above, I am sure many other algorithms can be applied.
The important points are 1) how to quickly find diverse menus and 2) contemplating how to reflect and modify the structure of knowledge.
In the next article, we will take a look at how to add limiting conditions according to the situation of each user. Thank you for your time.
Reference
[1] Khan AS, Hoffmann A. , Building a case-based diet recommendation system without a knowledge engineer, Artif Intell Med. 2003 Feb;27(2):155-79.
[2] Gaál B, Vassányi I, Kozmann G. , A novel artificial intelligence method for weekly dietary menu planning. , Methods Inf Med. 2005;44(5):655-64.
[3] Johan Aberg, Dealing with Malnutrition: A Meal Planning System for Elderly, AAAI Spring Symposium: Argumentation for Consumers of Healthcare, 2006
[4] Alessandro Mazzei, Luca Anselma, Franco De Michieli, Andrea Bolioli, Matteo Casu, Jelle Gerbrandy, Ivan Lunardi, Mobile Computing and Artificial Intelligence for Diet Management, ICIAP 2015 Workshops pp 342-349
Picture Source
figure1: https://en.wikipedia.org/wiki/Linear_programming , public domain
figure2: https://commons.wikimedia.org/wiki/Category:Evolutionary_algorithms , Creative Commons SA 3.0
