抄訳 SMOTE: Synthetic Minority Over-sampling Technique(2002)
SMOTEはオーバーサンプリングで不均衡データの予測性能の向上をはかる。 少数クラスのサンプルからk近傍にあるサンプルのうち1つをランダムに選ぶ。 もとのサンプルと選ばれたサンプルの各特徴の差に[0,1]区間のランダムな値を掛け、その値をもとのサンプルに足して、少数クラスのサンプルを合成する。
Posts
抄訳 Kafka: a Distributed Messaging System for Log Processing (2011)
Kafkaは、LinkedInで開発された分散メッセージングサービスである。 配信モデルはpullベースであり、consumerが、メッセージをリクエストし、メッセージを消費するスループットを制御する。 consumerは、関心のあるメッセージのストリームであるトピックを作る。 producerは、トピックつきのメッセージをborkerに送り、brokerがメッセージを保持する。 consumerは、brokerのトピックからメッセージを取得する。
抄訳 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とビザンチン将軍問題で例示する。 ステートマシンは、状態変数を決定的に変更するコマンドからなり、入力系列のみから出力が決まる。 モデルは、複数のステートマシンを同じ初期状態から開始し、同じ入力を与え、出力の合意をはかる。