Difference between revisions of "Recipe/Theory/Non-negative least squares"
(11 intermediate revisions by the same user not shown) | |||
Line 39: | Line 39: | ||
(2c) p<sub>j</sub> = (β<sub>1</sub> - β<sub>2</sub>)x<sub>1j</sub> + β<sub>2</sub>x<sub>1j</sub> + β<sub>2</sub>x<sub>2j</sub> + .... + β<sub>N</sub>x<sub>Nj</sub> | (2c) p<sub>j</sub> = (β<sub>1</sub> - β<sub>2</sub>)x<sub>1j</sub> + β<sub>2</sub>x<sub>1j</sub> + β<sub>2</sub>x<sub>2j</sub> + .... + β<sub>N</sub>x<sub>Nj</sub> | ||
− | (2d) p<sub>j</sub> = (β<sub>1</sub> - β<sub>2</sub>)x<sub>1j</sub> + β<sub>2</sub>(x<sub>1j</sub> + x<sub>2j</sub>) - β<sub>3</sub>(x<sub>1j</sub> + x<sub>2j</sub>) + β<sub>3</sub>(x<sub>1j</sub> + x<sub>2j</sub>) + .... + β<sub>N</sub>x<sub>Nj</sub> | + | (2d) p<sub>j</sub> = (β<sub>1</sub> - β<sub>2</sub>)x<sub>1j</sub> + β<sub>2</sub>(x<sub>1j</sub> + x<sub>2j</sub>) - β<sub>3</sub>(x<sub>1j</sub> + x<sub>2j</sub>) + β<sub>3</sub>(x<sub>1j</sub> + x<sub>2j</sub>) + β<sub>3</sub>x<sub>3j</sub> + .... + β<sub>N</sub>x<sub>Nj</sub> |
− | (2e) p<sub>j</sub> = (β<sub>1</sub> - β<sub>2</sub>)x<sub>1j</sub> + (β<sub>2</sub> - β<sub>3</sub>)(x<sub>1j</sub> + x<sub>2j</sub>) + β<sub>3</sub>(x<sub>1j</sub> + x<sub>2j</sub>) + .... + β<sub>N</sub>x<sub>Nj</sub> | + | (2e) p<sub>j</sub> = (β<sub>1</sub> - β<sub>2</sub>)x<sub>1j</sub> + (β<sub>2</sub> - β<sub>3</sub>)(x<sub>1j</sub> + x<sub>2j</sub>) + β<sub>3</sub>(x<sub>1j</sub> + x<sub>2j</sub> + x<sub>3j</sub>) + .... + β<sub>N</sub>x<sub>Nj</sub> |
(2f) etc. | (2f) etc. | ||
Line 50: | Line 50: | ||
== Bound ingredients == | == Bound ingredients == | ||
− | Do these bound ingredients have an upper limit? And can we determine these? | + | Do these bound ingredients have an upper limit? And can we determine these? For each bound ingredient there is a theoretical upper limit, which is set by the ingredient before. However probably it is not always possible to increase the bound ingredient to that limit. |
+ | |||
+ | By requiring a distance between the bounded ingredient and the ingredient after, we can try to increase the fraction for that limit. This can be done step by step until the variance increase above a set level. | ||
+ | |||
+ | The necessary formula's are described on [https://www.mathcha.io/editor/DZOW3fy7UqlHl4Fx3vV23UG2OWLF2LKoqlUjenVwm Matcha]. | ||
== Comparing approaches == | == Comparing approaches == | ||
Line 67: | Line 71: | ||
|- | |- | ||
| Forced NNLS pushed all || 0.334 || 0.334 || 0.031 || 0.334 || 0.031 || 0.031 || 0 || 0 || 137 | | Forced NNLS pushed all || 0.334 || 0.334 || 0.031 || 0.334 || 0.031 || 0.031 || 0 || 0 || 137 | ||
+ | |- | ||
+ | | Forced NNLS pushed chickpeas || 0.433 || 0.199 || 0.182 || 0.182 || 0.020 || 0.001 || 0.001 || 0.001 || 0.001 | ||
|} | |} | ||
Line 74: | Line 80: | ||
* Forced NNLS: Now a good order is maintained. Palm oil and chickpeas are bound (deviance is 0, no residuals); | * Forced NNLS: Now a good order is maintained. Palm oil and chickpeas are bound (deviance is 0, no residuals); | ||
* Forced NNLS pushed all: palm oil and chickpeas are moved up in the ingredient list. This increases the deviance to 127, so clearly a worse solution. Palm oil can clearly not be higher than sugar; | * Forced NNLS pushed all: palm oil and chickpeas are moved up in the ingredient list. This increases the deviance to 127, so clearly a worse solution. Palm oil can clearly not be higher than sugar; | ||
+ | * Forced NNLS Chickpeas pushed - the amount of chickpeas is now the same as hazelnuts, as was required. It did increase the sugars wrt to Forced NNLS and lowered the cocoa. The rice syrup is down as the sugar is up. The soy lecithin is also down, as the palm oil is up The variance and residual increased, but they are not to bad. It seems to suggest that some pushing is acceptable, but how much?; | ||
+ | |||
+ | [[Category:Recipe]] |
Latest revision as of 08:50, 27 February 2025
Theoretical solution
The best mathematical solution to the recipe estimation problem is offer by the non-negative least squares approach. There are multiple algorithms to solve approach. In this approach the general equation is:
(1) pj = β0 + β1x1j + .... + βNxNj
In this is
- pj - the nutritional value of the product for nutrient j;
- β0 - the base value without any ingredients;
- β1 - the fraction of ingredient 1 in the recipe;
- x1j - the nutritional value of ingredient 1 for nutrient j;
- N - the total number of ingredients;
- M - the total number of nutrients used;
Multiple equations
Formula (1) can often be solved directly. For instance for 7 ingredients and 7 nutrients, it will become 7 equations with 7 unknown. If there are less than 7 ingredients, there will be multiple solutions. If there are more than 7 ingredients, we should make a fit, either a least squares fit or a maximum likelihood fit. (or is it the other way around?)
There are however some constraints that could be applied:
It is clear that β0 must be zero and should be set as such in some solvers.
The values for βi will always be larger than 0. We are yet to see ingredients that will subtract nutrients.
Thus a solver that forces the βi larger than 0 is required
Non-Negative Least Squares
Solvers that only support solutions with βi > 0 are called Non-Negative Least Squares.
There seem to be many implementations for this. For instance nnls in the Rstudio package. Or nnls in the SciPy-package.
Unfortunately this approach does not always give the results we are looking for. The results favour ingredients that dominate the nutrients, like oil, sugar or salt. In most case the other ingredients are not needed and set to zero. In fact most products can be explained through these dominating ingredients. So another solution is needed that forces the other ingredients to participate.
Non-Negative Least Squares with forced order
With forced we mean that the first ingredients is more present than the second ingredient, the second more than the third, etc. This implies that βi > βi+1. Or βi-βi+1 > 0. By rewriting formula 1, we get another NNLS problem:
(2a) pj = β1x1j - β2x1j + β2x1j + .... + βNxNj
(2b) pj = (β1 - β2)x1j + β2x1j + .... + βNxNj
(2c) pj = (β1 - β2)x1j + β2x1j + β2x2j + .... + βNxNj
(2d) pj = (β1 - β2)x1j + β2(x1j + x2j) - β3(x1j + x2j) + β3(x1j + x2j) + β3x3j + .... + βNxNj
(2e) pj = (β1 - β2)x1j + (β2 - β3)(x1j + x2j) + β3(x1j + x2j + x3j) + .... + βNxNj
(2f) etc.
Formula 2f can be solved using a NNLS-approach, after which the original βi's can be calculated. Using this approach the results are very (too?) good.
This approach forces the ingredients which were first not participating, to contribute a bit to the recipe and the nutritional values. Although an ingredient i now participates, it is only pushed up and will be the same as the next ingredient i+1. In NNLS terms these are called bound ingredients (variables). And thus the fractions found for these ingredients are only a lower limit to the ingredient.
Bound ingredients
Do these bound ingredients have an upper limit? And can we determine these? For each bound ingredient there is a theoretical upper limit, which is set by the ingredient before. However probably it is not always possible to increase the bound ingredient to that limit.
By requiring a distance between the bounded ingredient and the ingredient after, we can try to increase the fraction for that limit. This can be done step by step until the variance increase above a set level.
The necessary formula's are described on Matcha.
Comparing approaches
The various approaches above have been tested with the Vegan Nutella.
Solver | Sugar | Palm oil | Hazelnuts | Chickpeas | Cocoa Powder | Rice Syrup | Soy Lecithins | Salt | Deviance |
---|---|---|---|---|---|---|---|---|---|
LS (no constraints) | -8.58 | -3.19 | 3.09 | -16.6 | 13.1 | 16.4 | NA | NA | 0 |
NNLS | 0.444 | 0.138 | 0.000 | 0.152 | 0.164 | 0.000 | 0.137 | 0.000 | 0 |
Forced NNLS | 0.394 | 0.175 | 0.175 | 0.099 | 0.099 | 0.076 | 0.017 | 0.001 | 0 |
Forced NNLS pushed all | 0.334 | 0.334 | 0.031 | 0.334 | 0.031 | 0.031 | 0 | 0 | 137 |
Forced NNLS pushed chickpeas | 0.433 | 0.199 | 0.182 | 0.182 | 0.020 | 0.001 | 0.001 | 0.001 | 0.001 |
Various solvers have been tried:
- LS: A straight least squares fit without any constraints fit gives an exact solution (deviance 0 and all residuals 0). It will not use soy and salt (underdetermined?). Also negative values;
- NNLS: non-negative least squares (deviance 0, no residuals). The order is not maintained. Hazelnuts and rice syrup forced to 0;
- Forced NNLS: Now a good order is maintained. Palm oil and chickpeas are bound (deviance is 0, no residuals);
- Forced NNLS pushed all: palm oil and chickpeas are moved up in the ingredient list. This increases the deviance to 127, so clearly a worse solution. Palm oil can clearly not be higher than sugar;
- Forced NNLS Chickpeas pushed - the amount of chickpeas is now the same as hazelnuts, as was required. It did increase the sugars wrt to Forced NNLS and lowered the cocoa. The rice syrup is down as the sugar is up. The soy lecithin is also down, as the palm oil is up The variance and residual increased, but they are not to bad. It seems to suggest that some pushing is acceptable, but how much?;