Question about MM algorithm.

[CGLemon]

Hello, Yuki Kobayashi! I am Hung-Zhe Lin. I raise the new issue here instead of email because it is more easy to write Latex here.

On the Paper

After seeing your and Remi's implementations, I guess that there are some differences between the theories and the implementation. In the paper, simply it says that

$\gamma_{new} = \frac{W}{Den}$ $Den=\sum{\frac{C}{E}}$ $E=C*\gamma_{old}+D$

where W is the hyperparameter for each gammas. where C is the participants which relate to $\gamma_{old}$. where D is the participants which do not relate to $\gamma_{old}$.

Yours

(it is simplification formula, ignore i and j)

$\gamma_{new} = \frac{win + 1}{\sigma + V}$ $\sigma = \sum{\frac{C}{E}}$ $E=\sum{G}$ $V=\frac{2}{1 + \gamma_{old}}$

where G is the legal move gammas in this turn (per move). where E is all gammas in this turn (per move).

• I know that it update the new $\gamma$ after gathering all $\sigma$ and $\gamma$ , I skip this process.

Remi's

(it is simplification formula, ignore i and j)

$\gamma_{new} = \frac{win + 1}{\sigma + V}$ $\sigma = \sum{\frac{C}{E}}$ $E=\sum{G}$ $V=\frac{2}{1 + \gamma_{old}}$

where G is each updating participants gammas in this updating step. where E is all relation gammas in this updating step.

Question

Look like that your implementations and updating conditions are differences with paper. Why? Or may I wrong?

[kobanium]

@CGLemon Probably my implementation is essentially the same as Remi's implementation. Ej in my implementation holds the sum of $\gamma$ of all legal moves, so Ej is following equation, $E_j = \sum C_{ij}\gamma_{ij} + D_{ij}$ It is the same as $E_j$ definition described in the paper. Your understanding of $\gamma_{new}$ updating form, $\sigma$ and $V$ is correct.

Maybe I did not understand your question completely, so please ask again if my answer does not solve your question.

[CGLemon]

@kobanium (There were some typos in the formula wrote by me. I fixed them.)

I misunderstood the $E_j$ meaning before. Now I get it. But I still do not understand the updating form. The implementation looks more complexity then paper. Are they equal to each other?

[kobanium]

@CGLemon We need only following 3 parameters for updating gammas.

• $W_i$ : The number of winning count for feature $i$.
• $C_{ij}$ : Sum of features' gamma related to $\gamma_i$ (Match No. $j$).
• $E_j$ : Sum of all gammas (Match No. $j$).

In the current implementation, member variables of struct mm_t store

• w : The number of times this feature was selected. It is equal to the value of $\sum W$
• c : Temporary variable. It stores $C_{ij} \gamma_{i}$ not $C_{ij}$ for a turn.
• sigma : It is equal to the value of $\sum \frac{C}{E}$. It stores $\frac{C}{E}$ for all positions of training data.
• gamma : $\gamma$ value of this feature.

Therefore, updating rule of gamma $\gamma = \frac{W}{\sum \frac{C}{E}}$ is implemented as gamma = w / sigma, using struct mm_t member variables.

$\gamma$ must be normalized by 1 win and 1 lose for a opponent which has $\gamma = 1$. Implementation will be gamma = (w + 1) / (sigma + 2.0 / (1.0 + gamma)).

My implementation is the same as the updating formula described in Remi's peper, although it is a little difficult to understand how to obtain each parameter.

This is a little off the subject but I implemented training functions in time for the CGF open 2022. Comments and clarity of codes aren't enough, so I'm going to work on that as well.

[CGLemon]

Thanks for your help! Look like that it works. It was trained with square and diamond patterns (around 33000 patterns).

May I upload your paper to the cloud? I will write the log about MM algorithm. Your derivation is much clearly than Remi's. I hope that I may add the reference in the log, and to be sure that everybody may see the paper. Or you have already uploaded it. May you sent the URL to me? Thanks!

[kobanium]

I'm glad you can train patterns well. Here is my paper's link. http://id.nii.ac.jp/1438/00001972/ I'm a little glad someone gets my paper from this page, because we can see the stats on who accessed my paper.