English| 中文版

Dive into the heart of our technology with a hands-on demonstration. Simply initiate the process in your terminal:

$ python app.py

Alternatively, explore our space hosted on the Hugging Face platform:

🤗 Space

Engage directly with our algorithm in a few easy steps:

• Step 1. Select your desired parameters on the left side;
• Step 2. Click Execute Algorithm;
• Step 3. Eagerly await your customized results on the right. Experience our solutions at your fingertips.

• Quick Start
• 1. Introduction
• 2. NMF Variants
• 3. Noise Types
• 4. Setup and Execution
• 5. Convergence Trends
• 6. Results
  • 6.1. Metrics
    • 6.1.1. What are They?
    • 6.1.2. Why RMSE More Important?
  • 6.2. Performance on ORL and YaleB Datasets
  • 6.3. Reconstruction Effects
• 7. Project Structure
• 8. Updata Log & TODO List
• 9. Contribution

📌 Important Notice: Please ensure that dataset files are placed in the data directory before executing run.py. For emphasis, we've incorporated an error notification mechanism. Moreover, we've provided comprehensive docstrings and comments within our code. Should you have any questions, feel free to explore our source code in depth.

Please refrain from intentionally inputting unexpected data types to test our algorithms. We do not have initial input type assertions, so they cannot reject inappropriate inputs from the start. Thank you for your understanding.

1. Simplicity

To swiftly experience the method in action, simply configure and run the following in run.py:

from algorithm.pipeline import Pipeline

pipeline = Pipeline(nmf='L1NormRegularizedNMF', # Options: 'L2NormNMF', 'L1NormNMF', 'KLDivergenceNMF', 'ISDivergenceNMF', 'L21NormNMF', 'HSCostNMF', 'L1NormRegularizedNMF', 'CappedNormNMF', 'CauchyNMF'
                    dataset='YaleB', # Options: 'ORL', 'YaleB'
                    reduce=3, # ORL: 1, YaleB: 3
                    noise_type='salt_and_pepper', # Options: 'uniform', 'gaussian', 'laplacian', 'salt_and_pepper', 'block'
                    noise_level=0.08, # Uniform, Gassian, Laplacian: [.1, .3], Salt and Pepper: [.02, .10], Block: [10, 20]
                    random_state=99, # 0, 42, 99, 512, 3407 in our experiments
                    scaler='MinMax') # Options: 'MinMax', 'Standard'

# Run the pipeline
pipeline.run(max_iter=500, verbose=True) # Parameters: max_iter: int, convergence_trend: bool, matrix_size: bool, verbose: bool
pipeline.evaluate(idx=9, imshow=True) # Parameters: idx: int, imshow: bool

Our development framework empowers you to effortlessly create your own NMF algorithms with minimal Python scripting. Here's how you can get started:

import numpy as np
from algorithm.nmf import BasicNMF
from algorithm.pipeline import Pipeline

class ExampleNMF(BasicNMF):
    # To tailor a unique NMF algorithm, subclass BasicNMF and redefine matrix_init and update methods.
    def matrix_init(self, X, n_components, random_state=None):
        # Implement your initialization logic here.
        # Although we provide built-in methods, crafting a bespoke initialization can markedly boost performance.
        # D, R = <your_initialization_logic>
        # D, R = np.array(D), np.array(R)
        return D, R  # Ensure D, R are returned.

    def update(self, X, **kwargs):
        # Implement the logic for iterative updates here.
        # Modify self.D, self.R as per your algorithm's logic.
        # flag = <convergence_criterion>
        return flag  # Return True if converged, else False.

Test the initial performance of your algorithm seamlessly with our pipeline:

pipeline = Pipeline(nmf=ExampleNMF(),
                    dataset='YaleB',
                    reduce=3,
                    noise_type='salt_and_pepper',
                    noise_level=0.08,
                    random_state=99,
                    scaler='MinMax')

For a comprehensive assessment, conduct experiments across our datasets:

from algorithm.pipeline import Experiment

exp = Experiment()
# Once you build the data container
# You can choose an NMF algorithm and execute the experiment
exp.choose('L1NormRegularizedNMF')
# This step is very time-consuming, please be patient.
# If you achieve a better performance, congratulations! 
# You can share your results with us.
# Similarly, you can replace 'L1NormRegularizedNMF' with other your customized NMF algorithm
exp.execute()

Note: The Experiment function accepts either a string representing a built-in algorithm or a BasicNMF object, enabling you to directly evaluate your custom NMF algorithm.

2. Convenience

You are invited to try out our experiments on Google Colab. First, execute all the code snippets in the Setup section to access our repository. Also, all you need to do is upload the data.zip file. (You no longer need to upload the data.zip file.)

Once the experimental environment is set up, you have the choice to either run run.py in the terminal or adjust the default settings and then execute the script within the Jupyter notebook as you see fit.

For a more comprehensive setup and detailed execution instructions, please refer to the "Setup and Execution" section.

It is a matrix factorization technique where all the elements of the decomposed matrices are required to be non-negative. This kind of decomposition is especially suitable for datasets where all the elements are non-negative, such as image data or text data.

NMF aims to decipher the following formula:

$$X \approx D R$$

Figure 1. Illustration of NMF

Where, if $X$ is of size $m \times n$, typically $D$ would be of size $m \times k$ and $R$ would be of size $k \times n$, where $k$ is a predefined number of factors and is usually less than both $m$ and $n$.

NMF has found utility in many applications, including feature extraction, image processing, and text mining.

Our experiments seek to compare the robustness of various NMF variants.

Figure 2. Illustration of Our Experiments

• 2 Datasets: ORL, Cropped YaleB
• 8 NMFs: $L_2$ Norm Based, KL Divergence, IS Divergence, $L_{2, 1}$ Norm Based, Hypersurface Cost, $L_1$ Norm Regularized, Capped Norm Based, Cauchy
• 5 Noise Types: Uniform, Gaussian, Laplacian, Block Occlusion, Salt and Pepper

Note: GitHub itself does not support rendering LaTeX math formulas in Markdown previews, so some formulas may not display correctly. You might want to use other tools to view these formulas.

• $L_2$ Norm Based NMF

  • Cost Function: $\lVert X - DR \rVert^2 = \sum_{\substack{ijk}}(x_{ij} - d_{ik}r_{kj})^2$
  • Update Rule:
    $\mathbf{D} \leftarrow \mathbf{D} \times \frac{\mathbf{X} \mathbf{R^\top}}{\mathbf{D} \mathbf{R} \mathbf{R^\top}}\
    \mathbf{R} \leftarrow \mathbf{R} \times \frac{\mathbf{D^\top} \mathbf{X}}{\mathbf{D^\top} \mathbf{D} \mathbf{R}}$

• KL Divergence NMF

  • Cost Function:
    $d_{KL}(\mathbf{X} \lVert \mathbf{DR}) = \sum_{\substack{ijk}}(x_{ij}\mathrm{log}\frac{x_{ij}}{d_{ik}r_{kj}} - x_{ij} + d_{ik}r_{kj})$
  • Update Rule:
    $\mathbf{D} \leftarrow \mathbf{D} \times \frac{(\frac{\mathbf{X}}{\mathbf{DR}})\mathbf{R}^\top}{\mathbf{1}{m,n} \cdot \mathbf{R}^\top}\ \mathbf{R} \leftarrow \mathbf{R} \times \frac{\mathbf{D}^\top \left(\frac{\mathbf{X}}{\mathbf{DR}} \right)}{\mathbf{D}^\top \cdot \mathbf{1}{m,n}}$

• IS Divergence NMF

  • Cost Function:
    $d_{IS}(\mathbf{X} \lVert \mathbf{DR}) = \frac{\mathbf{X}}{\mathbf{DR}} - \mathrm{log}\frac{\mathbf{X}}{\mathbf{DR}} - 1$
  • Update Rule:
    $\mathbf{D} \leftarrow \mathbf{D} \times \frac{((\mathbf{DR}^{-2}) \mathbf{X})\mathbf{R}^\top}{(\mathbf{DR})^{-1} \mathbf{R}^\top}\ \mathbf{R} \leftarrow \mathbf{R} \times \frac{\mathbf{D}^\top ((\mathbf{DR})^{-2}\mathbf{X})}{\mathbf{D}^\top (\mathbf{DR})^{-1}}$

• $L_{2, 1}$ Norm Based NMF

  • Cost Function:
    $\lVert \mathbf{X - DR} \rVert_{2, 1} = \sum_{\substack{i=1}}^n \sqrt{\sum_{\substack{j=1}^p}(\mathbf{X} - \mathbf{DR}){ji}^2} = \sum{\substack{i=1}}^n \lVert x_i - \mathbf{D}r_i \rVert$
  • Update Rule:
    $D_{ji} \leftarrow D_{jk} \times \frac{(\mathbf{X \Lambda R^\top}){jk}}{(\mathbf{DR\Lambda R^\top})jk} \ R{ki} \leftarrow R{ki} \times \frac{(\mathbf{D^\top X\Lambda}){ki}}{(\mathbf{D^\top DR\Lambda}){jk}}\ $ where $\Lambda$ is a diagonal matrix with the diagonal elements given by,
    $D_{ii} = \frac{1}{\sqrt{\sum_{\substack{j=1}}^p(\mathbf{X - DR})_{ji}^2}} = \frac{1}{\lVert x_i - \mathbf{D}r_i \rVert}$

• Hypersurface Cost NMF

  • Cost Function: $\phi(\mathbf{D}, \mathbf{R}) = \frac{1}{2}(\sqrt{1 + \lVert \mathbf{X} - \mathbf{DR} \rVert^2} - 1)$
  • Update Rule:
    $\mathbf{D} \leftarrow \mathbf{D} - \alpha\frac{\mathbf{DRR}^{\top} - \mathbf{XR}^{\top}}{\sqrt{1 + \lVert \mathbf{X} - \mathbf{DR} \rVert}}\ \mathbf{R} \leftarrow \mathbf{R} - \beta \frac{\mathbf{D}^{\top}\mathbf{DR} - \mathbf{D}^{\top}\mathbf{X}}{\sqrt{1 + \lVert \mathbf{X} - \mathbf{DR} \rVert}}$

• $L_1$ Norm Regularized NMF

  • Cost Function: $\lVert \mathbf{X} - \mathbf{DR} - \mathbf{S}\rVert_F^2 + \lambda \lVert S \rVert_1$
  • Update Rule:
    $\mathbf{S} \leftarrow \mathbf{X} - \mathbf{DR}\ \mathbf{S}{ij} \leftarrow \begin{cases} \mathbf{S}{ij} - \frac{\lambda}{2} \text{ , if} \mathbf{S}{ij} > \frac{\lambda}{2} \ \mathbf{S}{ij} + \frac{\lambda}{2} \text{ , if} \mathbf{S}{ij} < \frac{\lambda}{2}\ 0 \text{ , otherwise} \end{cases}\ \mathbf{D} \leftarrow \frac{\left | (\mathbf{S} - \mathbf{X})\mathbf{R}^{\top}\right | - ((\mathbf{S} - \mathbf{X})\mathbf{R}^{\top}}{2\mathbf{DRR}^{\top}}\ \mathbf{R} \leftarrow \frac{\left |\mathbf{D}^{\top}(\mathbf{S} - \mathbf{X})\right | - (\mathbf{D}^{\top}(\mathbf{S} - \mathbf{X})}{2\mathbf{D^{\top}}\mathbf{DR}}\ \mathbf{D} \leftarrow \frac{\mathbf{D}}{\sqrt{\sum^n{k=1}\mathbf{D}{kj}^2}}\ \mathbf{R} \leftarrow \mathbf{R}\sqrt{\sum^n{k=1}\mathbf{D}_{kj}^2}$

• Capped Norm Based NMF

  • Update Rule:
    $\mathbf{D} \leftarrow \mathbf{D}\frac{\mathbf{XIR}^\top}{\mathbf{DRIR}^{\top}}\ \mathbf{R} \leftarrow \mathbf{R}\sqrt{\frac{\mathbf{IXD}}{\mathbf{IR}^{\top}\mathbf{RXD}}}\ \mathbf{I}_{jj} = \begin{cases} \frac{1}{2\lVert x_j - \mathbf{D}r_j\rVert_2}\text{ , if} \lVert x_j - \mathbf{D}r_j\rVert \leq \theta \ 0 \text{ , otherwise} \end{cases}$,
    where $\mathbf{I}$ is initialized as an identify mamtrix and then will be updated to a diagonal matrix.

• Cauchy NMF

  • Update Rule:
    $\theta \leftarrow \theta \cdot \frac{b_\theta}{a_\theta + \sqrt{a_\theta^2 + 2b_\theta \cdot a_\theta}}$
    For $\mathbf{D}$,
    $a_\theta = \frac{3}{4} \frac{\sigma}{\sigma^2 + \mathbf{X}} \mathbf{R}^\top\ b_\theta = \sigma^{-1}\mathbf{R}^\top$;
    For $\mathbf{R}$,
    $a_\theta = \frac{3}{4}\mathbf{D}^{\top}\frac{\sigma}{\sigma^2 + \mathbf{X}}\ b_\theta = \mathbf{D}^{\top}\sigma^{-1}$

• Uniform:

Figure 3. Uniform Noise

• Gaussian

Figure 4. Gaussian Noise

• Laplacian

Figure 5. Laplacian Noise

• Block Occlusion

Figure 6. Block Noise

• Salt and Pepper

Figure 7. Salt and Pepper Noise

If you're not concerned about package version conflicts, you may skip this step.

To avoid potential conflicts between package versions, we ensure smooth execution only under our specified package versions. We can't guarantee flawless operation across all versions of the related packages. However, if you have concerns or wish to ensure the highest compatibility, you can follow the steps below to create a new environment specifically for this experiment.

1. Create a New Conda Environment:

   First, you'll want to create a new Conda environment named NumPyNMF. To do this, open your terminal or command prompt and enter the following command:

   $ conda create --name NumPyNMF python=3.8

2. Activate the New Environment:

   Before installing any packages or running any scripts, you must activate the NumPyNMF environment. To do this, enter the following command:

   $ conda activate NumPyNMF

3. Install Required Packages:

   Navigate to the directory where the requirements.txt file is located and install the necessary packages using pip:

   $ pip install -r requirements.txt

4. Running the Experiment:

   After setting up the environment and installing the required packages, always ensure that the NumPyNMF environment is activated before executing any scripts.

Important: As mentioned, we've tailored this environment to avoid potential version conflicts, ensuring optimal compatibility with our codebase. Please use this environment to ensure accurate and conflict-free execution.

To run the current experiment, follow these steps:

1. Configure the Algorithm and Dataset: In run.py, we provide a Pipeline class. You can configure your experiment by adjusting its parameters. Here's an explanation of the Pipeline parameters:

   • nmf: Choose the desired Non-negative Matrix Factorization (NMF) algorithm. Options are: L2NormNMF, L1NormNMF, KLdivergenceNMF, ISdivergenceNMF, RobustNMF, HypersurfaceNMF, L1NormRegularizedNMF, CappedNormNMF, CauchyNMF.

   • dataset: Select the dataset. Options are: ORL, YaleB.

   • reduce: In our experiments, use 1 for ORL and 3 for YaleB. If the value is too small, the execution time will be excessive; if too large, it will result in information loss.

   • noise_type: The type of noise. Choices are: uniform, gaussian, laplacian, salt_and_pepper, block.

   • noise_level: The level of noise. The specific values vary depending on your choice of noise type.

   • random_state: The random seed value used in the experiment. In our experiments, we've used: 0, 42, 99, 512, 3407.

   • scaler: The method for data normalization. Choices are: MinMax, Standard.

2. Run the Pipeline:

   pipeline.run() 

   Optional parameters include: max_iter (maximum iterations), convergence_trend (display convergence trend), matrix_size (show matrix size or note), and verbose (show training procedure or not).

3. Evaluate the Results:

   pipeline.evaluate()

   Optional parameters are: idx (index), and imshow (display image or not).

After you've configured your experiment parameters in the run.py script, you can execute the experiment directly from the terminal. Follow these steps:

1. Navigate to the Directory:

   First, make sure you're in the directory where the run.py file is located. Use the cd command followed by the directory path to navigate. For example:

   $ cd path/to/your/directory/NumPyNMF

2. Execute the Script:

   Run the script using Python. Depending on your setup, you might use python, python3, or another variation. Here's the general command:

   $ python run.py

   If you're using Python 3 specifically and have both Python 2 and Python 3 installed, you might use:

   $ python3 run.py

Hope this helps you carry out the experiment smoothly!

• $L_1$ Norm Based NMF:

Figure 8. Convergence Trend of L1 Norm Based NMF

• $L_{2, 1}$ Norm Based NMF:

Figure 9. Convergence Trend of L2, 1 Norm Based NMF

• Root Means Square Errors (RMSE)
  $\mathrm{RMSE} = \sqrt{\frac{1}{N} \lVert \mathbf{X - DR} \rVert^2_F}$
• Average Accuracy
  $\mathrm{Acc(Y, Y_{pred})} = \frac{1}{n} \sum_{\substack{i}}^n {\mathrm{{Y_{(pred)(i)}}} = \mathrm{Y(i)}}$
• Normalized Mutual Information (NMI)
  $\mathrm{NMI(Y, Y_{pred})} = \frac{2 \times I(\mathrm{Y, Y_{pred}})}{H(\mathrm{Y}) + H(\mathrm{Y_{pred})}}$,
  where $I(\cdot, \cdot$) is the mutual information, $H(\cdot)$ is the entropy.

Figure 10. Greater RMSE, Average Accuracy and NMI

Figure 11. Less RMSE, Average Accuracy and NMI

As illustrated in Figure 10, the reconstructed image exhibits a higher level of granularity.

In our preliminary experiments, we observed that certain NMFs might not perform optimally on our specific datasets. This could be attributed to:

• The inherent characteristics of the datasets.
• Potential implementation errors (we leave this to future work).

We warmly welcome you to delve into our source code and contribute to its enhancement.

• Gaussian Noise Reconstruction

Figure 12. Gaussian Noise Reconstruction (Noise Level: 0.16)

• Laplacian Noise Reconstruction

Figure 13. Laplacian Noise Reconstruction (Noise Level: 0.1)

• Uniform Noise Reconstruction

Figure 14. Uniform Noise Reconstruction (Noise Level: 0.1)

• Block Occlusion Noise Reconstruction

Figure 15. Block Occlusion Noise Reconstruction (Block Size: 10)

Figure 16. Block Occlusion Noise Reconstruction (Block Size: 20)

• Salt and Pepper Noise Reconstruction

Figure 17. Salt and Pepper Noise Reconstruction (Noise Level: 0.1)

├── NumPyNMF/
│   ├── algorithm/
│   │   ├── __init__.py
│   │   ├── datasets.py
│   │   ├── nmf.py
│   │   ├── pipeline.py
│   │   ├── preprocess.py
│   │   ├── sample.py
│   │   ├── trainer.py
│   │   ├── user_evaluate.py
│   │   └── visualize.py
│   └── data/
│       ├── CroppedYaleB/
│       └── ORL/
├── figures/*.png
├── .gitignore
├── LICENSE
├── README.md
├── README.zh-CN.md
├── requirements.txt
├── run.ipynb
└── run.py

• 2023-10-20
  • TODO List:
    • NumPy memory preallocation ❌ (Conflicts with readability)
    • Reasons for algorithmic non-functionality (Done: 2023-11-24)
    • GUI interface (Done: 2024-02-01)
• 2023-11-10
  • Update Log:
    • Enhanced algorithm.NMF module
    • Fixed non-functionality of several algorithms
• 2023-11-24
  • Update Log:
    • Deprecated some modules and decoupled algorithm.nmf, which makes it flexible for users to transfer on other tasks
    • Integrated the basic functions in the deprecated modules into BasicNMF
• 2024-02-01
  • Update Log:
    • Released user interface scripts.
    • Introduced advanced techniques.
    • Streamlined processes in a step-by-step manner
• 2024-02-07
  • Update log:
    • Constructed experiments utilizing multiprocessing techniques, which have resulted in significant acceleration
    • Added log recordings during experiments

We welcome contributions of any kind, whether it's suggesting new features, reporting bugs, or helping with code optimizations. Here are the steps to get started:

• Fork this repository by clicking the "Fork" button on the top right corner of this page.

git clone https://github.com/YOUR_USERNAME/PROJECT_NAME.git

Then navigate to the project directory:

cd PROJECT_NAME

• Name your branch based on the change you're implementing, e.g., feature/new-feature or bugfix/issue-name:

git checkout -b branch-name

• Make your changes on this branch and then commit them.

  git add .
  git commit -m "Describe your changes here"

git push origin branch-name

• Go back to your fork on GitHub, and click "New Pull Request". Choose the branch you just pushed and submit the pull request.

• The maintainers of the project will review your pull request. They might request some changes or merge it.