Towards a Fairer Non-negative Matrix Factorization

This paper proposes a min-max formulation for Non-negative Matrix Factorization (NMF) to mitigate group bias, deriving specific optimization algorithms and demonstrating through experiments that while this approach can improve fairness, it may increase individual error, necessitating application-specific trade-off considerations.

The Gist

Imagine you are a chef trying to create the perfect "Signature Dish" for a massive, diverse community. This dish needs to be made from a giant pot of ingredients (the data) that represents everyone: children, adults, seniors, people from different cultures, and people with different dietary needs.

The Problem: The "Average" Taste
In the world of machine learning, a popular tool called Non-negative Matrix Factorization (NMF) is like a chef who tries to break this giant pot of ingredients down into a few basic "flavor profiles" (topics or features) to understand the whole meal.

The standard way this chef works is by trying to make the average person happy. They taste the whole pot and adjust the recipe until the overall flavor is good.

• The Catch: If 90% of the people in the community love spicy food, and 10% love mild food, the chef will make the dish very spicy. The 90% are happy, but the 10% are left with a dish that is too hot to eat.
• In math terms, the "spicy" group (the majority) gets a low "reconstruction error" (they are well represented), while the "mild" group (the minority) gets a high error (they are poorly represented). The math ignores the minority because their voices are drowned out by the majority.

The Solution: The "Fairer" Chef
This paper introduces a new way of cooking called Fairer-NMF. Instead of trying to please the average person, this new chef uses a "Min-Max" strategy.

Think of it like this: The chef looks at the person who is most unhappy with the current recipe (the group with the worst flavor) and asks, "How can I change the recipe to make you happier, even if it means the others are slightly less happy than before?"

The goal isn't to make everyone perfectly happy (which might be impossible), but to ensure that no single group is left starving. The chef tries to minimize the maximum amount of unhappiness across all groups.

How They Do It (The Kitchen Tools)
The authors propose two new "kitchen tools" (algorithms) to help this chef cook:

1. The Alternating Minimization (AM) Method: This is like a slow, meticulous chef who tastes the dish, adjusts one spice, tastes again, adjusts another, and repeats. It's very precise and finds a great balance, but it takes a long time and requires a lot of computing power (like using a supercomputer to chop an onion).
2. The Multiplicative Updates (MU) Method: This is like a faster, more intuitive chef. They make quick, multiplicative adjustments (scaling flavors up or down) based on who is currently the most unhappy. It's much faster and gets the job done in seconds, though it might not be quite as perfectly balanced as the slow method.

The Trade-Off (The "Fairness Tax")
The paper makes a very honest admission: Fairness has a cost.
Sometimes, to make the minority group happy, you have to slightly upset the majority.

• Analogy: Imagine a school bus. If the bus is designed for tall people, short people can't see out the windows. If you lower the ceiling so short people can see, the tall people might have to duck.
• In the paper's experiments, they found that sometimes, making the "Fairer" model meant that the majority group's data was slightly less accurate than before. However, the authors argue this is a necessary trade-off to prevent the minority group from being completely ignored or misclassified.

Real-World Examples
The authors tested this on real data:

• Heart Disease Data: They looked at patient data split by gender. The standard method accidentally favored one gender, making predictions for the other gender less accurate. The "Fairer" method balanced the accuracy so both genders were treated equally well.
• News Articles: They analyzed news topics. The standard method ignored smaller topics (like "Sales" or "Recreation") because they had fewer articles than big topics like "Politics." The "Fairer" method ensured that even the small topics were represented accurately in the final summary.

The Bottom Line
This paper doesn't promise a "perfectly fair" world. It admits that fairness is complicated and depends on what you are trying to achieve. However, it provides a practical toolkit for data scientists to stop blindly optimizing for the "average" and start paying attention to the groups that get left behind.

It's a shift from asking, "What works best for most people?" to asking, "Who is suffering the most, and how can we fix that first?"

Technical Summary

Here is a detailed technical summary of the paper "Towards a Fairer Non-negative Matrix Factorization".

1. Problem Statement

Non-negative Matrix Factorization (NMF) is a widely used unsupervised learning technique for dimensionality reduction, topic modeling, and feature extraction. It decomposes a non-negative data matrix $X$ into two lower-rank non-negative matrices, $W$ (representation) and $H$ (dictionary), such that $X \approx WH$.

The standard NMF objective minimizes the average reconstruction error (typically the Frobenius norm $\|X - WH\|_F^2$) across the entire dataset. The authors argue that this "average-case" optimization leads to unfair outcomes in scenarios with imbalanced data:

• Group Imbalance: Large or complex groups dominate the optimization, causing small or complex minority groups to suffer high reconstruction errors.
• Complexity Imbalance: Groups with higher intrinsic rank (complexity) are often poorly represented if the target rank $r$ is fixed, as the algorithm prioritizes minimizing the total error, often at the expense of the more complex group.
• Consequence: In downstream tasks (e.g., medical diagnosis, criminal justice), this results in models that perform well for the majority but fail for underrepresented or complex subgroups, propagating bias.

2. Methodology: Fairer-NMF

The authors propose Fairer-NMF, a modification of the standard NMF objective function based on a min-max fairness framework, inspired by "Fair PCA" (Samadi et al., 2018).

2.1 Objective Function

Instead of minimizing the sum of errors, Fairer-NMF seeks to minimize the maximum relative reconstruction loss across $L$ distinct population groups.

1. Relative Reconstruction Loss: For a group $\ell$ with data matrix $X_\ell$, the loss is defined as:
   $$\text{Loss}_\ell = \frac{\|X_\ell - W_\ell H\| - E_\ell}{\|X_\ell\|}$$
   Where:

   • $\|X_\ell - W_\ell H\|$ is the reconstruction error of group $\ell$ using the global dictionary $H$.
   • $E_\ell$ is a baseline error representing the "optimal" error achievable if the group were modeled in isolation (estimated via randomized standard NMF on $X_\ell$).
   • $\|X_\ell\|$ is the Frobenius norm, normalizing for group size and magnitude.

2. The Optimization Problem:
   $$\min_{W, H \geq 0} \max_{\ell \in \{1, \dots, L\}} \left( \frac{\|X_\ell - W_\ell H\| - E_\ell}{\|X_\ell\|} \right)$$
   The goal is to find a common dictionary $H$ that minimizes the worst-case deviation from the group-specific optimal performance.

2.2 Algorithms

The authors derive two algorithms to solve this non-convex, constrained optimization problem:

• Alternating Minimization (AM) Scheme:

  • Iteratively updates $H$ and $W$.
  • Update $H$: Solves a Second-Order Cone Program (SOCP) to minimize the maximum loss.
  • Update $W$: Solves a Non-Negative Least Squares (NNLS) problem (equivalent to standard NMF update for fixed $H$).
  • Pros: Theoretically guarantees non-increasing loss; finds high-quality solutions.
  • Cons: Computationally expensive due to SOCP solving.

• Multiplicative Updates (MU) Scheme:

  • Adapts the classic Lee & Seung multiplicative updates.
  • Introduces a weighting vector $c$ (initially 0) that tracks the group with the maximum loss.
  • Constructs weighted block matrices $\tilde{X}$ and $\tilde{W}$ based on the current worst-performing group.
  • Performs standard multiplicative updates on these weighted matrices.
  • Pros: Extremely fast; only requires matrix multiplications; no hyperparameters for step size (uses a specific decay rule for weights).
  • Cons: Slightly less consistent in convergence compared to AM on synthetic data, though performs well on real data.

3. Key Contributions

1. Formulation: Introduced a min-max fairness objective for NMF that explicitly accounts for group size and intrinsic complexity (via the $E_\ell$ baseline).
2. Algorithms: Derived two practical algorithms (AM and MU) to solve the Fairer-NMF problem, handling the non-negativity constraints and the min-max structure.
3. Empirical Analysis: Demonstrated through synthetic and real-world experiments that standard NMF often sacrifices minority groups, while Fairer-NMF significantly reduces disparity in reconstruction errors.
4. Critical Insight: Highlighted that "fairness" is context-dependent. While Fairer-NMF improves equity, it may increase the absolute error for some individuals (the "price of fairness"), necessitating careful application-specific evaluation.

4. Experimental Results

The authors evaluated the methods on synthetic data and three real-world datasets: Heart Disease (medical), 20Newsgroups (text), and synthetic benchmarks.

• Synthetic Data (Different Ranks): Standard NMF minimized total error by perfectly reconstructing the low-rank group while failing the high-rank group. Fairer-NMF successfully balanced the errors, ensuring the high-rank group was not ignored, though it slightly increased the error for the low-rank group.
• Synthetic Data (Overlapping Subspaces): Standard NMF favored groups sharing a subspace, leaving the orthogonal group with high error. Fairer-NMF equalized the loss across all groups.
• Heart Disease Dataset: Standard NMF favored the female group (larger sample size) over the male group. Fairer-NMF achieved comparable reconstruction losses for both sexes, though it occasionally resulted in negative loss (indicating the joint model was better than the isolated model for specific groups).
• 20Newsgroups Dataset: Standard NMF produced high variance in error across the 6 topic groups. Fairer-NMF reduced this variance, making the reconstruction error consistent across all topics.
• Algorithm Comparison:
  • Accuracy: Both AM and MU achieved similar fairness outcomes on real-world data. AM was slightly more consistent on synthetic data.
  • Efficiency: MU was orders of magnitude faster. On the 20Newsgroups dataset, AM took over an hour, while MU converged in under 129 seconds.

5. Significance and Discussion

• Transparency: The work provides a mathematically rigorous way to incorporate fairness into a foundational ML tool (NMF) used for interpretability.
• Trade-offs: The paper emphasizes that fairness is not a rigid definition. Improving fairness for a group may increase error for others. The authors argue that practitioners must weigh the "price of fairness" (increased error for some) against the benefit of reduced disparity.
• Practicality: By providing the MU algorithm, the authors offer a scalable solution that can be integrated into existing pipelines without prohibitive computational costs.
• Future Directions: The authors note that the assumption of known subgroups is a limitation. Future work could involve learning subgroups dynamically (e.g., via clustering on reconstruction errors) or exploring different fairness criteria.

In conclusion, Fairer-NMF offers a practical, algorithmic approach to mitigating bias in unsupervised learning, ensuring that dimensionality reduction and topic modeling do not systematically disadvantage smaller or more complex population subgroups.