<p dir="auto">NMF in scikit-learn overview :</p>
<p dir="auto"><strong>Current implementation (<a href="https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/decomposition/nmf.py">code</a>):</strong><br>
- loss = squared (aka Frobenius norm)<br>
- method = projected gradient<br>
- regularization = trick to enforce sparseness or low error with beta / eta</p>
<p dir="auto"><strong><a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="8247053" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/1348" data-hovercard-type="pull_request" data-hovercard-url="/scikit-learn/scikit-learn/pull/1348/hovercard" href="https://github.com/scikit-learn/scikit-learn/pull/1348">#1348</a> (or in <a href="https://gist.github.com/omangin/8801846">gist</a>):</strong><br>
- loss = (generalized) Kullback-Leibler divergence (aka I-divergence)<br>
- method = multiplicative update<br>
- regularization = None</p>
<p dir="auto"><strong><a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="21288191" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/2540" data-hovercard-type="pull_request" data-hovercard-url="/scikit-learn/scikit-learn/pull/2540/hovercard" href="https://github.com/scikit-learn/scikit-learn/pull/2540">#2540</a> [WIP]:</strong><br>
- loss = squared (aka Frobenius norm)<br>
- method = multiplicative update<br>
- regularization = None</p>
<p dir="auto"><strong><a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="4966330" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/896" data-hovercard-type="issue" data-hovercard-url="/scikit-learn/scikit-learn/issues/896/hovercard" href="https://github.com/scikit-learn/scikit-learn/issues/896">#896</a> (or in <a href="https://gist.github.com/mblondel/09648344984565f9477a">gist</a>):</strong><br>
- loss = squared (aka Frobenius norm)<br>
- method = coordinate descent, no greedy selection<br>
- regularization = L1 or L2</p>
<p dir="auto"><strong>Papers describing the methods:</strong><br>
- <a href="http://www.researchgate.net/profile/Daniel_Lee27/publication/2538030_Algorithms_for_Non-negative_Matrix_Factorization/links/0fcfd50aab9a59c112000000.pdf" rel="nofollow">Multiplicative update</a><br>
- <a href="http://www.csie.ntu.edu.tw/~cjlin/papers/pgradnmf.pdf" rel="nofollow">Projected gradient</a><br>
- <a href="http://www.cs.utexas.edu/~cjhsieh/nmf_kdd11.pdf" rel="nofollow">Coordinate descent with greedy selection</a></p>
<hr>
<p dir="auto"><strong>About the uniqueness of the results</strong><br>
The problem is non-convex, and there is no unique minimum:<br>
Different losses, different initializations, and/or different optimization methods generally give different results !</p>
<p dir="auto"><strong>About the methods</strong></p>
<ul dir="auto">
<li>The multiplicative update (MU) is the most widely used because of it's simplicity. It is very easy to adapt it to squared loss, (generalized) Kullback-Leibler divergence or Itakura–Saito divergence, which are 3 specific cases of the so-called beta-divergence. All three losses seem used in practice. A regularization L1 or L2 can easily be added.</li>
<li>The Projected gradient (PG) seems very efficient for the squared loss, but does not scale well (w.r.t X size) for the (generalized) KL divergence. A L1 or L2 regularization could possibly be added in the gradient step. I don't know where the sparseness enforcement trick in current code comes from.</li>
<li>The Coordinate Descent (CD) seems even more efficient for squared loss, and we can add easily L1 or L2 regularization. It can be further speeded up by a greedy selection of coordinate. The adaptation for KL divergence is possible with a Newton method for solving subproblem (slower), but without greedy selection. This adaptation is supposed to be faster than MU-NMF with (generalized) KL divergence.</li>
</ul>
<p dir="auto"><strong>About the initialization</strong><br>
Different schemes exist, and can change significantly both result and speed. They can be used independantly for each NMF method.</p>
<p dir="auto"><strong>About the stopping condition</strong><br>
Actual stopping condition in PG-NMF is bugged (<a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="21766182" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/2557" data-hovercard-type="pull_request" data-hovercard-url="/scikit-learn/scikit-learn/pull/2557/hovercard" href="https://github.com/scikit-learn/scikit-learn/pull/2557">#2557</a>), and leads to poor minima when the tolerance is not low enough, especially in the random initialization scheme. It is also completely different from stopping condition in MU-NMF, which is very difficult to set. Talking with audio scientists (who use a lot MU-NMF for source seperation) reveals that they just set a number of iteration.</p>
<hr>
<p dir="auto">As far as I understand NMF, as there is no unique minimum, there is no perfect loss/method/initialization/regularization. A good choice for some dataset can be terrible for another one. I don't know how many methods we want to maintain in scikit-learn, and how much we want to guide users with few possibilities, but several methods seems more useful than only one.</p>
<p dir="auto">I have tested MU-NMF, PG-NMF and CD-NMF from scikit-learn code, <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="21288191" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/2540" data-hovercard-type="pull_request" data-hovercard-url="/scikit-learn/scikit-learn/pull/2540/hovercard" href="https://github.com/scikit-learn/scikit-learn/pull/2540">#2540</a> and <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="4966330" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/896" data-hovercard-type="issue" data-hovercard-url="/scikit-learn/scikit-learn/issues/896/hovercard" href="https://github.com/scikit-learn/scikit-learn/issues/896">#896</a>, with squared loss and no regularization, on a subsample of 20news dataset, and performances are already very different depending on the initialization (see below).</p>
<p dir="auto"><strong>Which methods do we want in scikit-learn?</strong><br>
Why do we have stopped <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="8247053" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/1348" data-hovercard-type="pull_request" data-hovercard-url="/scikit-learn/scikit-learn/pull/1348/hovercard" href="https://github.com/scikit-learn/scikit-learn/pull/1348">#1348</a> or <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="4966330" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/896" data-hovercard-type="issue" data-hovercard-url="/scikit-learn/scikit-learn/issues/896/hovercard" href="https://github.com/scikit-learn/scikit-learn/issues/896">#896</a> ?<br>
Do we want to continue <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="21288191" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/2540" data-hovercard-type="pull_request" data-hovercard-url="/scikit-learn/scikit-learn/pull/2540/hovercard" href="https://github.com/scikit-learn/scikit-learn/pull/2540">#2540</a> ?<br>
I can work on it as soon as we have decided.</p>
<hr>
<p dir="auto">NNDSVD (similar curves than NNDSVRAR)<br>
<a target="_blank" rel="noopener noreferrer nofollow" href="https://cloud.githubusercontent.com/assets/11065596/7963015/ece155b2-0a10-11e5-83c4-53d1257c4f13.png"><img src="https://cloud.githubusercontent.com/assets/11065596/7963015/ece155b2-0a10-11e5-83c4-53d1257c4f13.png" alt="nndsvd" style="max-width: 100%;"></a><br>
NNDSVDA<br>
<a target="_blank" rel="noopener noreferrer nofollow" href="https://cloud.githubusercontent.com/assets/11065596/7963016/ece399f8-0a10-11e5-99c3-a5999925ff15.png"><img src="https://cloud.githubusercontent.com/assets/11065596/7963016/ece399f8-0a10-11e5-99c3-a5999925ff15.png" alt="nndsvda" style="max-width: 100%;"></a><br>
Random run 1<br>
<a target="_blank" rel="noopener noreferrer nofollow" href="https://cloud.githubusercontent.com/assets/11065596/7963017/ece391f6-0a10-11e5-9daf-f6311e46b02b.png"><img src="https://cloud.githubusercontent.com/assets/11065596/7963017/ece391f6-0a10-11e5-9daf-f6311e46b02b.png" alt="random_2" style="max-width: 100%;"></a><br>
Random run 2<br>
<a target="_blank" rel="noopener noreferrer nofollow" href="https://cloud.githubusercontent.com/assets/11065596/7963018/ece405c8-0a10-11e5-8567-472caea08368.png"><img src="https://cloud.githubusercontent.com/assets/11065596/7963018/ece405c8-0a10-11e5-8567-472caea08368.png" alt="random_3" style="max-width: 100%;"></a><br>
Random run 3<br>
<a target="_blank" rel="noopener noreferrer nofollow" href="https://cloud.githubusercontent.com/assets/11065596/7963014/ece0f9be-0a10-11e5-8537-af7ee9e75ad3.png"><img src="https://cloud.githubusercontent.com/assets/11065596/7963014/ece0f9be-0a10-11e5-8537-af7ee9e75ad3.png" alt="random_4" style="max-width: 100%;"></a></p>
<p dir="auto">We should fix the remaining sphinx warnings here:<br>
<a href="https://circleci.com/gh/scikit-learn/scikit-learn/1629" rel="nofollow">https://circleci.com/gh/scikit-learn/scikit-learn/1629</a></p>
<p dir="auto">and then make circle IO error if there are any warnings (grep'ing for <code class="notranslate">WARNINGS</code> I guess?).</p>
<p dir="auto">This way we immediately see if someone broke anything in the docs.</p>