Posts

抄訳 Pregel: A System for Large-Scale Graph Processing(2010)

Googleで開発されたPregelは、ソーシャルグラフやハイパーリンクのグラフなどの巨大なグラフデータの処理に適した計算モデルである。 計算モデル自体も、処理対象のデータとおなじく、ワーカーが別のワーカーとのメッセージの送受信を繰り返すグラフ構造をなす。 このモデルのオリジナルは、以前紹介したValiantのBulk Synchronous Parallel model(BPS)である。 BPSは時間を一定間隔に区切り、次の間隔が始まる時点で、それまでのメッセージの送受信が全て成功していることを保証する。 間隔の中で、コンポーネントは別のコンポーネントにメッセージを送信する。 間隔を過ぎたとき、失敗した処理や未送信のあるコンポーネントがあれば、成功するまで計算を再実行させる。 Pregelでは、この間隔をsuperstepとよび、グラフ上の点であるワーカーがコンポーネントにあたる。

Normalized Cuts and Image Segmentation (2000)

単純無向グラフのクラスタリングを応用して画像をセグメントに分割する。 カットの評価基準としてnormalized cutとその近似解を求め方を提案した。 Normalized cutが最小値のとき、異なるサブグラフにあるノード間の類似度は最小に、同じサブグラフにあるノードの類似度は最大になる。 Normalized cutをレイリー商に変形し、固有値問題をとくことで、Normalized cutの最小値の近似解を求める。

Understanding diagnostic tests3: receiver operating characteristic curves(2007)

医学では陰性と陽性を区別する分割点をカットオフポイントと呼ぶ。 ROC曲線は、縦軸を感度(sensitivity)TP/(FN+TP), 横軸を1-特異度(specificity)1 - TN/(TN+FP)とするグラフで、この2値はトレードオフの関係にある。 トレードオフのもとでカットオフポイントの決める方法を先行研究から2つ紹介している。

抄訳 The Transaction Concept: Virtues and Limitations(1981)

トランザクションのコミットとロールバックの2通りの実装方針を提案している。 1つは、オブジェクトの値とその値の有効期間を記録し、値の履歴を管理する。 もうひとつは、ログとロックを利用した実装で、操作時にUNDOログとREDOログを出力する。 ロールバック時には、ログをもとにコミット開始前の状態にシステムを復元する。 UNDOやREDOを再実行可能でなければならず、そのためにオブジェクトにしばしばバージョンをつけることがある。 2つの実装方針は異なるように見えるが、内部の実装は似かよったものになる。

On Spectral Clustering: Analysis and an algorithm

スペクトラルクラスタリングは、類似度を辺の重みとするグラフをデータから構築し、重みをもとにカットする辺を決めて、データをクラスタに分ける。 グラフラプラシアンのようなグラフを表現した行列をつくり、その固有ベクトルを求め、固有ベクトルを列ベクトルとして並べた行列にK-meansを適用する。 もとのデータに二重丸のような凸集合でないクラスタがあるときに、最初からK-meansを適用するよりも良い結果を期待できる。 また、データ分布に確率モデルにあてはめ、どのクラスタにデータを割りあてるか確率的に決めるクラスタリングと違い、データの分布を仮定しなくてよい。

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs(1979)

プロセッサは、高速化のためにソースコードと違う順序で命令を実行することがある。 順序の入れ換えが実行結果に影響しなければ、プロセッサは逐次的であるという。 マルチプロセッサに期待する実行結果は、各プロセッサがソースコードの順序で命令を実行し、かつ、全プロセッサの命令がある順序で逐次的に実行されるときの結果である。 任意のプログラムで実行結果が等しいならば、そのマルチプロセッサには逐次一貫性がある。 プロセッサがメモリ上のデータを共有する場合、各プロセッサが逐次的でも、マルチプロセッサが逐次一貫になるとは限らない。 マルチプロセッサが逐次一貫であるには、各プロセッサがソースコード通りの順序でメモリにリクエストを送り、メモリは各セルへのリクエストを到着順(FIFO)に処理しなければならない。

A Min-max Cut Algorithm for Graph Partitioning and Data Clustering

重みつき隣接行列で表した無向グラフを2分割するクラスタリングであり、グラフ間の類似を最小化し、グラフ内のノードの類似の最大化をはかる。 隣接行列を\(W_{uv}\), \(\text{cut}(A, B)=W(A, B)\), \(W(A, B) = \sum_{u\in A, v\in B}W_{uv}\)として、以下の目的関数を最小化する分割を探索する。 ノードを2つに分ける最適解はNP完全であるため、近似解をもとめる。 $$ \text{Mcut} = \frac{\text{cut}(A, B)}{W(A)} + \frac{\text{cut}(A, B)}{W(B)} $$

Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial

サーバのレプリケーションによってフォールトトレランスを高めることができるが、レプリケーション間の合意形成のプロトコルが必要になる。 そこで、ステートマシンをモデルにプロトコルを定義する手法を、Fail Stopとビザンチン将軍問題で例示する。 ステートマシンは、状態変数を決定的に変更するコマンドからなり、入力系列のみから出力が決まる。 モデルは、複数のステートマシンを同じ初期状態から開始し、同じ入力を与え、出力の合意をはかる。

LEAST ANGLE REGRESSION

Least Angle Regression(LARS)はLASSO回帰のアルゴリズムで、目的変数の値とモデルの推定値の残差と相関の大きい入力変数をひとつずつモデルに取り込む。 ベクトル間の相関が大きいほど間の角度が小さくなるため、least angle(最小角)と名がつく。 初期状態のモデルは説明変数をもたず推定値は0である。 そのため、目的変数との相関が最大の説明変数を最初にモデルに取り込む。 次に、別の説明変数と残差の相関が取り込んだ説明変数の相関と等しくなるまで、取り込んだ説明変数の方向に、出力する推定値を更新する。 以降は、取り込んだすべての説明変数から等角度の方向に、取り込んでいない説明変数と残差の相関が取り込んだ説明変数との相関と等しくなるまで、モデルの推定値を更新する。 説明変数\(\boldsymbol{x}_1\), \(\boldsymbol{x}_2\)と目的変数\(\boldsymbol{y}\)で更新の様子を説明する。 初期状態の推定値\(\hat{\boldsymbol{\eta}}_0\)では、\(\boldsymbol{x}_2\)よりも\(\boldsymbol{x}_1\)のほうが\(\boldsymbol{y}-\boldsymbol{\hat{\eta}}_0\)と相関がある。そこで、\(\boldsymbol{x}_1\)を最初にモデルに取り込む。 \(\boldsymbol{x}_1\)の方向に\(\boldsymbol{\hat{\eta}_1}\)まで更新すると、\(\boldsymbol{x}_1\)と\(\boldsymbol{x}_2\)は、残差\(\boldsymbol{y}-\boldsymbol{\hat{\eta}}_1\)との相関が等しくなる。 そして今度は、\(\boldsymbol{x}_1\)と\(\boldsymbol{x}_2\)と等角度の方向に\(\boldsymbol{\eta}_2\)まで更新する。 論文へのリンク 引用元の画像が荒いため、画像は、スモールデータ解析と機械学習から引用しました。

Consensus in the Presence of Patial Synchrony (1988)

同期的なシステムには、プロセッサ間のメッセージの到達時間や時刻の誤差に有界がある。 非同期的なシステムには、どちらの有界もない。 表題のpartial synchronousは、同期、非同期の中間的な環境である。 到達時間や時刻の誤差の有界について、存在するが値が分からない環境と、値が分かっているがどの時刻から値が保証されるか分からない環境を意味する。