Posts

抄訳 MillWheel: Fault-Tolerant Stream Processing at Internet Scale(2013)

MillWheelはGoogleで開発されたストリーミング処理のフレームワークである。 開発者が羃等な処理をノードとする有向グラフを実装すれば、MillWheelがデータをノードに正確に一回だけ配信する。 データは、キー、値、論理的な時刻の3組からなるレコードを単位として、ノードからノードに出力される。 向き先のノードは、レコードからキーへの関数を、根のノードから出力されるレコードに適用し、期待するキーに対応するレコードをノードに集約する。

抄訳 RUSBoost: A Hybrid Approach to Alleviating Class Imbalance(2010)

RUSBoostは、random undersampling(RUS)とAdaBoostを応用し、不均衡データの予測性能を改善する。 類似の先行研究であるSMOTEBoostよりも学習時間が短く、アルゴリズムが単純である。 アンダーサンプリングで学習データを減らせば、学習時間を短くできるが、学習器に与える情報が減る。 一方、AdaBoostは、前に訓練した弱学習器が誤分類したデータに高い重みを与え、次の弱学習器を学習し、予測性能を上げる。 AdaBoostを借りることで、単分類の難しい少数クラスのサンプルに高い重みを単純に与えられる。

抄訳 GraphChi: Large-Scale Graph Computation on Just a PC(2012)

GraphChiは、商業規模の有向グラフをコンシューマPCで計算できるとうたうデータ構造とプログラミングモデルである。 そのためには、任意のひとつのノードとそのノードに接続する全てのエッジを読み込めるメモリがあればよい。 順序つきのノードを互いに素なP個の集合に分け、それぞれをintervalをよぶ。 interval内のノードに向うエッジを根のノード順にソートし、エッジをP個のshardに分けて保存する。 1つのshardをディスクの連続領域に保存することで、あるノードとノードに接続するエッジを、高々P回のディスクへのアクセスでメモリに読み込める。

抄訳 Popular Ensemble Methods: An Empirical Study(1999)

アンサンブル学習は、弱学習器を組みわせることで、より予測性能の高いモデルを生成する。 弱学習器にニューラルネットワークと決定木を使い、バギングとブースティングの予測性能を、23件のデータで測定した。 バギングはほぼすべての場合に1つの学習器より高精度だったが、まれにブースティングよりも著しく性能が低かった。 他方で、ブースティングは、単体の学習器よりも性能が低いことがあった。 特にニューラルネットワークを弱学習器にした場合に逆転の傾向がみられた。 ブースティグは、既存の弱学習器が誤答したサンプルを回答できる弱学習器を生成する。 Freundらは、データにノイズが多いと、学習の後半になるほどノイズを学習するので、性能が悪くなると示唆している。 データにノイズを混ぜ、その量とブースティングの精度を比較することで、ノイズが多いほどブースティングの性能がバギングと比べたときよりも悪くなることを確認した。

抄訳 DEFINING LIVENESS(1985)

L.Lamportは、Proving the Correctness of Multiprocess Programsで、安全性と活性を導入し、並行プログラミングの正しさを議論した。 そこでは、安全性は、実行中に「よくないこと」が起きない性質であり、活性は「よいこと」が起きる性質である。 後に、Lamportは安全性を形式的に定義したが、活性には与えていない。 そこで、DEFINING LIVENESSは、並行プログラムの実行を状態系列とみなし、活性を形式的な定義した。 プログラムの一部である任意の有限長系列\(\alpha\)について、\(\alpha\)に後続する無限長の系列を\(\beta\)とするとき、性質\(P\)をみたす連結\(\alpha\beta\)が存在し、また、そのときに限り、\(\alpha\)は\(P\)の活性がある。

抄訳 Borderline-SMOTE: A New Over-Sampling Method in Imbalanced Data Sets Learning(2005)

SMOTEは不均衡データに対するオーバーサンプリングを使う手法である。 少数側のクラスのサンプルと近傍のサンプルから少数クラスのサンプルを合成する。 SMOTEはすべての少数クラスのサンプルが合成の材料になりえる。 対して、borderline-SMOTE1とborderline-SMOTE2は、境界から遠い少数クラスのサンプルを使わず、近いサンプルのみから合成する。 borderline-SMOTE1は合成の相手側として常に少数クラスのサンプルを選ぶ。 borderline-SMOTE2は多数クラスのサンプルを選ぶこともある。

抄訳 Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals(1997)

SQLのGROUP BYと集約関数を組み合わせて0次元や1次元の値を出力できる。 一方、ピボットテーブルのように、ある属性値の同じレコードの別の属性値を集計し、さらに集計値の集計値を求めたいことがある。 (DATA) CUBEは、GROUP BYを多次元に拡張した演算子であり、ヒストグラム、ピボットテーブル、ロールアップ、ドリルダウンの計算に使える。

抄訳 ADASYN: Adaptive Synthetic Sampling Approach for Imbalanced Learning(2008)

ADASYNはオーバーサンプリングで不均衡データの予測性能を向上させる。 以前抄訳したSMOTEとおなじく、既存の学習データからサンプルを合成する。 SMOTEとの違いは、K近傍に多数クラスのサンプルの多い少数クラスのサンプルから、より多くのサンプルを合成する点にある。

抄訳 Sagas(1987)

データベースのトランザクションが長くなるほど、ほかのトランザクションを待たせてしまう。 トランザクションの時間は短いほどよい。 トランザクションを短い複数のトランザクションに分割でき、そのトランザクションの間にほかのトランザクションを実行できるなら、そのトランザクションをsagaと呼ぶ。

抄訳 SMOTE: Synthetic Minority Over-sampling Technique(2002)

SMOTEはオーバーサンプリングで不均衡データの予測性能の向上をはかる。 少数クラスのサンプルからk近傍にあるサンプルのうち1つをランダムに選ぶ。 もとのサンプルと選ばれたサンプルの各特徴の差に[0,1]区間のランダムな値を掛け、その値をもとのサンプルに足して、少数クラスのサンプルを合成する。