🔔 本の下書きプレビューをシェアできるようになりました
Zenn
🐸

直交プロクラステス問題を用いたベクトル空間の対応付け

2025/01/12に公開
自然言語処理
word2vec
tech

はじめに

Word2Vecのような、1つの文書に対して1つの単語ベクトル空間を学習する自然言語処理手法では、複数の文書で学習を行うと、それぞれの文書に対して異なるベクトル空間が生成されます。そのため、文書間で単語ベクトルを直接比較することができません。

この問題に対する解決策として、直交プロクラステス問題を活用した手法があります。この手法では、異なる文書で独立に学習した単語のベクトル空間を線形変換で対応付けることで、直接比較できるようにしています。( Diachronic Word Embeddings Reveal Statistical Laws of Semantic Change ）

今回は、直交プロクラステス問題の解の導出と、実際に回転行列が見つけられることの確認を行います。

直交プロクラステス問題

直交プロクラステス問題とは、次の最小化問題です。

\min_{Q^T Q = I} \| A - Q B \|_F^2

2つの行列A,Bが与えられたとき、行列Bを直交行列Qで変換して最もAに近付くようなQを求める問題になっています。

直交行列の性質として、変換前後で内積やノルムが変化しない ((Q a)^{T} Q b = a^{T} b, \|Qa\|=\|a\|) というものがあります。この制約で、変換による各単語ベクトルが持つ意味の喪失を防ぐことができます。

最小化問題の解

\begin{aligned} \argmin_{Q^T Q = I} \| A - Q B \|_F^2 &= \argmin_{ Q^T Q = I } \text{tr} \left( (A - Q B)^T (A - Q B) \right) \\ &= \argmin_{Q^T Q = I} \text{tr} \left( A^{T} A \right) - 2 \text{tr} \left( A^{T} Q B \right) + \text{tr} \left( B^{T} B \right) \\ &= \argmax_{Q^T Q = I} \text{tr} \left( A^{T} Q B \right) \\ &= \argmax_{Q^T Q = I} \text{tr} \left( B A^{T} Q \right) (\text{tr} \left(A B \right) = \text{tr} \left(B A \right)) \\ &= \argmax_{Q^T Q = I} \text{tr} \left( U L V^{T} Q \right) \text{(特異値分解)} \\ &= \argmax_{Q^T Q = I} \text{tr} \left( L V^{T} Q U \right) \\ &= \argmax_{Q^T Q = I} \text{tr} \left( L Z \right) \end{aligned}

ここで、

L=\begin{pmatrix} \sigma_{1} & & 0 \\ & \ddots & \\ 0 & & \sigma_n \end{pmatrix}

なので以下のように評価できます。

\begin{aligned} \text{tr} \left( L Z \right) &= \sigma_{1} z_{1}^{T} + \sigma_{2} z_{2}^{T} + ... + \sigma_{n} z_{n}^{T} \\ &\leq \sigma_{1} \| z_{1} \| + \sigma_{2} \| z_{2} \| + ... + \sigma_{n} \| z_{n} \| \\ &= \sigma_{1} + \sigma_{2} + ... + \sigma_{n} \text{(Zは直交行列なので、各行は単位ベクトル)} \\ &= \text{tr} \left( L \right) \end{aligned}

したがって求める回転行列は Q = V U^{T}となります。

実装

import numpy as np

def orthogonal_procrustes(A, B):
    """
    直交プロクラステス問題を解く:
    Minimize ||A - B * Q||_F subject to Q^T Q = I.

    Parameters
    ----------
    B : np.ndarray of shape (d, n)
        回転させたい元の行列
    A : np.ndarrayの形状 (d, n)
        B * Q が近づくようにしたい行列

    Returns
    -------
    Q : np.ndarray of shape (d, d)
        B を A に最も近い形に変換する
        直交行列（回転行列）
    """
    # M = B * A^T を計算する (サイズ: d x d)
    M = B @ A.T

    # M に対して SVD を実行
    U, L, Vt = np.linalg.svd(M, full_matrices=True)

    # 最適な回転行列 Q = V * U^T を計算
    Q = Vt.T @ U.T

    return Q

次の設定で実際に回転行列が見つけられることを確認します。

  1. B, 直交行列Q_trueを用意
  2. BをQ_trueで回転したAを計算しておく
  3. 最適化問題をorthogonal_procrustes(A, B)で解いてQ_estを得る
  4. Q_trueと結果Q_estを比較
# ランダムに行列を生成
d, n = 32, 100
B = np.random.randn(d, n)

# A は B を何らかの回転行列で変換したものを用意
# 適当に直交行列 Q_true を作成
C = np.random.randn(d, d)
U_c, _, _ = np.linalg.svd(C)
Q_true = U_c  # 形状: (d, d)

A = Q_true @ B

# Q_est = argmin ||A - B*Q || を求める
Q_est = orthogonal_procrustes(A, B)

# Q_true と Q_est がどの程度近いかを表示
diff = np.linalg.norm(Q_true - Q_est, ord='fro')
print("(Q_true - Q_est)のFノルム: ", diff)
# diff が非常に小さければ、正しく計算できている
実行結果
(Q_true - Q_est)のFノルム:  7.834507516811041e-14

利用例

Diachronic Word Embeddings Reveal Statistical Laws of Semantic Change では、以下のような手順で直交プロクラステス法を用いて単語の意味変化を定量化する手法を提案しています。

  1. アメリカ英語を代表する大規模コーパスを1900年代から1990年代までの10年ごとに区切り、Word2Vec(SGNS)などで単語のベクトル空間を学習
  2. 直交プロクラステス問題を用いてベクトル空間同士を対応付け
  3. 年代間で単語ペアのコサイン類似度を計算
  4. コサイン類似度の時系列データから、単語の意味変化率を計算

まとめ

  • 直交プロクラステス問題の解は特異値分解（SVD）を用いて𝑄=𝑉𝑈^{𝑇}と求められる
  • 異なる時期の単語ベクトルを比較するために、ベクトル空間を変換して同じ座標軸に揃えることが可能

Discussion