Fast Rank-1 NMF for Missing Data with KL Divergence
Kazu Ghalamkari1,2,Mahito Sugiyama1,2

1 : The Graduate University for Advanced Studies, SOKENDAI
2 : National Institute of Informatics
github.com/gkazunii/A1GM

The 25th International Conference on Artificial Intelligence and Statistics (AISTATS 2022) 1

Contributions□ Closed formula of the best rank-1 NMMF w.r.t. minimizing KL divergence2

Contributions□ Closed formula of the best rank-1 NMMF w.r.t. minimizing KL divergence□ A1GM: Faster method for rank-1 NMF with missing values
Non-gradient-based method.
No worries aboutinitial values, stopping criterion and learning rate 😄
3

Closed formula of the best rank-1 NMMF

Theorem 1.

4Modeling of NMMF
□ Introduce partial order structure in the input of NMMF

5

Modeling of NMMF
□ Each node has θ- and η-parameters6Modeling of NMMF
□ Each node has θ- and η-parameters7Modeling of NMMF
□ Each node has θ- and η-parameters8Modeling of NMMF
□ Example for.

9

Modeling of NMMF
□ Example for.

Möbius inversion formula10

Modeling of NMMF
□ Example for.

Möbius inversion formula11

Information geometry of rank-1 NMMF
□ Introducing θ- and η-coordinate

OneTo
One

12

Information geometry of rank-1 NMMF
𝑿, 𝒀, 𝒁 is simultaneously rank-1 decomposable. ⇔ It can be written as 𝒘 ⊗ 𝒉, 𝒂 ⊗ 𝒉, 𝒘 ⊗ 𝒃 .
One-body parameterTwo-body parameter13

Information geometry of rank-1 NMMF
𝑿, 𝒀, 𝒁 is simultaneously rank-1 decomposable. ⇔ It can be written as 𝒘 ⊗ 𝒉, 𝒂 ⊗ 𝒉, 𝒘 ⊗ 𝒃 .
One-body parameterTwo-body parameter

Simultaneous Rank-1 𝜽-condition
Its all two-body 𝜃-parameters are 0.

14

Information geometry of rank-1 NMMF
𝑿, 𝒀, 𝒁 is simultaneously rank-1 decomposable. ⇔ It can be written as 𝒘 ⊗ 𝒉, 𝒂 ⊗ 𝒉, 𝒘 ⊗ 𝒃 .
One-body parameterTwo-body parameter

Simultaneous Rank-1 𝜽-condition
Its all two-body 𝜃-parameters are 0.

Simultaneous Rank-1 𝜼-condition

𝜂𝑖𝑗 = 𝜂𝑖1 𝜂1𝑗15

Information geometry of rank-1 NMMF
𝑿, 𝒀, 𝒁 is simultaneously rank-1 decomposable. ⇔ It can be written as 𝒘 ⊗ 𝒉, 𝒂 ⊗ 𝒉, 𝒘 ⊗ 𝒃 .
One-body parameterTwo-body parameter

Simultaneous Rank-1 𝜽-condition
Its all two-body 𝜃-parameters are 0.

Simultaneous Rank-1 𝜼-condition

𝜂𝑖𝑗 = 𝜂𝑖1 𝜂1𝑗

16

Information geometry of rank-1 NMMF
𝑿, 𝒀, 𝒁 is simultaneously rank-1 decomposable. ⇔ It can be written as 𝒘 ⊗ 𝒉, 𝒂 ⊗ 𝒉, 𝒘 ⊗ 𝒃 .
One-body parameterTwo-body parameter

Simultaneous Rank-1 𝜽-condition
Its all two-body 𝜃-parameters are 0.

Simultaneous Rank-1 𝜼-condition

𝜂𝑖𝑗 = 𝜂𝑖1 𝜂1𝑗One-body 𝜼-parameters do not change before or after the projection.
17

Information geometry of rank-1 NMMF
𝑿, 𝒀, 𝒁 is simultaneously rank-1 decomposable. ⇔ It can be written as 𝒘 ⊗ 𝒉, 𝒂 ⊗ 𝒉, 𝒘 ⊗ 𝒃 .
One-body parameterTwo-body parameter

Simultaneous Rank-1 𝜽-condition
Its all two-body 𝜃-parameters are 0.

Simultaneous Rank-1 𝜼-condition

𝜂𝑖𝑗 = 𝜂𝑖1 𝜂1𝑗All 𝜼-parameters after the projection are identified.
18

Information geometry of rank-1 NMMF
𝑿, 𝒀, 𝒁 is simultaneously rank-1 decomposable. ⇔ It can be written as 𝒘 ⊗ 𝒉, 𝒂 ⊗ 𝒉, 𝒘 ⊗ 𝒃 .
One-body parameterTwo-body parameter

Simultaneous Rank-1 𝜽-condition
Its all two-body 𝜃-parameters are 0.

Simultaneous Rank-1 𝜼-condition𝜂𝑖𝑗 = 𝜂𝑖1 𝜂1𝑗

Möbius inversion formulaAll 𝜼-parameters after the projection are identified.
Using inversion formula, we found the projection destination.

19

Rank-1 NMF with missing values□ NMMF can be viewed as a special case of NMF with missing values.
Equivalent

20

Rank-1 NMF with missing values□ NMMF can be viewed as a special case of NMF with missing values.
Equivalent□ NMF is homogeneous for row and column permutations

21

A1GM: Method

Step 1 : Increase the number of missing values.

22A1GM: Method

Step 1 : Increase the number of missing values.
Step 2 : Gather missing values in the bottom right.

23

A1GM: Method

Step 1 : Increase the number of missing values.
Step 2 : Gather missing values in the bottom right.
Step 3 : Use the formula of rank-1 NMMF and repermutate.

24

Experiments on real data
□ A1GM is compared with gradient-based KL-WNMF- Relative runtime < 1 means A1GM is faster than KL-WNMF.
- Relative error > 1 means worse reconstruction error of A1GM than KL-WNMF.
- Increase rate is the ratio of # missing values after addition of missing values at step1.

25

Experiments on real data
□ A1GM is compared with gradient-based KL-WNMF- Relative runtime < 1 means A1GM is faster than KL-WNMF.
- Relative error > 1 means worse reconstruction error of A1GM than KL-WNMF.
- Increase rate is the ratio of # missing values after addition of missing values at step1.

26

Experiments on real data
□ A1GM is compared with gradient-based KL-WNMF- Relative runtime < 1 means A1GM is faster than KL-WNMF.
- Relative error > 1 means worse reconstruction error of A1GM than KL-WNMF.
Much faster!
- Increase rate is the ratio of # missing values after addition of missing values at step1.

27

Summary□ Closed Formula of the Best Rank-1 NMMF

□ A1GM: Faster Rank-1 NMF with missing values
Non-gradient-based method.
No worries about
initial values, stopping criterion and learning rate.
28