メインコンテンツへスキップ
見出し画像

scikit-learn機械学習㊷TruncatedSVD

    前回は、t-SNEによる次元削減によって、高次元データの局所構造を保ちつつ、2次元や3次元での直感的なデータの可視化の仕組みを紹介しました。

    今回は、「疎なデータ」(Sparse Data)の次元削減に向いた手法であるTruncatedSVDを紹介します。

    疎なデータとは、「ほとんどの要素が0になる」データです。

    「スパースなデータ」や「スパースデータ」とも呼ばれます。

    例えば、「ほとんどの要素が0で埋まっている行列やベクトル」を思い浮かべてみてください。このようなデータをそのまま特徴量として扱うと、ほとんどの計算が0になるので、無駄な計算が多くなります。

    疎なデータはサイズが大きい場合が多く、特にt-SNEでは処理時間が長くかかります。

    本記事では、実例を使ってPCAやt-SNEと比較しながらTruncatedSVDを解説します。

    疎なデータとは

    疎な言語データのイメージ

    たとえば、以下のような3つの短い文書があったとします:

    • 「私はりんごが好きです」

    • 「彼はバナナを食べました」

    • 「りんごとバナナは果物です」

    これらの文書の特徴を捉えて分類するために、「登場するすべての単語」を軸としてベクトルに表現すると、次のような行列になります。

    画像

    このように文書をベクトル化すると、行列の中に「0」がたくさん現れます。

    これは、1つの文書が使っている単語は全体のごく一部であり、ほとんどの単語は使われていないからです。

    この例では、語彙数(ボキャブラリのサイズ)は13語だけですが、実際のテキスト処理では数万〜数十万語の語彙を扱うことも珍しくなく、疎になる傾向が顕著になります。

    なお、近年の言語モデルでは、単語やサブワードをあらかじめ密なベクトル(分散表現)に変換することで、疎なデータ構造の問題そのものを回避するアプローチが取られています。

    ただし、この記事では疎なデータの代表例として上述のような手法によるテキストのデータ表現を使っています。TruncatedSVD自体は、テキストだけでなく任意の疎な行列(例:ユーザー行動履歴、推薦システムなど)にも活用可能な手法です。

    この記事では、疎なデータの例として、テキストを数値ベクトルに変換する「TF-IDF」という手法を取り上げます。

    TF-IDFによる疎なデータ表現

    TF-IDF(Term Frequency - Inverse Document Frequency)は、文書内に現れる単語の重要度を数値化する方法です。

    まず、TF(Term Frequency)とは、単語(トークン)の出現頻度です。これは、各単語がある文書の中で何回出てきたかを頻度で表現します。

    例えば、文書Aにおいて「ネコ」が3回出現し、文書Aの総単語数が100の場合、TFは以下になります。

     文書Aにおける「ネコ」のTF=「ネコ」の出現回数文書Aの総単語数=3100=0.03 \\ \text{文書Aにおける「ネコ」のTF} = \frac{「ネコ」の出現回数}{文書Aの総単語数} = \frac{3}{100} = 0.03 \\[2ex]

    IDF(Inverse Document Frequency)は、トークンの逆文書頻度です。

    例えば、コーパスが1000の文書で構成され、「ネコ」が100の文書に登場する場合、IDFは常用対数(底が10)を使うと以下になります。

     コーパスにおける「ネコ」のIDF=log⁡10コーパス内の文書の数「ネコ」が出現する文書数=log⁡101000100=log⁡1010=1\begin{aligned}  \\ \text{コーパスにおける「ネコ」のIDF} &= \log_{10} \frac{コーパス内の文書の数}{「ネコ」が出現する文書数} \\[3ex] &= \log_{10} \frac{1000}{100} = \log_{10} 10 = 1 \end{aligned}

    このIDFは「ネコ」が登場する文書が少ないほど大きな値になります。つまり、単語の希少性を表現しています。逆に、多くの文書に出現すトークンは、対数の中身が1に近づくので、IDFは0に近づきます。つまり、稀ではないトークンのIDFは0に近づき、特徴としては弱くなります。

    TF-IDFをまとめると以下になります。

    TF-IDF​=TF×IDF=文書内のトークンの頻度×log⁡(文書総数トークンを含む文書の数​)​\begin{aligned} \text{TF-IDF} ​&= \text{TF} \times \text{IDF} \\ &= \text{文書内のトークンの頻度} \times \log \left(\frac{\text{文書総数}}{\text{トークンを含む文書の数​}}\right)​ \\\end{aligned}

    つまり、TF-IDFは、ある文書における各単語の特徴を「出現頻度 x 珍しさ」で表現しています。その文書の中ではよく使われているけれど、他の文書ではあまり見かけない単語は、文書の特徴をより強く表すことになります。

    各文書に登場するトークンに対して、TF-IDFを計算すれば、文書をベクトルとして数値で表現することができます。このベクトルの各要素は、コーパス内に出現するすべてのトークンに対応し、各文書で使われているトークンに対してだけTF-IDFの値があり、それ以外はゼロになります。

    TF-IDFによる文書ベクトルは、コーパス内の文書の違いを表現することができる一方、文書によって使われるトークンが大きく異なる場合、文書ベクトルは疎になります。すると、コーパス全体が疎行列で表現され、疎なデータセットになります。

    なお、scikit-learnにはTF-IDFを扱うためのツールが用意されています。

    疎なデータセットの準備

    ここからは、scikit-learnのTruncatedSVDによる実践を通して解説します。

    Python環境の設定

    Pythonの仮想環境を作ってscikit-learnとJupyterなど必要なライブラリをインストールします。

    # 作業フォルダを作って、そこへ移動する
    mkdir tsvd_test
    cd tsvd_test
    
    # 仮想環境を作り、アクティベートする
    python3 -m venv venv
    source venv/bin/activate
    
    # pip をアップグレードしておく
    pip install --upgrade pip
    
    # 必要なライブラリをインストール
    pip install numpy scikit-learn pandas jupyter matplotlib

    Jupyterを立ち上げるか、vscode内で新規に作った.ipynbファイルを開いてセルを追加しながら実行していくスタイルを想定しています。

    ニュースグループのデータ

    まずは、scikit-learn の datasets から20のニュースグループからのテキストをダウンロードします。

    from sklearn.datasets import fetch_20newsgroups
    
    # データの読み込み
    newsgroups = fetch_20newsgroups(
        subset='all', 
        remove=('headers', 'footers', 'quotes'))

    ヘッダーやフッターは不要なので除外しています。

    20のニュースグループの名前を見てみます。

    newsgroups.target_names
    ['alt.atheism',
     'comp.graphics',
     'comp.os.ms-windows.misc',
     'comp.sys.ibm.pc.hardware',
     'comp.sys.mac.hardware',
     'comp.windows.x',
     'misc.forsale',
     'rec.autos',
     'rec.motorcycles',
     'rec.sport.baseball',
     'rec.sport.hockey',
     'sci.crypt',
     'sci.electronics',
     'sci.med',
     'sci.space',
     'soc.religion.christian',
     'talk.politics.guns',
     'talk.politics.mideast',
     'talk.politics.misc',
     'talk.religion.misc']

    'comp'で始まるのは「コンピュータ関係」、'rec'で始まるのは「レクリエーション」といった具合です。

    次に、最初のテキストを見てみます。

    # 最初のテキスト
    print(newsgroups.data[0])
    I am sure some bashers of Pens fans are pretty confused about the lack
    of any kind of posts about the recent Pens massacre of the Devils. Actually,
    I am  bit puzzled too and a bit relieved. However, I am going to put an end
    to non-PIttsburghers' relief with a bit of praise for the Pens. Man, they
    are killing those Devils worse than I thought. Jagr just showed you why
    he is much better than his regular season stats. He is also a lot
    fo fun to watch in the playoffs. Bowman should let JAgr have a lot of
    fun in the next couple of games since the Pens are going to beat the pulp out of Jersey anyway. I was very disappointed not to see the Islanders lose the final
    regular season game.          PENS RULE!!!

    これはどのカテゴリでしょうか。

    print(newsgroups.target[0])
    10

    これはカテゴリのインデックスなのでカテゴリ名は次のように取得します。

    print(newsgroups.target_names[10])
    rec.sport.hockey

    ホッケーの関連ですね。

    Pandasで前処理

    このデータをPandasのデータフレームに格納して前処理を行います。

    import pandas as pd
    
    # データフレームに格納
    df = pd.DataFrame({
        'target': newsgroups.target,
        'text': newsgroups.data, 
    })

    各テキストのラベル名がわかるようにフィールドを追加します。

    # ラベルの名前を追加
    df.insert(1, 'label', df['target'].apply(lambda x: newsgroups.target_names[x]))

    データの最初の5行を確認します。

    # データの確認
    df.head()
    画像

    これで前処理が終了しました。

    データ分析とフィルタリング

    各カテゴリの文章の数を確認します。

    # それぞれのグループのデータ数
    df['label'].value_counts()
    label
    rec.sport.hockey            999
    soc.religion.christian      997
    rec.motorcycles             996
    rec.sport.baseball          994
    sci.crypt                   991
    rec.autos                   990
    sci.med                     990
    comp.windows.x              988
    sci.space                   987
    comp.os.ms-windows.misc     985
    sci.electronics             984
    comp.sys.ibm.pc.hardware    982
    misc.forsale                975
    comp.graphics               973
    comp.sys.mac.hardware       963
    talk.politics.mideast       940
    talk.politics.guns          910
    alt.atheism                 799
    talk.politics.misc          775
    talk.religion.misc          628
    Name: count, dtype: int64

    最後の3つを除くと、ほぼ均等になっています。

    では、テキストの長さはどうでしょうか。カテゴリごとに文書の平均の文字数を確認します。

    # カテゴリごとの平均の文字数
    df['text'].apply(len).groupby(df['label']).mean()
    label
    alt.atheism                 1180.553191
    comp.graphics               1294.299075
    comp.os.ms-windows.misc     1806.608122
    comp.sys.ibm.pc.hardware     748.612016
    comp.sys.mac.hardware        655.126687
    comp.windows.x              1474.977733
    misc.forsale                 702.516923
    rec.autos                    655.187879
    rec.motorcycles              572.448795
    rec.sport.baseball           724.451710
    rec.sport.hockey            1125.755756
    sci.crypt                   1420.279516
    sci.electronics              714.970528
    sci.med                     1309.617172
    sci.space                   1212.656535
    soc.religion.christian      1628.073220
    talk.politics.guns          1187.664835
    talk.politics.mideast       2146.444681
    talk.politics.misc          1723.335484
    talk.religion.misc          1318.464968
    Name: text, dtype: float64

    これは、カテゴリによって差がありますが、どれも量があります。

    ただし、カテゴリが多く可視化が分かりにくくなるので、3つに絞ります。

    # 使用するグループを選択
    filtered_df = df[df['label'].isin([
        'comp.sys.mac.hardware',
        'rec.motorcycles',
        'talk.politics.misc',
    ])]

    この3つのカテゴリはだいぶ異なるのでそれなりに分割できるはずです。

    TF-IDFによる文書のベクトル化

    次に、scikit-learnの TfidfVectorizer を使って、TF-IDFによる文書のベクトルを計算します。

    from sklearn.feature_extraction.text import TfidfVectorizer
    
    vectorizer = TfidfVectorizer(max_features=5000, stop_words='english')

    max_features = 5000 と指定しているのは、特徴量として扱うトークンの最大数です。少ないと特徴を十分表現できないので、ある程度の数は必要です。どのくらいを使うべきかは試して決めるようになりますが、ここでは適当に5000にしました。

    また、stop_words = 'english' となっているのは、テキストをトークン化するときに重要で無いものを無視するルールが英語用だということです。

    英語のストップワードは、例えば “and”, “the”, “him” といったものです。

    英語以外の場合は、無視するテキストのリストを指定します。

    なお、TfidfVectorizer では、英語のような言語で単語間にスペースがあるものを想定しています。よって、正規表現による単純なトークンの抽出が行われます。この正規表現のデフォルトは token_pattern=r"(?u)\b\w\w+\b"と指定されています。

    日本語などは文章を分析しないとトークン化できないので、TfidfVectorizer では簡単に日本語のトークン化が行えません。そこで自前のトークン化の関数を用意して tokenizer として指定する必要があります。詳しくは、公式ドキュメントを参照してください。

    では、すべての文書をTF-IDFによって変換します。

    # TF-IDFの行列
    X_tfidf = vectorizer.fit_transform(filtered_df.text)

    X_tfidfは、各文書をTF-IDFでベクトル化したものを含む行列です。

    print(f"TF-IDF行列の形状: {X_tfidf.shape}")

    この形状は(文書数、語彙数)になります。

    TF-IDF行列の形状: (2734, 5000)

    このデータ構造の中身をプリントしてみます。

    print(X_tfidf)
    <Compressed Sparse Row sparse matrix of dtype 'float64'
    	with 111044 stored elements and shape (2734, 5000)>
      Coords	Values
      (0, 3172)	0.10462204673612928
      (0, 2509)	0.36638771090612055
      (0, 1571)	0.2867623451925324
      (0, 4740)	0.24354926318282874
      (0, 3088)	0.08064573828379822
      (0, 4699)	0.1486953921764238
      (0, 1573)	0.12670974136063204
      (0, 2969)	0.1690231925479129
      (0, 3200)	0.10699576246010871
      (0, 2015)	0.17131079347028744
      (0, 1529)	0.07736403687996615
      (0, 2583)	0.1384732977500712
      (0, 2400)	0.3593664098417731
      (0, 3526)	0.12341909901965399
      (0, 4014)	0.1050030798609962
      (0, 71)	0.1103002093828817
      (0, 2318)	0.1103002093828817
      (0, 4944)	0.08825984298974597
      (0, 1456)	0.1449331528781767
      (0, 4476)	0.29164890530979937
      (0, 4754)	0.3426215869405749
      (0, 4654)	0.09871761724683675
      (0, 1475)	0.13672056456671888
      (0, 721)	0.11755247086746243
      (0, 4741)	0.08950707251978582
      :	:
      (2733, 2827)	0.11474604200390613
      (2733, 3395)	0.2032568130507972
      (2733, 516)	0.11687731490306351
      (2733, 510)	0.12392285603450526
      (2733, 1154)	0.10789438598673222
      (2733, 288)	0.12499690903514399
      (2733, 468)	0.10023192630800776
      (2733, 3933)	0.12499690903514399
      (2733, 3829)	0.2402102884724634
      (2733, 3082)	0.09596867764334725
      (2733, 4519)	0.10648220314937987
      (2733, 2917)	0.11220481328810818
      (2733, 2551)	0.1329432102382567
      (2733, 2944)	0.12732591185246117
      (2733, 2049)	0.25989351663434945
      (2733, 2034)	0.13461925993213006
      (2733, 1454)	0.14310947334535895
      (2733, 4065)	0.20782995769291993
      (2733, 2261)	0.11842909454235834
      (2733, 4935)	0.10838710148983462
      (2733, 1714)	0.13843697173040362
      (2733, 369)	0.14590554629486024
      (2733, 3643)	0.14590554629486024
      (2733, 3142)	0.13843697173040362
      (2733, 1455)	0.4474001268840853

    「Compressed Sparse Row sparse matrix of dtype 'float64' with 111044 stored elements and shape (2734, 5000)」と書かれていますが、これは以下の意味です。

    • 形式:CSR(Compressed Sparse Row)
      行(文書)ごとに圧縮されている。
      よって、文書ごとに効率的にアクセスできる形式。

    • データ型:「float64」

    • 格納要素数:111,044(非ゼロのTF-IDFスコアの数)

    • 文書数:2734行

    • 語彙数:5000列

    タイプを確認します。

    type(X_tfidf)
    scipy.sparse._csr.csr_matrix

    scipy.sparse の疎行列形式(csr_matrix) です。プリントされたデータを見ると、0以外の値にインデックス(文書ID、トークンID)をつけて、TF-IDFの値を格納しているのがわかります。

    例えば、(0, 3172) 0.1046 は、以下の意味になります。

    • 文書のインデックスが0

    • 語彙のID(列番号)が3172

    • TF-IDFの値が0.1046

    このように疎行列形式は、メモリを効率的に利用しています。

    最初の文書のトークンをTF-IDFが高い順で10個表示してみます。

    # トークンの名前
    tokens = vectorizer.get_feature_names_out()
    
    # 最初の文書のトークンとTF-IDF値
    doc_row = X_tfidf[0]
    doc_words = [tokens[i] for i in doc_row.indices]
    doc_tfidf = doc_row.data
    
    # TF-IDF値の高い順にソート
    sorted_tfidf = sorted(zip(doc_words, doc_tfidf),
                 key=lambda x: x[1], reverse=True)
    
    # 最初の文書のトップ10のトークンとTF-IDF値
    for word, tfidf in sorted_tfidf[:10]:
        print(f"{word:15s}: {tfidf:.2f}")
    jasmine        : 0.37
    inexpensive    : 0.36
    utility        : 0.34
    tape           : 0.29
    drive          : 0.29
    use            : 0.24
    tapes          : 0.18
    gain           : 0.17
    modern         : 0.17
    150            : 0.16

    なお、NumPyの配列(密行列形式)することもできます。

    print(X_tfidf.toarray())
    [[0.         0.         0.         ... 0.         0.         0.        ]
     [0.         0.         0.         ... 0.         0.         0.        ]
     [0.         0.         0.         ... 0.         0.         0.        ]
     ...
     [0.         0.         0.         ... 0.         0.         0.        ]
     [0.         0.         0.         ... 0.         0.         0.        ]
     [0.11048279 0.         0.         ... 0.         0.         0.        ]]

    多くの要素がゼロの行列になっているのが確認できます。

    TruncatedSVDによる次元削減

    TruncatedSVDで実験する前に、t-SNEとPCAで実験して後で比較します。

    t-SNEによる次元削減

    まずは、t-SNEで次元削減してみます。

    # t-SNEで次元削減
    import time
    from sklearn.manifold import TSNE
    
    time_start = time.time()
    
    tsne = TSNE(n_components=2)
    X_tsne = tsne.fit_transform(X_tfidf.toarray())
    
    print('t-SNE done! Time elapsed: {:.4f} seconds'.format(time.time()-time_start))

    なお、X_tfidf.toarray() とデータをNumPyの配列(密行列)に変換して渡しています。

    ちなみに、疎行列のままに渡すこともできます。その場合は、TSNEの初期化の時に、init='random'と指定します。ただし、結果は悪くなります。

    実は、TSNEのデフォルトでは、init='pca'が指定されており、これはデータをあらかじめPCAを使って指定次元に事前圧縮した後に、TSNEのロジックを適用しています。これによって、低次元での配置が良くなりやすいという利点があります。

    よって、ここでは初期化はデフォルト(init='pca')にしておき、変換の際に入力を密行列にしています。

    また、かかった秒数をプリントしています。

    t-SNE done! Time elapsed: 5.4165 seconds

    5.4秒でした。もちろん、ハードウェアや環境によって結果は異なります。

    結果を可視化するために次のような関数を定義します。

    import matplotlib.pyplot as plt
    
    def plot_2d(X, title):
        plt.figure()
        for label in filtered_df.label.unique():
            x1, x2 = X[filtered_df.label == label].T
            plt.scatter(x1, x2, label=label, alpha=0.3)
        plt.title(title)
        plt.legend()
        plt.axis('equal')
        plt.show()

    では、t-SNEによる次元削減の結果を可視化をします。

    # 可視化
    plot_2d(X_tsne, 't-SNE')
    画像

    3つのカテゴリに分かれているのがわかります。ただし、中央にたくさんの文書が集まってもいます。

    パープレキシティはデフォルト(30)のままです。50にしてもあまり変わりませんでした。異なるカテゴリでもデータが疎なので特徴が類似していると判断されているようです。

    PCAによる次元削減

    次に、PCAで実験します。

    # PCAで次元削減
    import time
    from sklearn.decomposition import PCA
    
    time_start = time.time()
    
    pca = PCA(n_components=2)
    X_pca = pca.fit_transform(X_tfidf)
    
    print('PCA done! Time elapsed: {:.4f} seconds'.format(time.time()-time_start))
    PCA done! Time elapsed: 0.0275 seconds

    私の環境では、わずか0.275秒でした。t-SNEと比べるとずっと早いです。

    なお、PCAのデフォルトでは、svd_solver = 'auto' となっており、使われるロジックが自動的に選ばれます。

    svd_solverが、'auto'のままか、あるいは'arpack'か'covariance_eigh'が指定されている場合は、疎なデータを受け入れることができます。

    ちなみにfit(あるいはfit_transform)の後には、実際に選ばれたソルバーを次のように参照することもできます。

    print(pca._fit_svd_solver)
    arpack

    詳しくは公式ドキュメントを参照してください。

    可視化を行います。

    # 可視化
    plot_2d(X_pca, 'PCA')
    画像

    割と綺麗に3つに分かれていますが、中央で重なりがあります。データが疎であるため特徴の区別がつけられないためでしょう。

    TruncatedSVDによる次元削減

    TruncatedSVDでは、疎行列をそのまま入力として使うことができます。

    # SVDで次元削減(例)
    import time
    from sklearn.decomposition import TruncatedSVD
    
    time_start = time.time()
    
    svd = TruncatedSVD(n_components=2)
    X_svd = svd.fit_transform(X_tfidf)
    
    print('SVD done! Time elapsed: {:.4f} seconds'.format(time.time()-time_start))

    また、PCAよりわずかに速かったですが、この程度のデータ量だとほぼ同等の処理速度でした。

    TruncatedSVD done! Time elapsed: 0.0231 seconds

    可視化をします。

    # 可視化
    plot_2d(X_svd, 'TruncatedSVD')
    画像

    TruncatedSVDでは、2つのカテゴリが大きく重なっています。よって、PCAより高速ですが、このテストではPCAほど次元削減による特徴の区別がうまくいっていないのがわかります。

    これは、PCAでは中心化を行うからだと考えられます。TruncatedSVDでは中心化を行いません。

    仮に、自分で中心化したデータをTruncatedSVDに渡すと次元削減の結果が同じようになります。

    # 中心化してから、SVDで次元削減
    import time
    from sklearn.decomposition import TruncatedSVD
    
    time_start = time.time()
    
    centered_X_tfidf = X_tfidf.toarray() - X_tfidf.toarray().mean(axis=0)
    
    svd = TruncatedSVD(n_components=2)
    centered_X_svd = svd.fit_transform(centered_X_tfidf)
    
    print('SVD done! Time elapsed: {:.4f} seconds'.format(time.time()-time_start))
    SVD done! Time elapsed: 0.1660 seconds

    中心化をする時間を加えたため、だいぶ遅くなりました。よって、PCAの内部では中心化をより効率よく行なっているようです。

    画像
    中心化した入力によるTruncatedSVD

    このプロットを見ると、PCAからの出力と非常に似ています。

    では、中心化を除くと、TruncatedSVDとPCAは何が違うのでしょうか。

    TruncatedSVDの仕組み

    PCAと何が違うのか

    scikit-learn のPCAは、svd_solver = 'auto' (デフォルト)の場合、
    内部で判断して、固有値分解か特異値分解の異なるライブラリが使われます。多くの場合、特異値分解が使かわれるので、PCAが中心化することを除けばTruncatedSVDとほとんど同じです。

    ただし、TruncatedSVDが使用しているのは、ランダム化SVD(randomized SVD)という手法です。これは、「近似的にSVDを高速に計算するためのアルゴリズム」です。特に、巨大な行列に対して、上位k個の特異値・特異ベクトルだけが欲しいときに使います。計算コストを大幅に削減できます。

    なお、PCA においても svd_solver='randomized' を指定すれば、TruncatedSVD と同様のランダム化手法が利用されます。

    しかし、PCAの良いところは、デフォルトのsvd_solver='auto'の場合、最適な手法を自動で選んでくれるところです。上述したように、今回のデータでは「arpack」(scipy.sparse.linalg.svdsを使う)が選ばれています。

    また、PCA は中心化(平均を0にする処理)を前提としているので、中心化を必要としない場合などは、TruncatedSVD を使うことも選択肢になります。

    まず、やりたいこと

    通常のSVDの計算では、全ての特異値とベクトルを計算しますが、これは次元の呪いによってデータの量や特徴量の数によって計算量が多くなります。

    要するに、行列が大きくなると非常に遅いです。また、疎行列でも密行列として扱う必要が出てきて、メモリ的にも要求が高くなります。

    そこで、大きな行列AAを「低次元の行列BB」と「高次元の行列CC」で表現することを考えます。

    A⏟m×n =B⏟m×k  C⏟k×n\underbrace{A}_{m \times n} = \underbrace{B}_{m \times k} \; \underbrace{C}_{k \times n}

    ここで、mmがデータの数(サンプル数)で、nnが特徴量の数(次元数)です。また、kk は削減後の次元数であり、ユーザーが指定するパラメータです。

    たとえば、データ数が9000で、特徴量が5000で、指定された次元が2の場合、次のようになります。

    A⏟9000×5000 =B⏟9000×2  C⏟2×5000\underbrace{A}_{9000 \times 5000} = \underbrace{B}_{9000 \times 2} \; \underbrace{C}_{2 \times 5000}

    このような分解が可能であれば、行列AAの各データをn=5000n=5000次元から、k=2k=2次元に削減できたことになります。なお、2次元空間として意味のある表現にするためには、行列BBの列ベクトルが互いに直交していることが望まれます。

    しかし、こうした直交ベクトルを計算するには、通常は行列全体を固有値分解か特異値分解する必要があります。これは計算コストが高く、大規模データでは現実的でない場合もあります。

    欲しいのは高次元の行列AAを低次元化した行列BBであり、行列CCには興味ありません。何か直接BBだけを計算し、無駄を省く方法がないものでしょうか。

    そこで、ランダム射影が使われます。

    ランダム射影で削減

    ランダム射影は、高次元空間からkk本の「ほぼ直交する方向」を確率的に近似的に選び出し、その方向に射影することで、元の行列の構造を効率よく低次元に圧縮します。

    まず、大きな行列AAに対して、ランダムな行列Ω\Omegaを掛けます。

    B⏟m×k=A⏟m×n  Ω⏟n×k\underbrace{B}_{m \times k} = \underbrace{A}_{m \times n} \; \underbrace{\Omega}_{n \times k}

    ここで、Ω\Omegaは各列がランダムに(ガウス分布などで)選ばれた密なベクトルで構成された行列です。Ω\Omegaの列ベクトルは、ユーザーが指定するk<nk < nにより、元の行列AAは高次元nnから低次元kkへと圧縮されます。

    先ほどの例を用いると、次のようになります。

    B⏟9000×2=A⏟9000×5000  Ω⏟5000×2\underbrace{B}_{9000 \times 2} = \underbrace{A}_{9000 \times 5000} \; \underbrace{\Omega}_{5000 \times 2}

    これは、50005000次元空間における2つのランダムな方向(ベクトル)を選び、データをその2方向に射影(2次元に変換)するということです。

    高次元空間では、ランダムなベクトル同士は、コサイン類似度は非常に低くなる傾向があります。これは次元が大きくなるほど、ランダムなベクトル同士は高確率でほぼ直交することを意味しています。

    よって、ランダム行列Ω\Omegaの列ベクトルも互いにほぼ直交しており、B=A ΩB = A \, \Omegaという変換は、元の行列AAを異なる(ほぼ)直交方向に射影しているとみなすことができます。

    また、Ω\Omegaのベクトルは密であり、すべての次元にある程度の重みを持つため、元の特徴量の情報が、射影後の空間にも広く反映されます。これにより、低次元の行列BBにおいても、元の行列AAの構造を、近似的に保つことが可能になります。

    もちろん、次元を削減する以上、一定の情報は失われます。しかし、ここでの議論はあくまで「低次元に変換する前提で、できるだけ元の構造を保ちたい」という文脈に基づいて行われています。

    参考:Finding structure with randomness

    こうして、データセットは近似的に直交するベクトルによって低次元空間に射影されました。

    次に、QR分解を行って、このランダムに得られた空間の中から、互いに直交する整った基底(方向)を抽出します。これにより、後続の処理が、より安定的かつ効率的になります。

    「安定」とは、正規直交な軸に基づく演算で数値誤差が抑えられることです。また、「効率的」とは、元の大きな行列に直接演算せず、小さな空間で処理を行えることを意味します。後者については、QR分解の結果がどう利用されるのかを見ると理解できます。

    QR分解による基底

    QR分解では、与えられた行列を「列直交行列QQ」と「上三角行列RR」に分解することができます。

    列直交行列とは「列が互いに直交かつ正規化された行列」です。

    なお、Q行列の列ベクトルは「分解される行列の列ベクトルが張る空間」と同じ空間を張ります。つまり、ここでは空間を変えずに基底を整えています。

    先ほどランダム射影によって低次元化された行列BBに対して、QR分解を行うことで、データ構造を維持したまま行列BBの列ベクトルを直交化できます。このQR分解は、以下のように表現できます。

    B⏟m×k=Q⏟m×k  R⏟k×k\underbrace{B}_{m \times k} = \underbrace{Q}_{m \times k} \; \underbrace{R}_{k \times k}

    ここで、行列QQの列ベクトルは、低次元空間における正規直交基底を表しています。つまり、行列QQの列ベクトルは互いに直交し、かつ正規化(長さ1)されています。

    行列RRは上三角行列で、行列QQの要素を組み合わせて行列BBを再現しています。しかし、この後では、特に必要ありません。

    なお、行列QQの列ベクトルはmm次元であり、元の行列AAの各列ベクトルと同じmm次元空間に属します。よって、行列QQが張るkk次元の正規直交基底に行列AAの各列を射影することで、次のように行列AAの低次元表現を得ることができます。

    D⏟k×n=Q⊤⏟k×m  A⏟m×n\underbrace{D}_{k \times n} = \underbrace{Q^\top}_{k \times m} \; \underbrace{A}_{m \times n}

    行列DDは、行列AAの各列をQQの基底で表現した座標情報を表しています。こうして構造をできるだけ保ちつつ行列AAの情報を低次元の正規直交基底で表現できました。

    ここでは、行列AAの各列がmm次元です。よって、各列は「1つの特徴量について、全mmサンプルにわたる値」をまとめたmm次元ベクトルと見なせます。

    これにQ⊤Q^\topを左からかける操作によって、mm次元だった各列ベクトルが、kk次元の空間に射影されています。よって、各特徴量ベクトルが表す「mm個のサンプル値」の次元をkkに圧縮しているわけです。

    サンプル数を削減しているのではなく、行列全体の情報量を圧縮しています。

    なお、 行列QQの列ベクトルは、互いに正規直交しています。よって、以下が成り立ちます。

    Q⊤Q=I⏟k×kQ^\top Q = \underbrace{I}_{k \times k}

    しかし、行列QQの行ベクトルは一般に独立ではありません。

    QQ⊤≠I⏟m×mQ Q^\top \neq \underbrace{I}_{m \times m}

    つまり、QD=QQ⊤A≠AQD = QQ^\top A \neq Aです。

    ただし、QDQDは、m×nm \times nの行列AAをk×nk \times nの行列DDに圧縮したものを、再びm×nm \times nの次元で表現したものです。よって、本質的には独立したkk個のベクトルで表現される空間(ランクがkk)から得られる以上の情報はありません。つまり、kk次元に圧縮されたものをmm次元にしただけです。このことをA≈QDA \approx QDと書くことにしますが、数値的に同じという意味ではありません。

    低次元で特異値分解

    こうしてkk次元に次元削減されたデータに特異値分解(SVD)を行います。

    SVDは固有値分解と違って、分解される行列が正方行列である必要がなく、次のように分解できます。

    D=U  Σ  V⊤D = U \; \Sigma \; V^\top

    それぞれのサイズは以下になります。

    D⏟k×n=U⏟k×k  Σ⏟k×n  V⊤⏟n×n\underbrace{D}_{k \times n} = \underbrace{U}_{k \times k} \; \underbrace{\Sigma}_{k \times n} \; \underbrace{V^\top}_{n \times n}

    ⊤^\topは行列の転置の意味です。

    どのような実数の行列DDに対しても必ず特異値分解が存在することが数学的に保証されています。

    次に、行列UUと行列VVの意味を解説します。

    DD⊤DD^\topは正方行列なので、次のような固有値分解が可能です。

    DD⊤U=UΛ(U)DD^\top U = U \Lambda^{(U)}

    行列UUは、DD⊤DD^\topの固有ベクトル(列ベクトル)を並べたものです。また、Λ(U)\Lambda^{(U)}は、固有値を対角行列にしたものです。さらに、次の関係が成り立ちます。

    DD⊤=UΛ(U)U⊤DD^\top = U \Lambda^{(U)} U^\top

    ここでは、固有ベクトルが互いに直交しているためUU⊤=IUU^\top=Iとなることを利用して両辺にU⊤U^\topを掛けています。

    D⊤DD^\top Dも正方行列なので、固有値分解が可能です。

    D⊤DV=VΛ(V)D^\top D V = V \Lambda^{(V)}

    行列VVは、D⊤DD^\top Dの固有ベクトル(列ベクトル)を並べたものです。また、Λ(V)\Lambda^{(V)}は、固有値を対角行列にしたものです。さらに、次の関係が成り立ちます。

    D⊤D=VΛ(V)V⊤D^\top D = V \Lambda^{(V)} V^\top

    ただし、実装ではDD⊤DD^\topやD⊤DD^\top Dを直接に計算するわけではなく、専用のアルゴリズムを使い効率的に計算します。そのため、scikit-learnでも内部で異なるSVDの実装ライブラリを使っています。

    なお、DD⊤DD^\topとD⊤DD^\top Dは、どちらも半正定値対称行列であるため、固有値は非負実数(0以上の実数)です。

    半正定値対称行列とは、どのようなベクトルv\boldsymbol{v}に対しても、v⊤Xv≥0\boldsymbol{v}^\top X \boldsymbol{v} \ge 0を満たす実対称行列XXのことを指します。

    DD⊤DD^\topとD⊤DD^\top Dでは、次の関係が成り立ちます。
    v⊤(D⊤D)v=(Dv)⊤(Dv)≥0\boldsymbol{v}^\top (D^\top D) \boldsymbol{v} =(D \boldsymbol{v})^\top (D\boldsymbol{v}) \ge 0
    v⊤(DD⊤)v=(D⊤v)⊤(D⊤v)≥0\boldsymbol{v}^\top (D D^\top) \boldsymbol{v} =(D^\top \boldsymbol{v})^\top (D^\top \boldsymbol{v}) \ge 0

    また、DD⊤DD^\topとD⊤DD^\top Dはどちらも対称行列です。
    (D⊤D)⊤=D⊤D(D^\top D)^\top = D^\top D
    (DD⊤)⊤=DD⊤(D D^\top)^\top = D D^\top

    DD⊤DD^\topのある固有ベクトルをu\boldsymbol{u}、固有値をλu\lambda_uとすると、次が成り立ちます。
    u⊤ DD⊤u= u⊤(DD⊤u)=λuu⊤u= λu≥0\boldsymbol{u}^\top DD^\top \boldsymbol{u} = \boldsymbol{u}^\top (DD^\top \boldsymbol{u}) = \lambda_u \boldsymbol{u}^\top \boldsymbol{u} = \lambda_u \ge 0

    D⊤DD^\top Dのある固有ベクトルをv\boldsymbol{v}、固有値をλv\lambda_vとすると、次が成り立ちます。
    v⊤ D⊤Dv=(D⊤Dv)⊤ v= λvv⊤v= λv≥0\boldsymbol{v}^\top D^\top D \boldsymbol{v} = (D^\top D \boldsymbol{v})^\top \boldsymbol{v} = \lambda_v \boldsymbol{v}^\top \boldsymbol{v} = \lambda_v \ge 0

    まだ、Σ\Sigmaの中身を説明していませんが、特異値分解の式を使ってDD⊤DD^\topを表現すると以下になります。

    DD⊤=(UΣV⊤)(UΣV⊤)⊤=UΣVV⊤Σ⊤U⊤= UΣΣ⊤U⊤DD^\top = (U\Sigma V^\top)(U\Sigma V^\top)^\top = U\Sigma V V^\top \Sigma^\top U^\top = U\Sigma \Sigma^\top U^\top

    ここでVV⊤=I⏟n×nV V^\top = \underbrace{I}_{n\times n}となることを利用しています。これによって、DD⊤U=  UΣΣ⊤DD^\top U =  U\Sigma \Sigma^\topとなるので、ΣΣ⊤\Sigma \Sigma^\topは、UUの固有値を持つk×kk \times kの対角行列であることがわかります。

    同様に、特異値分解の式を使ってD⊤DD^\top Dを表現すると以下になります。

    D⊤D=(UΣV⊤)⊤(UΣV⊤)=VΣ⊤U⊤UΣV⊤= VΣ⊤ΣV⊤D^\top D = (U\Sigma V^\top)^\top(U\Sigma V^\top) = V\Sigma^\top U^\top U \Sigma V^\top = V\Sigma^\top \Sigma V^\top

    ここでU⊤U=I⏟k×kU^\top U = \underbrace{I}_{k \times k}となることを利用しています。これによって、D⊤DV=  VΣ⊤ΣD^\top D V =  V\Sigma^\top \Sigmaとなるので、Σ⊤Σ\Sigma^\top \Sigmaは、VVの固有値を持つn×nn \times nの対角行列であることがわかります。

    前述したように、これらの固有値は非負の実数なので、その平方根をも実数であり、これを特異値(singular values)と呼びます。この特異値を対角線上に並べたものがΣ\Sigmaです。

    Σ=[σ10⋯0⋯00σ2 ⋯0⋯0⋮⋮⋱0⋯000 ⋯σk⋯0]\Sigma = \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 & \cdots & 0 \\[1ex] 0 & \sigma_2  & \cdots & 0 & \cdots & 0 \\[1ex] \vdots & \vdots & \ddots & 0 & \cdots & 0 \\[1ex] 0 & 0  & \cdots & \sigma_k & \cdots & 0 \\[1ex] \end{bmatrix}

    0で埋めることでk×nk \times nとなり、D=UΣV⊤D = U \Sigma V^\topに対応していますが、実際には行列VVのkk行より下は使われないのと同じなので切り捨てると、Σ\Sigmaをk×kk \times kにできます。

    Σ=[σ10⋯00σ2 ⋯0⋮⋮⋱000 ⋯σk]\Sigma = \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 \\[1ex] 0 & \sigma_2  & \cdots & 0 \\[1ex] \vdots & \vdots & \ddots & 0 \\[1ex] 0 & 0  & \cdots & \sigma_k \\[1ex] \end{bmatrix}

    よって、全体を次のようにコンパクトに表現できます。

    D⏟k×n=U⏟k×k  Σ⏟k×k  V⊤⏟k×n\underbrace{D}_{k \times n} = \underbrace{U}_{k \times k} \; \underbrace{\Sigma}_{k \times k} \; \underbrace{V^{\top}}_{k \times n}

    これによって、大幅な計算量の削減になります。

    繰り返しますが、実装では専用のアルゴリズムを使い、より効率良く計算します。

    元の行列が持つすべての特異値の数(最大でmmかnnか小さい方)から下位の特異値を除く形になっているため、「TruncatedSVD」(切り捨てられたSVD)と呼ばれます。少ない次元でSVDを行うので効率的です。

    さらに、D=UΣV⊤D = U\Sigma V^\topとA≈QDA \approx QDを組み合わせると以下の表現が得られます。

    A≈QD=Q(UΣV⊤)=(QU)ΣV⊤A \approx QD = Q(U\Sigma V^\top) = (QU)\Sigma V^\top

    ここで、QUQUは、UUをk×kk \times kからm×km \times kに線形変換しています。UUは固有値ベクトルを含み、DD⊤DD^\topの分散が最大となる重要な方向性を示します。よって、低次元で重要な方向をkk次元からmm次元で表現し直していることになります。

    つまり、流れとしては、最初にAAをQQでm×km \times k次元に射影(圧縮)し、その中の重要な(分散が最も大きい)軸がUUの中のkk次元ベクトルで表現され、それをQUQUによってm×km \times kとして表現しています。これは、元の行列AAをkk次元の重要な特徴量で近似して表現していることを意味します。

    よって、QUQUの各列ベクトルは、元の行列AAにおける主成分の近似であり、TruncatedSVD によって得られた rank-kkの特徴ベクトルです。

    最後に、実験結果やTruncatedSVDの仕組みの特性から、どの次元削減をいつ使うべきかを考察します。

    どんな時に使うべきか

    結論から言うと、データセットが疎であり、中心化を必要とせず(あるいはもともと中心化されており)、t-SNEやPCAでは時間がかかり過ぎるような場合では、TruncatedSVDを考慮するに値します。

    また、TruncatedSVDとPCAは、基本的には線形変換を行なっているので、特徴量間の関係が非線形な場合には向いていません。

    一方、t-SNEを使う方が良いのは、視覚化が目的であり、ある程度の時間がかかっても問題なく、データセットに主成分の組み合わせで表現できないような非線形な性質がある場合です。

    なので、これら3つの次元削減は用途に合わせて選ぶことになります。

    • PCA:線形なデータ構造を捉えたい。アルゴリズムを自動で選んで欲しい。

    • TruncatedSVD:中心化が不要で、高次元・疎行列の計算時間を短縮したい。

    • t-SNE:データに非線形な構造があり、視覚化を重視。時間を気にしない。

    PCAでとりあえず試して計算時間や次元削減の結果を確認するのがおすすめです。

    次回予告

    これまで、分類・回帰・クラスタリング・次元削減など、scikit-learnを用いた様々な機械学習手法を取り上げてきました。

    これらのモデルの多くは、「ガウス分布」や「ベイズ定理」といった共通の統計的な考え方を持っています。

    そこで次回は、それらを統一的に捉えるための枠組み「ガウス過程」(Gaussian Process)をご紹介します。

    ガウス過程を理解することで、これまで学んできた機械学習アルゴリズムの多くをより深い視点から再解釈することが可能となります。

    お楽しみに!

     
     
    「わかりやすく、具体的に」AIとサイエンスの情報を発信中

    あなたへのおすすめ