This is an article that I tried to reimplement and confirm the non-negative matrix factorization (NMF) that I understood about a year ago. Support Vector Machine (SVM) and recently Deep Learning are popular, but I would like to introduce that there is also such a method ... I implemented it in C ++ and Python 2.7 for the first time in a while.
[Updated on 2020/02/05]
I created a mock for real-time sound source separation using NMF. Here
[Updated on March 23, 2018]
Some texts have been revised. In addition, I implemented it in Julia, so I posted the link there.
Mac OS X 10.11.6 Elcapitan
Python 2.7.11 (I have to upgrade to 3 system soon ...)
numpy 1.11.1
cmake 3.6.2
NMF is an algorithm that approximates the nonnegative (> = 0) matrix V by the product of the other two nonnegative matrices W and H. This algorithm itself is used as a feature extraction, natural language processing, and clustering method.
Also, due to its non-negative value, there is also one that uses the power spectrum in acoustic signal processing, and it is also used to find the pronunciation time of the timbre of a specific musical instrument from the spectrogram.
The NMF formula for the matrix under i * j is
k \in R \\
V \approx WH\\
V \in R^{i \times j}\\
W \in R^{i \times k} \qquad H \in R^{k \times j}
It becomes.
Since the contents of the input matrix V are known, but the contents of W and H are unknown, NMF minimizes the distance between V and WH.
A well-known (and simple) algorithm in NMF is the multiplicative update algorithm. As mentioned above, we must define the distance (error) between X and WH and minimize it. There are three types of distances used in NMF that I know of.
D_{EUC}(V, WH) = (V-WH)^2
D_{KL}(V, WH) = V log \frac{V}{WH} - V + WH
https://en.wikipedia.org/wiki/Itakura–Saito_distance
D_{IS}(V,WH) = \frac{V}{WH} - log \frac{V}{WH} -1
There is also β divergence, which expresses these three distance functions. Use these algorithms as multiplicative update algorithms. Derivation and transformation of detailed expressions are omitted.
The update formula after transformation is
H_{n+1} \gets H_{n} \frac{W^{T}_{n}V_{n}}{W^{T}_{n}W_{n}H_{n}}, \qquad W_{n+1} \gets W_{n} \frac{V_{n}H^{T}_{n+1}}{W_{n}H_{n+1}H^{T}_{n+1}}
H_{n+1} \gets H_{n} \frac{W^{T}_{n}\frac{V_{n}}{W_{n}H_{n}}}{W^{T}_{n}}, \qquad W_{n+1} \gets W_{n} \frac{\frac{V_{n}}{W_{n}H_{n+1}}H^{T}_{n+1}}{H^{T}_{n+1}}
H_{n+1} \gets H_{n} \sqrt{\frac{\frac{W_{n}}{W_{n}H_{n}}^{T}\frac{V_{n}}{W_{n}H_{n}}}{\frac{W_{n}}{W_{n}H_{n}}^{T}}}, \qquad W_{n+1} \gets W_{n} \sqrt{\frac{\frac{V_{n}}{W_{n}H_{n+1}}\frac{H_{n+1}}{W_{n}H_{n+1}}^{T}}{\frac{H_{n+1}}{W_{n}H_{n+1}}^{T}}}
I wondered if it was like this ... (I remember a little bit. I'm sorry if I made a mistake) What you have to be careful about is that H in the formula is {n + 1}! If you forget this, you will end up in a situation where it does not converge at all. By repeating this, the distance between V and WH will be reduced. ..
Reference materials / URL
http://papers.nips.cc/paper/1861-algorithms-for-non-negative-matrix-factorization.pdf http://www.mitpressjournals.org/doi/pdf/10.1162/neco.2008.04-08-771
NMF.py
# coding:utf-8
import numpy as np
class NMF():
"""
A class that does simple NMF
"""
def setParam(self, k, row, column):
"""
:param k
:param row:Column
:param column:line
:return:
"""
self.__k = k
self.__row = row
self.__column = column
self.__dictionary = np.random.random_sample([self.__row, self.__k])
self.__activation = np.random.random_sample([self.__k, self.__column])
def setDictionary(self, index, data):
"""
If there is a template, set the template (default is random number)
:param index:Index of which template(0 <= index < k)
:param data:Template data
:return:
"""
if index >= self.__k and len(data) != self.__row:
print "Please NMF.setParam(k,row,column)"
print "k = " + str(self.__k)
print "row = " + str(self.__row)
return
self.__dictionary[:, index] = np.array(data[:self.__row], np.float32)
def setAnalyzData(self, data, k):
"""
Call this method at the very beginning
:param data:Data to decompose
:param k
:return:
"""
if len(np.shape(data)) == 1:
self.__data = np.ones([np.shape(data)[0], 1], np.float32)
self.setParam(k, np.shape(data)[0], 1)
else:
self.__data = data
self.setParam(k, np.shape(data)[0], np.shape(data)[1])
def separate_euc_with_template(self,iter=200):
"""
Performs separation processing of EUC specifications with templates
:param iter:
:return:
"""
counter = 0
while counter < iter:
approx = np.dot(self.__dictionary , self.__activation)
wh = np.dot(np.transpose(self.__dictionary) , self.__data)
wt = np.dot(np.transpose(self.__dictionary) , approx)
bias = wh/wt
bias[np.isnan(bias)] = 0
self.__activation = self.__activation * bias
counter += 1
return self.__dictionary,self.__activation
def separate_euc_without_template(self,iter=200):
"""
Separation of EUC specifications without template
:param iter:
:return:
"""
counter = 0
while counter < iter:
approx = np.dot(self.__dictionary , self.__activation)
wh = np.dot(np.transpose(self.__dictionary) , self.__data)
wt = np.dot(np.transpose(self.__dictionary) , approx)
bias = wh/wt
bias[np.isnan(bias)] = 0
self.__activation = self.__activation * bias
approx = np.dot(self.__dictionary,self.__activation)
wh = np.dot(self.__data,np.transpose(self.__activation))
wt = np.dot(approx,np.transpose(self.__activation))
bias = wh/wt
bias[np.isnan(bias)] = 0
self.__dictionary = self.__dictionary * bias
counter += 1
return self.__dictionary,self.__activation
The class that executes NMF itself is implemented this time like this. Due to the problem of sentence volume, only the EUC specifications are listed this time. The code is quite troublesome, but if you don't mind ...
I also made a test code (including how to use it), so I ran it.
main.py
#coding:utf-8
import numpy as np
"""
It's a hassle, but I have to import these two
"""
from NMF import NMF
"""
Test script
How to use
"""
if __name__ == "__main__":
"""
Basically a troublesome constructor,row,You don't have to pass the column
I just made it properly ...
"""
nmf = NMF()
"""
After creating the constructor, call it first!
Where k,row,Since the column is set, setDictionary will not work unless this is called!
"""
nmf.setAnalyzData([[1,2,3,4],[2,3,4,5]],k=3)
"""
Set the template here
"""
nmf.setDictionary(0,[0.0,2.0])
nmf.setDictionary(1,[1.0,6.0])
nmf.setDictionary(2,[11.0,10.0])
"""
Start NMF
Pass the algorithm and the number of iterative updates as arguments
"""
dic,act = nmf.separate_euc_with_template(iter=200)
# dic,act = nmf.separate_euc_without_template(iter=200)
"""
Result display
"""
print "=========================== Dictionary ==========================="
print dic
print "=========================== Activation ==========================="
print act
"""
Check if it can be disassembled properly
"""
print "=========================== Approx ==========================="
print np.dot(dic,act)
In this test
V = \begin{pmatrix}
1 & 2 & 3 & 4\\
2 & 3 & 4 & 5
\end{pmatrix}
\qquad k=3
NMF is performed on a matrix with such conditions. For this matrix, the dictionary matrix set by setDictionary ()
W = \begin{pmatrix}
0 & 1 & 11 \\
2 & 6 & 10
\end{pmatrix}
Update the excitation matrix using.
When you run the main.py script ...
$ python main.py
=========================== Dictionary ===========================
[[ 0. 1. 11.]
[ 2. 6. 10.]]
=========================== Activation ===========================
[[ 0.11776982 0.05902263 0.00976704 0.33375605]
[ 0.168019 0.20895539 0.24616295 0.1367387 ]
[ 0.07563464 0.16282224 0.25034882 0.35120557]]
=========================== Approx ===========================
[[ 1. 2. 3. 4.]
[ 2. 3. 4. 5.]]
Properly, the excitation matrix was updated so that the distance between V and WH became 0.
I omitted this time, including the KL / IS version, which is available on GitHub. In addition, the C ++ version source code (the structure is almost the same as the Python version), which is omitted this time, is also released. Click here for Python version (https://github.com/T-Sumida/Simple_NMF) Click here for C ++ version (https://github.com/T-Sumida/NMF_for_cpp) Julia version is here
It was a good review to write sentences and mathematical formulas after a long time of studying about a year ago.
As I wrote at the beginning, DNN etc. are attracting attention these days, but there is also such a simple algorithm! I hope it will be an introduction.
Next time, I would like to introduce a practical example using this.
Recommended Posts