ニュース

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

マシンハートレポート

編集者: ジアチー

マトリックスはわかりにくいですが、別の視点から見ると違うのかもしれません。

数学を学ぶとき、私たちは学んだ知識の難しさや抽象性にイライラすることがよくありますが、視点を変えるだけで問題に対するシンプルで直感的な解決策を見つけることができることがあります。たとえば、私たちが子供の頃に二乗和 (a+b)² の公式を習ったとき、それがなぜ a²+2ab+b² に等しいのか理解できなかったかもしれません。この本を読んで、先生は私たちにこのように覚えておいてくださいと言いました。

それを幾何学的な観点から理解できることに突然気づきました。

ここで、この啓発的な感覚が再び起こります。非負行列は、対応する有向グラフに等価的に変換できるのです。

以下の図に示すように、左側の 3×3 行列は、実際には右側の 3 つのノードを含む有向グラフとして等価に表すことができ、この表現は行列理論とグラフ理論の両方に非常に役立ちます。

この例は、誰もが数学を利用できるようにすることに尽力している数学者の Tivadar Danka によるものです。自称「混沌とした善良な」数学者は、一連のツイートやブログ投稿で、行列とグラフのこの等価性とその使用法を生き生きと紹介しました。これまでのところ、これらのツイートは 200 万回以上読まれ、3,200 件以上のリツイートと 9,100 件以上のお気に入りを獲得しています。

行列と有向グラフの価数

上の例に示すように、各行をノードとして扱う場合、各要素は有向で重み付けされたエッジとして表すことができます。もちろん、0 要素は無視できます。要素が行 i、列 j に位置する場合、それはノード i からノード j までのエッジに対応します。

一見、これは複雑に見えるかもしれませんが、ノードの 1 つを確認することから始めることができます。

図に示すように、この 3×3 行列の場合、行 1 は最上位のノード (ここではノード 1 と呼びます) に対応します。このノードには 3 つの要素が含まれていますが、そのうちの 1 つは 0 であるため、ノードは 2 つの側面に広がります。黄色のエッジは (1,1) の要素 0.5 を表すため、重み 0.5 でそれ自体を指す有向エッジです。同様に、青いエッジはノード 2 を指すエッジで、重みは 1 です。

このようにして、行列の i 番目の列が i ノードを指すすべてのエッジに対応していることを分析できます。

この同等の表現はどのような用途に使われるのでしょうか?

非負行列と有向グラフのこの等価性は、行列とその演算をより深く理解するのに役立つだけでなく、一部の計算プロセスを簡素化するのにも役立ち、ひいてはグラフを新しい視点から理解するのにも役立ちます。

たとえば、行列のべき乗はグラフ内のウォークに対応します。

上の図に示すように、n×n 正方行列 A の k 乗について、各要素の合計プロセスには、考えられるすべての k ステップ ウォークが含まれます。

たとえば、上記の 3×3 行列を 2 乗したいとします。

行列の乗算を使用する場合は、次のように計算する必要があります。

演算結果の最初の要素については、結果 = 0.5×0.5+1×0.2+0×1.8 = 0.45 が得られます。最後に、次のように完全な結果を取得できます。

ただし、上記のグラフウォーキング方法を使用すると、パスを歩くことで結果を得ることができます。同様に、結果行列の最初の要素については、a_{1,l}→a_{l,1} に適合する 2 段階の歩行経路をすべて合計する必要があります。

ただし、この有向グラフがマルコフ連鎖の状態を表す場合、その遷移確率行列の二乗は本質的に、連鎖が 2 ステップ後に特定の状態に到達する確率を表します。

それだけでなく、行列をグラフとして表すことで、非負の行列の構造についての洞察も得られます。これを行うには、まず「強く接続されたコンポーネント」の概念を理解する必要があるとダンカ氏は言いました。

強く結合したコンポーネント

強結合成分とは何ですか?有向グラフの場合、グラフ内の他のすべてのノードにすべてのノードから到達できる場合、グラフは強く接続されていると言えます。以下に示すように。

強接続成分とは、強い接続性を実現できる有向グラフ内の部分/部分グラフを指します。以下の図に示すように、左右には強連結成分が存在しますが、中央の白いエッジはどの強連結成分にも属していません。

以下の図は別の例を示しています。ここでは、黄色の部分が強結合コンポーネントです。

強く接続されたグラフに対応する行列は既約行列ですが、非負行列内の他のすべての行列は既約行列です。

ダンカさんが例を挙げて説明します。 (説明を簡単にするため、例のすべての重みは単位重みですが、実際にはこれらの重み値は負でない任意の値にすることができます。)

次に、このグラフには、強く接続されたコンポーネントが含まれていますが、それ自体は強く接続されていないため、対応する行列形式に転写されます。

そして、この行列は可約行列です。

主対角線上の 2 つの部分行列はそれぞれ 2 つの強連結成分を表し、右上の部分行列は最初の強連結成分から 2 番目の強連結成分へのエッジを表し、左下の部分行列は を表していることがわかります。 2番目の強連結成分から1番目の強連結成分までのエッジを表します(そのようなエッジは存在しないため、すべて0になります)。

ブロック行列を記述するこの形式は、フロベニウス正規形式と呼ばれます。

したがって、当然のことながら、「非負行列をフロベニウス正準行列に変換できるか?」と尋ねます。

有向グラフを使用して非負行列を表すと、答えが「はい」であることが簡単にわかります。非負行列を表す有向グラフは、互いに接続された強連結成分として表すことができるためです。プロセスは非常に簡単です。

1. 非負行列に対応する有向グラフを構築します。
2. 強く接続されたコンポーネントを見つけます。
3. 各ノードにラベルを付けるより良い方法を見つけてください。

これで完了です!

グラフを使用してフロベニウスの標準形式を取得する

それで、これより良い方法は何でしょうか？

上記の例に基づいて、プロセスを見てみましょう。

まず、以下の図に示すように、強く接続された個々のコンポーネントが 1 つのオブジェクトに融合されます。現時点では、強く接続された各コンポーネントをブラック ボックスとして扱うことができます。内部構造は気にせず、外部接続のみを気にします。

次に、この新しいグラフで、出力エッジのみを持ち、入力エッジを持たないコンポーネントを見つける必要があります。この特定の例では 1 つだけあり、番号 0 とラベル付けします。

次のステップはさらに面倒です。各コンポーネントの番号が番号 0 から最も遠くなるように、各コンポーネントに番号を付けます。次の例は、この点をより明確に示しています。

番号 0 から中央のコンポーネントまでのパスが 2 つあることがわかります。そのため、番号を付けるには 0 から最も遠いパスを選択します。最終的に得たのは:

実際には、これによりコンポーネントの順序が定義されます。次に、各コンポーネントの内部ノードをマークします。

グラフ自体が行列に由来する場合、そのような再ラベル付けプロセスによりフロベニウス正準行列が生成されます。

実際、この再ラベル付けプロセスは、置換行列 P を使用して元の行列を変換することであり、置換行列は複数の転置行列の積で構成されます。

以下は定理の完全な形式です。

もちろん、グラフを使用して行列を表現することはこれにとどまりません。たとえば、行列の固有値を使用してグラフの固有値を定義することもできます。実際、この考え方からスペクトル グラフ理論という研究分野が生まれました。

結論

行列とグラフの間のこの等価関係は、グラフ理論の研究に役立つだけでなく、線形代数の計算と解析に新しい視点を提供することは明らかです。たとえば、DNA データは行列やグラフの形式で表現されることがよくあります。

さらに、現在の大規模モデル AI にとって行列演算の重要性は誰もが知っており、ナレッジ グラフで表されるグラフは、検索強化検索などの技術を通じて現在の AI の重要な推進力になりつつあります。この 2 つを結び付けることで、AI の解釈可能性とグラフ人工知能に新たなブレークスルーがもたらされる可能性があります。少なくとも、これは線形代数をより良く学ぶのに役立ちます。

実際、上記の内容は Tivadar Danka が執筆中の書籍「Mathematics of Machine Learning」から抜粋したものです。本書は、機械学習に関する数学的知識を簡単なレベルから深いレベルまで紹介しており、機械学習とは何なのか、なぜ行われるのかを読者が真に理解できるようにするものであり、ダンカ氏は「機械学習を学ぶための最良のリソース」であると自信を持って断言する。現在、彼は 2 つの章のプレビューをオンラインで公開しています。興味のある読者は https://tivadardanka.com/mathematics-of-machine-learning-preview/ にアクセスしてください。