2重確率行列の性質

概要

本記事は、2重確率行列（doubly stochastic matrix）の性質について整理する。

2重確率行列とは、行と列がすべて1に正規化された非負要素行列である。

機械学習や推薦システムにおいて、確率的な正規化、最適な割当問題、分布推定など幅広く活用可能である。

本記事では、その定義、性質、応用、計算例、およびPythonによる簡易な実装例を提示する。

ソースコード

github

jupyter notebook形式のファイルはこちら

google colaboratory

google colaboratory で実行する場合はこちら

実行環境

OSはmacOSである。LinuxやUnixのコマンドとはオプションが異なりますので注意していただきたい。

!sw_vers

ProductName:		macOS
ProductVersion:		13.5.1
BuildVersion:		22G90

!python -V

Python 3.9.17

基本的なライブラリをインポートし watermark を利用してそのバージョンを確認する。ついでに乱数のseedの設定する。

%matplotlib inline
%config InlineBackend.figure_format = 'svg'

import random

import scipy
import numpy as np

import matplotlib
import matplotlib.pyplot as plt

seed = 123
random_state = 123

random.seed(seed)
np.random.seed(seed)


from watermark import watermark

print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))

Python implementation: CPython
Python version       : 3.9.17
IPython version      : 8.17.2

matplotlib: 3.8.1
numpy     : 1.25.2
scipy     : 1.11.2

Watermark: 2.4.3

2重確率行列の定義

2重確率行列は、非負要素を持ち、行和および列和が1となる正方行列である。以下、$n \times n$行列$\mathbf{M}$を考える。各要素は$M_{ij} \geq 0$とする。行方向と列方向の和が1となるため、任意の行$i$について

$$ \sum_{j=1}^{n} M_{ij} = 1 $$

および任意の列$j$について

$$ \sum_{i=1}^{n} M_{ij} = 1 $$

が成立する。このような$\mathbf{M}$を2重確率行列と呼ぶ。要素が確率を表す行列として自然な解釈が可能である。 2重確率行列は、要素がすべて非負であり、行列全体として確率分布を二方向に整合的に保持する構造を持つ。

また、2重確率行列は以下のような写像を定義可能である。 $f: \mathbb{R}^n \to \mathbb{R}^n,\ f(\mathbf{x}) = \mathbf{M}\mathbf{x}$ ここで、$\mathbf{x}$は$n$次元ベクトルであり、2重確率行列$\mathbf{M}$を用いると、$\mathbf{x}$を確率的な重みを考慮したベクトル$\mathbf{y} = \mathbf{M}\mathbf{x}$に写像できる。

この写像は確率空間上の変換とみなせることができる。

2重確率行列の基本性質

非負行列および確率的性質

2重確率行列は非負行列であり、行方向・列方向ともに要素の総和が1であるため、行列そのものを確率分布の変換する行列として考える事ができる。この性質により、確率ベクトルを入力すると、確率ベクトルを出力することが保証される。

Birkhoff–von Neumannの定理

Birkhoff–von Neumann定理によれば、全ての2重確率行列は、有限個の置換行列(permutation matrix)の凸結合(convex combination)で表せる。置換行列$\mathbf{P}$は、各行および各列に1つずつ1があり、それ以外は0である。 2重確率行列$\mathbf{M}$は、ある非負の重み$\lambda_k$の集合を用いて、

$$ \mathbf{M} = \sum_{k} \lambda_k \mathbf{P}_k,\quad \sum_{k} \lambda_k = 1,\ \lambda_k \ge 0 $$

と表せる。これにより、2重確率行列は、置換行列を基本要素とする凸包(Birkhoff多面体)内部の点であることが分かる。

置換と置換行列

置換

置換 $\sigma$ とは、 ${1,2, \ldots, n}$ の並べ替える写像を表す。たとえば、 $\sigma(1)=2, \sigma(2)=1, \sigma(3)=3$ などとなる。

置換行列

置換行列（Permutation Matrix）とは、正方行列で、各行と各列にちょうど1つだけ 1 があり、それ以外の要素はすべて 0 であるような行列のことである。

置換行列 $P$ は、以下のように定義される。

$$ p_{ij} = \begin{cases} 1 & \text{if } j = \sigma(i)\\ 0 & \text{otherwise} \end{cases} $$

例えば、以下のような形をしている。

$$ P = \begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}. $$

この行列は

1 行目で 2 列目に 1 がある (つまり $\sigma(1)=2$)
2 行目で 1 列目に 1 がある (つまり $\sigma(2)=1$)
3 行目で 3 列目に 1 がある (つまり $\sigma(3)=3$)

L1ノルムの保存性

行列$\mathbf{M}$を2重確率行列とする場合、任意の確率ベクトル$\mathbf{x}$に対して、 $\mathbf{y} = \mathbf{M}\mathbf{x}$は再び確率ベクトルとなる。

よって、$\sum_i y_i = \sum_i x_i = 1$である。

これは行列$\mathbf{M}$が確率ベクトル空間上で$\mathbf{x}$を保形的に変換することを意味する。

特に、$|\mathbf{x}|_1 = |\mathbf{M}\mathbf{x}|_1$が成立するため、$L_1$ノルムを不変に保つ線形変換である。

Frobeniusノルムに関する考察

2重確率行列は、全要素が非負かつ行列要素の行・列和が1である。

例えば、$n=3$の場合、ある2重確率行列$\mathbf{M}$を考えると、そのフロベニウスノルム $|\mathbf{M}|_F = \sqrt{\sum_{i,j} M_{ij}^2}$ は行列要素に依存し、特定の制約下で最小や最大を取り得る。

2重確率行列の集合は凸集合であり、その内部で様々な行列が存在する。

Birkhoff–von Neumann定理より、2重確率行列は置換行列の凸結合なので、その$|\mathbf{M}|_F$は置換行列の凸結合による値域内に収まる。

置換行列は1が$n$個、他が0であるため、$|\mathbf{P}|_F = \sqrt{n}$である。

よって、2重確率行列のフロベニウスノルムは$\sqrt{n}$付近の値を中心に、凸結合による平滑化が期待できる。

具体的な計算例

ここで簡単な例を示す。 $n=3$の2重確率行列$\mathbf{M}$を考える。例えば、

$$ \mathbf{M}=\left(\begin{array}{ccc} 0.5 & 0.3 & 0.2 \\ 0.2 & 0.4 & 0.4 \\ 0.3 & 0.3 & 0.4 \end{array}\right) $$

この行列は各行和、列和を確かめると、

行1和: $0.5 + 0.3 + 0.2 = 1.0$
行2和: $0.2 + 0.4 + 0.4 = 1.0$
行3和: $0.3 + 0.3 + 0.4 = 1.0$
列1和: $0.5 + 0.2 + 0.3 = 1.0$
列2和: $0.3 + 0.4 + 0.3 = 1.0$
列3和: $0.2 + 0.4 + 0.4 = 1.0$

よって、$\mathbf{M}$は2重確率行列である。この行列に確率ベクトル$\mathbf{x} = (0.2, 0.5, 0.3)^T$をかけると、

$$ \mathbf{y}=\mathbf{M x}=\left(\begin{array}{ccc} 0.5 & 0.3 & 0.2 \\ 0.2 & 0.4 & 0.4 \\ 0.3 & 0.3 & 0.4 \end{array}\right)\left(\begin{array}{c} 0.2 \\ 0.5 \\ 0.3 \end{array}\right)=\left(\begin{array}{c} 0.5 * 0.2+0.3 * 0.5+0.2 * 0.3 \\ 0.2 * 0.2+0.4 * 0.5+0.4 * 0.3 \\ 0.3 * 0.2+0.3 * 0.5+0.4 * 0.3 \end{array}\right)\\ =\left(\begin{array}{c} 0.1+0.15+0.06 \\ 0.04+0.2+0.12 \\ 0.06+0.15+0.12 \end{array}\right)=\left(\begin{array}{c} 0.31 \\ 0.36 \\ 0.33 \end{array}\right) $$

この結果ベクトル$\mathbf{y}$の要素和は$0.31 + 0.36 + 0.33 = 1.0$である。

ゆえに、入力が確率ベクトルであれば、出力も確率ベクトルとなる。

Pythonによる簡易実装例

以下に、Pythonによる2重確率行列検証と、任意ベクトルとの積を行う例を示す。

import numpy as np


# 2重確率行列か判定
def is_double_stochastic(M_np):

    # 非負要素確認
    if np.any(M_np < 0):
        return False

    # 行和確認
    row_sums_np = np.sum(M_np, axis=1)

    # 列和確認
    col_sums_np = np.sum(M_np, axis=0)

    # すべて1であれば2重確率行列とする
    if np.allclose(row_sums_np, 1.0) and np.allclose(col_sums_np, 1.0):
        return True

    return False


M_list = [[0.5, 0.3, 0.2], [0.2, 0.4, 0.4], [0.3, 0.3, 0.4]]
M_np = np.array(M_list)

# 判定
print("Is double stochastic?", is_double_stochastic(M_np))

# 確率ベクトル
x_list = [0.2, 0.5, 0.3]
x_np = np.array(x_list)

# 積
y_np = M_np.dot(x_np)
print("y        : ", y_np)
print("Sum of y : ", np.sum(y_np))

Is double stochastic? True
y        :  [0.31 0.36 0.33]
Sum of y :  1.0

上記コードを実行すると、2重確率行列か判定し、確率ベクトルを与えると再び確率ベクトルが得られることを確認できる。実行結果としては、Is double stochastic? Trueと表示され、出力ベクトルyの合計は1.0となる。

2重確率行列を得るためのアルゴリズム

一般的に、任意の非負行列を2重確率行列へ射影するには、Sinkhorn-Knoppアルゴリズムが利用される。

これは反復的に行列の行和・列和を正規化するプロセスである。

任意の行列$\mathbf{A}$に対して、

各行を正規化: $\mathbf{A}’_{ij} = \displaystyle \frac{A_{ij}}{\sum_j A_{ij}}$
各列を正規化: $\mathbf{A}’’_{ij} = \displaystyle \frac{A’_{ij}}{\sum_i A’_{ij}}$

このステップを反復し、収束すれば2重確率行列に近似可能である。

行列分解やスペクトル特性

2重確率行列$\mathbf{M}$の固有値分布は、特定の制約下で特徴的な振る舞いを示す。

最大固有値は1であり、その固有ベクトルは$(1,1,\dots,1)^T$に対応する。

また、他の固有値は単位円内に収まることが多く、安定性や収束性に関する議論で用いられる。

結論

この記事では、2重確率行列の基本的性質と応用例を概観した。

2重確率行列は行・列方向で確率的整合性を保つ非負行列であり、Birkhoff–von Neumann定理により置換行列の凸結合で表せることが知られている。

実装例やSinkhorn-Knoppアルゴリズムによるプロジェクション手法を通じて、2重確率行列の取得や利用が可能である。

[ランダムウォーク] 2重確率行列の性質