研究のアイデアって、どうやって思いつくんだよ!
新しいアルゴリズムを発明する、既存の手法を高速化する、最新の理論を組み合わせる。研究というと、こうしたアプローチを想像しがちだし、こういう芸当ができるのは一部の研究者に限る。
ただ、研究者でもない私たちにも参考にできる視点があります。
「難しい計算をしてくださいと言われたら、その計算を真に受けない」
つまり、与えられた問題をそのまま解くのではなく、もっと簡単な計算で同じ結果を得られないか考える、ということ。
今回は、その考え方を線形代数の具体例から整理してみます。
この記事で扱うのは、次のような問題です。
1000×1000の行列の固有値問題を、2×2の行列の固有値問題に置き換える。
一見すると不思議ですが、これは特異値分解(SVD)の基本的な性質から理解できます。
1. 問題設定:データ数が多いと行列も巨大になる
例えば、1000人について身長と体重を記録したデータを考えましょう。
- データ数:N = 1000
- 特徴量数:D = 2
データ行列を次のように定義します。
X \in \mathbb{R}^{N \times D}
今回の場合、Xは1000×2の行列になります。
ここで、各データ間の内積を表すグラム行列を考えます。
S = XX^\top
行列のサイズは、
S \in \mathbb{R}^{N \times N}
したがって、今回の例では1000×1000になります。
この行列の固有値や固有ベクトルを求めたいとします。
通常であれば、
Su = \lambda u
という固有値問題を解くことになりますが、ではデータ数が10万、100万と増えていくとどうでしょう。
100万×100万の密行列には、1兆個の要素が存在します。
float64で保存するだけでも、およそ8TBのメモリが必要……
そのような行列を明示的に作成し、直接対角化するのは現実的ではないですよね。
そこで、次のように考えてみます。
「本当に、この巨大な行列を直接対角化する必要があるのか?」
2. 小さい行列に置き換える
ここで、別の行列を考えてみます。
C = X^\top X
Cのサイズは、
C \in \mathbb{R}^{D \times D}
今回の例では、なんと2×2になります。
整理すると、こう。
| 行列 | 定義 | サイズ |
|---|---|---|
| S | XXᵀ | 1000×1000 |
| C | XᵀX | 2×2 |
実は、この2つの行列には重要な関係があります。
XXᵀ と XᵀX は、ゼロでない固有値が一致する。
しかも、それぞれの対応する固有ベクトルを相互に変換できます。
つまり、1000×1000の行列の非ゼロ固有値を知りたいだけなら、2×2の行列を対角化すればよいんです。
※ ここでCは特徴量側のグラム行列として定義している。Xの各列を平均0に中心化し、CをN−1で割れば、通常の標本共分散行列になる。
3. なぜ同じ固有値になるのか?
数学的に確認してみます。
まず、Cの固有値問題を考えます。
X^\top Xv = \lambda v
ここで、両辺の左からXを掛けます。
XX^\top Xv = \lambda Xv
積の順番をまとめると、
(XX^\top)(Xv) = \lambda (Xv)
これは、XXᵀ の固有値問題そのものになっています。
したがって、λが正の固有値であれば、XvはXXᵀの固有ベクトルになります。
vが単位固有ベクトルである場合、正規化して、
u = \frac{Xv}{\sqrt{\lambda}}
と置けば、
XX^\top u = \lambda u
が成立します。
逆方向についても同様で、XXᵀ の正の固有値に対応する単位固有ベクトルuから、
v = \frac{X^\top u}{\sqrt{\lambda}}
によって、XᵀXの固有ベクトルを得られます。
つまり、
大きい行列の固有値問題を、小さい行列の固有値問題に変換できる。
注意点は、固有値0に対応する固有空間まで単純に同一視できるわけではないことです。2つの行列はサイズが異なるため、ゼロ固有値の重複度は異なる場合があります。
4. 特異値分解(SVD)との関係
この性質は、特異値分解を使うとさらにわかりやすいです。
データ行列XのSVDを、
X = U\Sigma V^\top
とします。
すると、
XX^\top = U\Sigma\Sigma^\top U^\top
一方、
X^\top X = V\Sigma^\top\Sigma V^\top
となります。
どちらにも、Xの特異値の2乗が非ゼロ固有値として現れます。
つまり、2つの行列はサイズこそ異なるものの、非ゼロ固有値に関して同じ情報を持っているということです。
特に重要なのは、行列のランク。
\operatorname{rank}(XX^\top)
=
\operatorname{rank}(X^\top X)
=
\operatorname{rank}(X)
\leq \min(N,D)
今回の例ではD=2なので、1000×1000の行列Sのランクは最大でも2しかありません。
見かけ上は1000次元の巨大な行列であっても、非ゼロ固有値は最大2個しかないです。
行列のサイズが大きいことと、その行列が持つ独立な情報の次元が大きいことは、必ずしも同じではない。
ここが、この話の特に面白いところだと思いました。
5. Pythonで実際に確認してみる
NumPyを使って、2つの行列の固有値が一致することを確認してみましょう。
実行例では、計算を軽くするためN=100、D=2としました。
import numpy as np
rng = np.random.default_rng(42)
N = 100
D = 2
# データ行列
X = rng.normal(size=(N, D))
# 2つのグラム行列
S = X @ X.T # 100 x 100
C = X.T @ X # 2 x 2
# 対称行列用の固有値計算
eig_S = np.linalg.eigvalsh(S)
eig_C = np.linalg.eigvalsh(C)
# Sの大きい方からD個の固有値と比較
print("Sの非ゼロ固有値:")
print(eig_S[-D:])
print("Cの固有値:")
print(eig_C)
print(
"一致するか:",
np.allclose(eig_S[-D:], eig_C)
)
実行すると、2つの固有値が数値誤差の範囲で一致することが確認できます。
さらに、固有ベクトルも復元してみる。
# 小さい行列Cを固有値分解
eigenvalues, V = np.linalg.eigh(C)
# 今回はXがフル列ランクであることを想定
positive = eigenvalues > 1e-10
lam = eigenvalues[positive]
V = V[:, positive]
# Sの固有ベクトルを復元
U = (X @ V) / np.sqrt(lam)
# 固有値方程式の残差を確認
residual = S @ U - U * lam
print(
"固有値方程式の残差:",
np.linalg.norm(residual)
)
print(
"固有ベクトルの直交性:",
np.allclose(
U.T @ U,
np.eye(len(lam))
)
)
残差がほぼ0になれば、小さい行列から復元したベクトルが、大きい行列の固有値方程式を満たしていることがわかります。
なお、実際の大規模データでは、確認のためにSを作成する必要はありません。
6. 計算量はどれくらい変わるのか?
一般に、密なn×n対称行列の全固有値分解には、おおよそO(n³)の計算量が必要になります。
NがDより十分大きい場合を考える。
直接計算する場合
S = XXᵀ を作成し、固有値分解する。
- Sの構築:O(N²D)
- Sの固有値分解:O(N³)
- Sの保存:O(N²)
小さい行列を利用する場合
C = XᵀX を作成し、固有値分解する。
- Cの構築:O(ND²)
- Cの固有値分解:O(D³)
- Cの保存:O(D²)
元のデータXの保存には別途O(ND)が必要だが、N≫Dであれば非常に大きな差になります。
| 処理 | 大きい行列を直接計算 | 小さい行列を利用 |
|---|---|---|
| 行列の構築 | O(N²D) | O(ND²) |
| 固有値分解 | O(N³) | O(D³) |
| 対象行列の保存 | O(N²) | O(D²) |
もちろん、これは密行列に対する全固有値分解を比較した場合の話です。
実際には、反復法、疎行列アルゴリズム、ランダム化SVDなど、巨大な行列をすべて対角化しない手法もりますし、安定性を考慮してXに直接SVDを適用する方が望ましい場合もあります。
それでも、ここで重要なのは次のことです。
アルゴリズムを高速化する前に、計算対象のサイズそのものを小さくできないか考える。
ただし、大きな行列の全要素を明示的に出力する必要がある場合、その出力コスト自体をなくすことはできません。
7. NとDの小さい方を使う
ここまではN≫Dの場合を考えました。
では、逆にD≫Nの場合はどうでしょうか。
例えば、
- データ数:100
- 特徴量数:10000
という場合。
このとき、
- XᵀX:10000×10000
- XXᵀ:100×100
となります。
今度はXXᵀを使えばよいのです。
つまり、重要なのは「常にXᵀXを使う」ということではありません。
NとDの大小関係を見て、より小さい方の固有値問題を考えること。
これは、主成分分析(PCA)などを理解するうえでも役に立つ考え方です。
例えば、特徴量数よりサンプル数が少ない場合には、サンプル側のグラム行列を利用して主成分を求める方法が考えられます。
8. ここから研究のアイデアをどう生み出すか?
今回紹介した数学的性質は、新しい発見ではありません。
SVDや線形代数では、よく知られた基本的な性質です。
それでも、研究の進め方として非常に参考になるんじゃないかと思います。
難しい問題に直面したとき、つい次のように考えてしまいますよね。
- もっと高速なアルゴリズムはないか?
- GPUを使えば解けないか?
- 並列化すれば計算できるのではないか?
- 近似アルゴリズムを導入するべきか?
もちろん、これらは重要なアプローチです。
しかし、その前に確認すべきことがあるのではないか、と。
「そもそも、その計算は本当に必要なのか?」
今回の例であれば、1000×1000の行列を高速に対角化する方法を探す前に、2×2の固有値問題に置き換えられることに気づけばよいですから。
この考え方を一般化すると、研究テーマを探す際には次のような問いが使えそうですね。
① 本当にその問題を直接解く必要があるか?
最終的に必要なのは、行列全体なのか、固有値なのか、上位数個の固有ベクトルなのか。
求めたいものを明確にすれば、不要な計算が見つかるかもしれない。
② 等価な別の問題に変換できないか?
元の問題を直接解くよりも、双対問題や別の表現に変換した方が簡単な場合があります。
今回のXXᵀとXᵀXの関係は、まさにその例です。
③ 問題の構造を利用できないか?
問題には、次のような構造が隠れていることがあります。
- 低ランク性
- 疎性
- 対称性
- 冗長性
- ブロック構造
- 不変性
これらを利用すれば、同じ結果を得るために必要な計算を減らせる可能性があります。
④ 難しさは問題の本質なのか?
一見難しい問題であっても、その難しさは表現方法に由来しているだけかもしれません。
変数の取り方や計算する空間を変えることで、簡単な問題になる場合があります。
9. 研究としての新規性はどこにあるのか?
ここで注意したいのは、既知の数学的性質を利用することと、新しい研究成果を生み出すことは同じではない、という点です。
今回のXXᵀとXᵀXの関係そのものに新規性はありません。
しかし、例えば次のような状況には研究の余地があるかもしれない。
- 既存手法が利用していない低ランク構造を見つける
- 別の問題を、より小さい等価な問題に変換する
- ある分野で知られた計算技法を別分野に応用する
- 既存の近似手法について、新しい誤差保証を与える
- 特定の条件下で、計算量をさらに削減できることを示す
もちろん、実際に新規性があるかどうかは、先行研究の調査が必要になるでしょう。
それでも、最初の着眼点として「この計算は本当に必要なのか?」と疑う姿勢は有効だと思いました。
まとめ
今回の話から得られた教訓は、次の一言に集約される。
「難しい問題を、難しいまま解こうとしない」
1000×1000の行列が与えられたからといって、1000×1000の行列を直接対角化しなければならないわけではありません。
問題の構造を理解すれば、2×2の固有値問題に置き換えられる場合があるということです。
そして、これは行列計算だけの話ではないです。
研究やアルゴリズム開発においても、与えられた問題をそのまま受け入れるのではなく、次のように考えてみたい。
「同じ答えを、もっと簡単な問題を解くことで得られないだろうか?」
新しい研究アイデアは、既存の計算を高速化することだけでなく、そもそも不要な計算を見つけることからも生まれるのだと思いました。
お疲れ様でした。
わからないところ、間違っているところ、もっといい方法がある場合は、コメントでもDMでも教えてください。