Posts

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は、同期、非同期の中間的な環境である。 到達時間や時刻の誤差の有界について、存在するが値が分からない環境と、値が分かっているがどの時刻から値が保証されるか分からない環境を意味する。

Regression Shrinkage and Selection via the Lasso

Lasso(least absolute shrinkage and selection operator)を提案した論文で、特定の回帰係数を0にする正則化項により、モデルを解釈しやすくする。 Subset selectionはデータの変化に敏感で、学習結果が安定しない。 Ridge回帰は、回帰係数を全体的に小さくすることで正則化項の制約をみたすため、説明変数を減らしてモデルを解釈しやすくはしない。 線形回帰のモデルから人工的に生成し、Lasso回帰、Subset selection, Ridge回帰を比較した。 結果、もとのモデルの少数から中程度の回帰係数の絶対値が小さく残りが0のときに、Lasso回帰の精度が最も高かった。 絶対値の大きい少数の回帰係数と0の回帰係数のときはSubset selectionが、絶対値の小さい回帰係数が多いときにRidge回帰の精度が最も高かった。

C-Store: A Column-oriented DBMS(2005)

C-Storeは、OLAP系の読み込みクエリに特化した列指向データベースで、標準のSQLでのデータへのアクセスをサポートする。 高速化のために、テーブルのデータを、ある列の値でソートした複数の投影として保存する。 読み込みクエリのSELECT句やソートに合致する投影があれば処理を高速化でき、さらに可用性も向上する。 しかし、同じ列を重複して複数の投影に含める場合、必要なディスク容量も増える。 そのため、C-Storeは4種類の圧縮アルゴリズムによって、データを圧縮して保存する。

SIMPLS: an alternative approach to partial least squares regression

SIMPLSは、NIPALSとおなじく部分的最小二乗法(PLS)である。 NIPALSでは、潜在変数が、デフレーションされた説明変数の線形結合になる。 他方、SIMPLSの潜在変数は、中心化された説明変数の線形結合で表現できる。 そのため、NIPALSよりもSIMPLSの潜在変数の方が説明変数との関係を解釈しやすい。

The WyCach Portfolio Management System(1992)

Ward Cunninghamが証券ポートフォリオ管理システムWyCASH+を開発したときの事例報告で、92年のオブジェクト指向の国際会議OOPSLAで発表された。 この発表が技術的負債の典拠であるが、文中には技術的(technical)はなく単に負債(debt)と書かれている。 アジャイルソフトウェア開発宣言が発表された2001年以前に、ウォーターフォールよりもインクリメンタルな開発のほうが最短で適当な品質のソフトウェアを構築できると主張した。 しかし、インクリメンタルな開発では、全ての知識が十分に揃っていない状態でコーディングするため、システムの部分的な修正を重ねる必要がある。 そして、オブジェクト指向言語のメッセージパッシングによって漸進的な修正が可能になるというのが発表の骨子である。 負債で会社の成長を早められるように、コードをリリースすることで後に修正する必要があるかもしれないが、よい設計を早く知ることができるため、Cunninghamは最初にリリースするコードを負債と形容した。 負債と対比されているのはプログラミングの前に設計を熟考することであり、こちらが前払い、全額払いと表現されている。

PLS-regression: a basic tool of chemometrics

重回帰分析は、説明変数の行列がフルランクでないとき、多重共線性により出力が不安定になる。 そのため、説明変数の数を減らし、説明変数間に相関関係がないようにする必要がある。 PLS(部分的最小二乗法)は、入力変数の線形結合で表わせる潜在変数を求め、潜在変数の線形結合で目的変数を表す。 説明変数の数より少ない数の潜在変数を求めることで、説明変数間の相関関係をとりのぞく。

Statistics and Causal Inference(1986)

ルービンの因果モデルによる統計的因果推定では、群\(U\)の要素を\(u\), 処置を\(t\), \(c\), \(Y\)を潜在的結果変数とすると、\(u\)に対して処置\(c\)を適用するときの処置\(t\)の因果効果を、\(T = Y_t(u) - Y_c(u)\)とみなす。 たとえば、\(u\)を人、\(t\), \(c\)を運動をする、しない、\(Y\)をコレステロールの値とすれば、運動とコレステロール値の関係になる。 おなじ\(u\)に対して\(Y_t(u)\)と\(Y_c(u)\)を両方観測することはできない。 因果効果は、観測するものではなく、推定するものになる。

A Family of Experiments on Test-Driven Development

TDDがコードに及ぼす影響を調べた先行研究はあるが、研究手法、被検者、プログラミング環境などの実験条件は様々、結論は違い、明確な結論はない。 表題の論文は、個別のTDDの実験結果の精度と汎化性を上げるために、実験結果に影響するとみられる実験条件をかえ、TDDとITL(iterative test-last development)を比較する12の実験を実施した。 被検者は4大学と企業12社で、5つのトイタスクを解かせ、通ったテストオラクルの割合で実装の品質を評価した。 結果、TDD初心者の被検者はITLによる実装のほうが品質が高かった。 エディタや言語、ITLとTDDの実験の被験順序、TDDとITLをどちらを先に学んだかは品質に影響しなかった。 学生よりも企業に所属するプロフェッショナルのほうがTDD、ITL両方で品質がよかったが、TDDで実装したときの品質の下がり幅は学生の下がり幅の2倍に及んだ。