構造学習

機械学習技術 自然言語技術 人工知能技術 デジタルトランスフォーメーション技術 関係データ学習 機械学習アルゴリズムとデータ構造 本ブログのナビ

構造学習について

データが持つ構造を学習することは、そのデータが何であるかという解釈を行う上で重要なものとなる。構造学習の中で最もシンプルなもは、階層的なクラスタリングであり、決定木による学習の基本的な機械学習アルゴリズムとなる。さらにデータ間の関係性を学習する関係データ学習や、グラフ構造学習、疎構造学習等がある。

本ブログではこれらの構造学習に関して以下の項目について述べている。

実装

• 構造学習の概要と各種適用事例および実装例

構造学習(Structural Learning)は、機械学習の一分野であり、データの構造や関係性を学習する手法を指し、通常、教師なし学習や半教師あり学習の枠組みで使用されるものとなる。構造学習は、データの中に存在するパターン、関係性、または構造を特定し、それをモデル化し、データの背後にある隠れた構造を明らかにすることを目的としている。構造学習は、グラフ構造、木構造、ネットワーク構造など、さまざまなタイプのデータ構造を対象としている。

ここでは、この構造学習に関して様々な適用事例と具体的な実装例について述べている。

• 時間と共に変化していくグラフデータを解析する手法について

時間と共に変化するグラフデータを解析する手法は、ソーシャルネットワーク分析、ウェブトラフィック分析、バイオインフォマティクス、金融ネットワークモデリング、交通システム解析など、さまざまなアプリケーションに適用されている。ここではこの技術の概要とアルゴリズム及び実装例について述べている。

• スナップショット解析による時間的な変化を考慮に入れるグラフデータ解析

スナップショット解析（Snapshot Analysis）は、データの異なる時間点でのスナップショット（瞬間のデータスナップショット）を使用して、時間的な変化を考慮に入れたデータ解析の手法となる。この手法は、時間に関する情報を持つデータセットを分析し、そのデータの時間的なパターン、トレンド、および変化を理解するのに役立ち、グラフデータ解析と組み合わせることで、ネットワークや関係性データの時間的な変化をより深く理解することができるようになる。ここでは、このアプローチの概要とアルゴリズム及び実装例について述べている。

• ダイナミックコミュニティ分析について

ダイナミックコミュニティ分析（Dynamic Community Detection）は、時間に関連する情報を持つネットワーク（ダイナミックネットワーク）内で、コミュニティ（モジュールまたはクラスタ）の時間的な変化を追跡および解析するための手法となる。通常、ノードとエッジが時間に関連した情報を持つグラフデータ（ダイナミックグラフ）を対象としており、この手法は、さまざまな分野で応用され、例えばソーシャルネットワーク分析、バイオインフォマティクス、インターネットトラフィックモニタリング、金融ネットワーク分析などで利用されている。

• ダイナミック中心性指標による時間的な変化を考慮に入れるグラフデータ解析

ダイナミック中心性指標（Dynamic Centrality Metrics）は、時間的な変化を考慮に入れたグラフデータ解析の一種であり、通常の中心性指標（例: 次数中心性、媒介中心性、固有ベクトル中心性など）は、静的なネットワークに適しており、ネットワーク内のノードの重要性を単一のスナップショットで評価するものとなる。しかし、実際のネットワークは時間に関連する要素を持つことが多いため、ネットワークの時間的な変化を考慮することが重要となる。

• ダイナミックモジュール検出による時間的な変化を考慮に入れるグラフデータ解析

ダイナミックモジュール検出は、時間的な変化を考慮に入れたグラフデータ解析の手法の一つであり、この手法は、ダイナミックネットワーク内でコミュニティ（モジュール）の変化を追跡し、異なる時間スナップショットでのコミュニティ構造を特定するものとなる。ここではダイナミックモジュール検出に関する詳細とその実装例についての情報を示す。

• ダイナミックグラフ埋め込みによる時間的な変化を考慮に入れるグラフデータ解析

ダイナミックグラフ埋め込み（Dynamic Graph Embedding）は、時間的な変化を考慮に入れるグラフデータ解析のための強力な手法となる。このアプローチでは、グラフデータが時間に沿って変化する場合、ノードやエッジの表現を時間軸上で持つことを目的としている。

• テンソル分解法によるダイナミックモジュール検出について

テンソル分解法（Tensor Decomposition）は、高次元のテンソルデータを低ランクのテンソルに近似する手法であり、この手法は、データの次元削減や特徴抽出に使用され、機械学習やデータ解析のさまざまなアプリケーションで有用なアプローチとなる。ダイナミックモジュール検出にテンソル分解法を適用することは、時系列データや動的なデータモジュールの検出といったタスクに関連する。

• ネットワークアライメントによる時間的な変化を考慮に入れるグラフデータ解析

ネットワークアライメントは、異なるネットワークやグラフ間で類似性を見つけ、それらをマッピングし合わせる技術であり、時間的な変化を考慮に入れるグラフデータ解析にネットワークアライメントを適用することで、異なる時間スナップショットのグラフを対応付け、その変化を理解することが可能とするものとなる。

• 時間予測モデルを用いた時間的な変化を考慮に入れるグラフデータ解析

時間予測モデルを用いた時間的な変化を考慮に入れるグラフデータ解析は、グラフデータ内の時間的なパターン、トレンド、予測を理解するために使用される。ここではこのアプローチについての詳細について述べる。

• 大規模グラフデータのサブサンプリングについて

大規模グラフデータのサブサンプリングは、グラフの一部をランダムに選択することで、データのサイズを削減し、計算およびメモリの使用量を制御するもので、大規模なグラフデータセットを扱う際に、計算効率を向上させるためのテクニックの一つとなる。ここでは、大規模グラフデータのサブサンプリングに関するいくつかのポイントとテクニックについて述べる。

• タイムライン上でグラフスナップショットを表示したり、アニメーション化する手法

タイムライン上でグラフスナップショットを表示したり、アニメーション化することは、時間的な変化を視覚化し、グラフデータの動的な特性を理解するのに役立ち、グラフデータを解析する上で重要な手法となる。ここではこれらに用いられるライブラリ及び実装例について述べている。

• NetworkXとmatplotlibを組み合わせたグラフのアニメーションの作成について

Pythonでネットワークの動的な変化を視覚的に表現するための手法であるNetworkXとMatplotlibを組み合わせたグラフのアニメーションの作成について述べる。

• 高次元のデータを次元削減技術（例: t-SNE、UMAP）を使用して低次元にプロットし、可視化を容易にする手法について

高次元のデータを次元削減技術を使用して低次元にプロットし、可視化を容易にする手法は、データの理解、クラスタリング、異常検出、特徴量選択など多くのデータ分析タスクで有用となる。ここでは主要な次元削減技術とその手法について述べる。

• Gephiを用いたデータの可視化について

Gephiは、オープンソースのグラフ可視化ソフトウェアで、ネットワーク分析や複雑なデータセットの可視化に特に適したツールとなる。ここではGephiを使用してデータを可視化する基本的なステップと機能について述べる。

• Cytoscape.jsを用いたデータの可視化について

Cytoscape.jsは、JavaScriptで書かれたグラフ理論ライブラリであり、ネットワークやグラフデータの可視化を行うために広く使用されているものとなる。Cytoscape.jsを使用することで、ウェブアプリケーションやデスクトップアプリケーションに対してグラフやネットワークデータの可視化を追加することが可能となる。ここではCytoscape.jsを用いたデータの可視化に関する基本的なステップとコードの例を示す。

• Sigma.jsを用いたグラフデータの可視化について

Sigma.jsは、Webベースのグラフ可視化ライブラリで、対話的なネットワーク図を作成するのに役立つツールとなる。ここではSigma.jsを使用してグラフデータを可視化するための基本的な手順と機能について述べる。

• 機械学習における類似度について

類似性（similarity）は、二つ以上のオブジェクトや事物が共通の特徴や性質を持ち、互いに似ていると見なされる程度を表す概念であり、比較や関連性の観点からオブジェクトを評価したり、分類やグループ化を行ったりする際に重要な役割を果たしている。ここでは、様々なケースでの類似度の概念と一般的な計算方法について述べている。

技術トピック

• 具体と抽象と言葉の構造

我々のまわりの世界はつきつめると「具体」と「抽象」という2つの対立概念から成り立っている。「具体」という言葉がもっとも用いられるのは、何かをわかりやすく説明するときに「具体的に言うと…」とか、相手の話がわからないときに「もう少し具体的に話してもらえませんか?」のような場合となる。逆に「抽象」という言葉は「あの人の話は抽象的でわからない」といった文脈となる。

このように「具体=わかりやすい」「抽象=わかりにくい」というのが一般的に認知されているこれらの概念の印象となる。このように「抽象」という言葉は負の印象をもたれることがや多いが、実際は人間の思考の基本中の基本であり、人間を人間たらしめ、動物と決定的に異なる存在としている概念でもある。

• Rのhclustを用いた階層クラスタリング

Rを使った階層クラスタリングについて述べる。

• 階層k-meansの画像検索への応用

クラス認識は対象物体の属するクラスを予測することになるが、インスタンス認織は対象物体そのものを特定するタスクとなる。インスタンス認織の中心となる課題として、入力画像からデータベース内の画像をすばやく探す画像検索問題がある。インスタンス認識(instance recognition)は、東京タワーを見て電波塔と認織するのではなく、東京タワーとして認織するような対象物体そのものを特定するものとなる。これらは、入力画像内の物体と同じ物体が写る画像をデータベースから探し出すことで実現できる。

インスタンス認織の実現方法は以下のようになる。1蓄積された画像群から局所特徴を抽出し、画像データベースを作成する、2クエリ画像の局所特徴を抽出する、3クエリ画像の局所特徴を一つ取り上げ、画像データベースの全局所特徴と比較する。もっとも類似した局所特徴を持つデータベース内の画像に1票投じる。この投票を入力画像がもつ局所特徴全てに行う、データベース内で最も票を獲得した画像の物体を、クエリ画像の物体として認識する。

• 解釈可能なモデルとしての決定木

決定規則は、条件(前提とも呼ばれる)と予測値からなる単純なIF-THEN文となる。例えば、今日雨が降っていて4月であるならば(条件)、明日あめが降るだろう(予測)というものになる。予測は単一の決定規則もしくは、いくつかの決定規則の組み合わせで行われる。

データから規則を学習する方法として以下の3つが挙げられる。(これら以外にもたくさん存在する)

1. 1. 1. OneR: 単一の特徴量から規則を学習する。OneRの特徴は、単純かつ理解しやすいことにある。
      2. Sequential covering: 繰り返し規則を学習していき、新しい規則でカバーされるデータ点を削除するという手法。
      3. Bayesian Rule Lists: ベイズ統計を用いて、あらかじめ発見された頻出パターンを決定リストに統合する。事前に発見されたパターンを使用することも、多くの規則を学習するアルゴリズムでよく使われるアプローチとなる。

• 決定木アルゴリズム概要

決定木学習器は、フューチャーとして得られる可能性のある結果の関係をモデリングするために、木構造(tree structure)を使う強力な分類器となる。

決定木アルゴリズムの大きな特徴は、フローチャート風の木構造が必ずしも学習器内部専用になるわけではなく、モデルの出力結果を人間が読んで、特定のタスクのためにモデルが上手く機能する(あるいはしない)理由やメカニズムについて大きなヒントになるところにある。

このような仕組みを用いることで、法的な理由で分類メカニズムが透明なものでなければならない場合や、組織間での商慣行を明示するために他者と結果を共有する場合に特に有効になる。

• 集団学習と決定木(ランダムフォレスト)

特徴空間においてデータが複雑に分布している場合、非線形な分類器が有効となる。非線形な分類器を構成するには、カーネル法やニューラルネットワークなどを利用した手法が挙げられる。ここでは単純な分類器を複数組み合わせることで、非線形な分類器を構成する集団学習(ensemble learning)について述べる。なお、集団学習はアンサンブル学習とも呼ばれている。

集団学習として、訓練データ集合からサブセットを生成し、各サブセットで予測器を学習させるバギングについて述べる。この手法は、とくに不安定な学習アルゴリズムに有効となる。不安定な学習アルゴリズムとは、訓練データ集合の小さな変化が、学習される予測器の構造やパラメータに大きな影響を与えるアルゴリズムのことを言う。不安定な学習アルゴリズムとして、ニューラルネットワークや決定木がある。

有限なデータ集合から多様なサブセットを生成する手法として、ブートストラップ法が(bootstrap method)がある。これは、データ集合からランダムに復元抽出をM回繰り返すことで、M個の新規なデータ集合を生成する手法となる。

• 階層的なトピックモデル

客観的に見ると、言語とは記号列だと考えることができる。細かく見るとそれは文字からなっているが、ここでは英語の様に、言葉は単語からなっているとして話を進める。

言語の単語列を見てすぐにきづくことは、単語の頻度には大きな偏りがあるというものになる。ここで、単語の順位と頻度が反比例関係にあることはZipfの法則といわれ、1930年台に発見された基本的事実の一つとなる。これは近年では言語を超えて、自然界の多くの離散的現象に共通する冪乗法則として知られる様になっている。

この様な不確定性を表現するには、p自体の場所についての確率分布が必要になる。その最も簡単なものとして以下の式の様なディリクレ分布がある。

• 関係データ学習

関係データとは、最も単純な場合、N個のオブジェクトがあったときに、その中の任意のペアに対してどのような「関係」が存在するかを表すデータとなる。ここで「何か」と「何か」の関係を表す形として行列を考えると、関係性を表すデータは行列の中の要素そのものとなる。

関係データ学習とはこの行列の中のパターンを抽出するものとなり、適用されるタスクとしては大きく分けて、「予測(prediction)」と「知識抽出(knowledge xtraction)」の2つがある。

予測問題とは、観測データから学習、設計された統計モデルを用いて未観測のデータの値を推定する問題で、典型的な予測問題として、関係ネットワーク内に存在するリンクの有無の推定(リンク予測(link prediction)問題)や、購買データを用いユーザーごとのアイテム購入(adoption)確率推定等がある。これらは関係データ行列の欠損値を予測する問題として実現が可能となる。また、ネットワーク内の情報伝搬(information dissemination)あるいは情報拡散(information diffusion)の推定も予測問題の重要な例となる。

知識抽出問題とは、グラフ特徴を計算することで関係データ自体の特性を解析することや、与えられた観測データを適切にモデリングすることによって何らかの有用な知見や知識につながる情報を抽出することを目的に行われるもので、具体的なタスクとしてはネットワーク内のコミュニティ抽出や、広義のクラスタリング等がある。

本ブログでは、以下のページでこの関係データ学習に対して、理論的概要、具体的なアルゴリズムとさまざまな応用に関して述べている。

• グラフニューラルネットワーク

グラフデータに対して深層学習を行うフレームワークであるグラフニューラルネットワーク技術の概要。化合物の物性推定やAtttensionを使った自然言語処理、共起ネットワーク、画像情報処理等に活用される

• その他に該当するデータに対するSVMでのアプローチ

物体検出では、人や車などの物体を取り囲む四角い領域を画像中かに発見することを目的としている。物体検出の多くの手法では、物体領域候補を複数提案し、物体クラス認識の手法を用いて、それらの領域がどの物体に分類されるのかを判断する。画像から提案される物体領域候補は膨大となる場合が多く、物体クラス認識では計算コストの低い手法がよく利用される。

画像から物体領域候補を提案する手法としては、スライディングウィンドウ法、選択検索法、分岐限定法がある。またそれらを分類する手法としてはExampler-SVM、ランダムフォレスト、R-CNN(regious with CNN feature)等がある。

• グラフィカルlassoを用いたグラフの疎構造学習

関係性にスパース性を導入したグラフィカルlasso(ガウス型グラフィカルモデルの疎構造学習)とその活用として異常検知への適用(ホテリングT2スコアの拡張)について述べる。

• 関係性へのスパース性の導入

データがスカラーの出力yとM次元ベクトルxの組でD={(y⁽ⁿ⁾,x⁽ⁿ⁾)|n=1,…,N}のように与えられている時、線形回帰としてスパースな解を実現する(回帰係数をスパースにしたり、変数ではなく、余分な標本を消すと言う意味でのスパース化を行う)ことについて述べる。

ユースケースとしては観測データがノイズで汚染されており、必ずしもすべての標本が信用できないと言う場合や、グラフデータに拡張して、ある機械を決まった数のセンサーで常時監視するような場合等のグラフモデル(関係モデル)への適用について述べる。

• Poisson-Gammaモデルによるクラスタ推定

特定の集団における健康関連事象の頻度や分布を調査し、その要因を解明し、かつ研究成果を健康問題の予防やコントロールに適用する学問を疫学(epidemiology)という。特に空間データを用いる疫学研究は空間疫学(spacial epidemiology)と呼ばれ、地図や位置情報を用いることから地理情報システム(GIS)との関連も深い研究分野として注目されている。

ここで、都道府県や保健所管轄などの、ある地域単位で集計されたデータを扱う場合、単に観測数のみを考えれば、その数は当然人口の多胎地域ほど多くなる傾向となる。また疾病によっては地域住民の年齢構成が影響を与える場合もあり、単純な観測数やその地域の人口で割った人口あたりの観測数で比較しても不十分な場合もある。そのために、人口の違いとともに、年齢等の影響を取り除くために標準化されたリスク指標を用いた疾病地図がよく利用される。それらの中で代表的なものとして、間接法とよばれる標準化羅病比(Standard Morbility Ratio;SMR)などが用いられる。

さらに地域間の比較を目的とした場合、その地域のリスク指標の推定精度を考慮するため、ベイズ推定値が用いられることもある。ここでは都道府県、保健所管轄単位の所持者数データに対し、日本全国を基準集団として年齢構成を調整したSMRのPoisson-Gammaモデルによる経験ベイズ推定値を求めた。

• 複雑ネットワークとは何か 複雑な関係性を読み解く新しいアプローチ 読書メモ

「友だちの元カレは私の元カレだった！」たった6人をたどるだけで世界中の誰にでも行き着けるスモールワールド。「複雑ネットワーク」は21世紀最大のキーワード。複雑に見える身の回りの現象も「複雑ネットワーク」の考え方を応用すれば単純な関係に置き換えることができる。伝染病やコンピューター・ウイルスの感染経路、ニューロンやタンパク質の情報伝達の方法、会社や社会の中の人間関係に「意外な法則」が見えてくる

• 疎構造学習による異常検知 – 変数同士の依存関係の崩れを異常と結びつけるグラフモデルとL1正則化

多変量の変数で表される系の監視業務などでは、個々の異常現象に対する各変数の寄与度を知ることが重要になる。単純ベイズ法のようなある意味極端な方法を除き、それを行うための手段は多くない。ここでは、変数同士の依存関係の崩れを異常と結びつけるという考え方に基づき、個々の変数の異常度を計算する手段について述べる。変数同士の依存関係を学習するにあたっては、本質的な依存関係を効率よく抽出できるように算法を工夫する。それにより、見かけ状の次元が高くても、系に内在するモジュール構造を自動的に抽出することが可能となる。

• 密度比推定による異常検知 – カルバック・ライブラー密度比推定法を用いた教師なしデータからの異常推定

今回は「正常であるとわかっているデータをもとに、異常標本が含まれるかもしれないデータの中から異常標本を見つけ出す」という問題について述べる。これは基本的には外れ値検出の問題となるが、異常度を計算する標本をバラバラに扱うのではなく、あえてデータ集合全体の確率分布を考え、それに対する確率密度比の推定問題として定式化する。この定式化の主な利点は、異常検知モデルに含まれるパラメータの系統的な決定方法が得られること、個々の標本に乗るノイズの悪影響をある程度抑制することで検出精度の向上が見込めることにある。

• 密度比推定による変化検知 – カルバック・ライブラー密度比推定法を用いた構造変化の検出

今回は、恣意的な分布の仮定を行わずに、密度比の直接推定により変化検知を行う手法について述べる。変化検知は分布全体の変化の有無をマクロ的に調べる問題だが、それに加えて、ミクロ的に変数同士の個々の依存関係の変化を見るという問題も同じ枠組みで扱う事ができる。構造変化検知という問題設定は、複雑な系の監視のための有力な手段として近年注目されている。

変化検知問題における確率分布の役割を強調して、特に分布変化検知(distributional cahnge detection)の問題と呼ぶ事がある。いわゆる検定論の枠内に落とし込まないことを除けば、統計学における2標本検定(two-sample test)と問題設定は同様になる。

変化度の定義は、分布同士の相違度をカルバック・ライブラー・ダイバージェンスで測るのと厳密に同じとなる。カルバック・ライブラー・ダイバージェンスは、2つの分布の相違度を測る尺度となる。

• 部分-全体関係の学習法

部分-全体関係は多くの領域で重要であるが、通常、包摂関係ほど注目されていない。本論文では、部分-全体関係を見つけるための方法を説明する。本手法は2つのステップから構成される。(i)明示的および暗黙的な部分全体関係に対するフレーズパターンを見つける、(ii)これらのパターンを部分全体関係インスタンスを見つけるために適用する。本手法を発がん性物質の発生源探索のドメインに適用した結果を示す。発がん性物質の発生源の探索

• 構造化サポートベクトルマシン

SVMによって構造を持つデータを予測することは、構造サポートベクトルマシンという拡張を利用することでできる。この手法では、複雑な構造を導入することで増加する制約条件を切除平面ほうと呼ばれる最適化手法で効率的に扱うことができる。構造型データは例えば木構造や配列として表現されたデータがある。自然言語処理における構造木予測では各単語間の文法上の関係が木構造として表現される。あるいは、タンパク質の類似配列検索の問題ではタンパク質をアミノ酸の配列として表現することがある。

• グラフィカルモデルの構造学習

今回は、グラフ構造そのものをデータから学習する方法について述べる。具体的なアプローチとしてはベイジアンネットワークやマルコフ確率場でグラフ構造をデータから学習する方法で、Max-Min Hill Climbming(MMHC)、Chow-Liuのアルゴリズム、スコア関数を最大化する方法、PC(Peter Spirtes and Clark Clymoir)アルゴリズム、GS(Grow-Shrink)アルゴリズム、SGS(Spietes Glymour and Scheines)アルゴリズム、スパース正則化、独立性条件等がある。