Posts

CAP Twelve Years Later: How the "Rules" Have Changed (2012)

CAP定理は、データベースが一貫性 (Consistency), 可用性 (Availability), 分断耐性 (Partition Tolerance) から2つしか選択できない定理として知られる。この定理は、Martin Kleppmannによって、その著書Designing Data-Intensive ApplicationsやA Critique of the CAP Theorem で批判されている。 CAP定理をなづけたBrewerは、CAP Twelve Years Later: How the “Rules” Have Changedで、2つを選択するという表現は誤解をまねく表現であると認め、現実的にはデータベースはネットワークの分断時に一貫性と可用性のトレードオフにさまられると主張した。 CAP定理の発表された12年後の今日では、分断時における一貫性と可用性の最適化に、各ノードの操作履歴を記録するversion verctorsやCommutative Replicated Data Types (CRDTs) を利用できる。

#CAP定理

December 23, 2023

Wide and Deep Learning for Recommender Systems (2016)

推薦システムに一般化線形モデルや深層学習を応用する場合、両者には一長一短がある。一般線形化モデルは、学習データに忠実かつ解釈しやすい推測を出力するが、交互作用では学習データにないアイテムを推薦できない。深層学習は、汎化性能にすぐれるが、疎で高ランクな行列を学習しがたい。 Wide & Deep Learning for Recommender Systemsは、一般線形化モデルとフィードフォワードニューラルネットワーク (FFN) の出力の重みつき和をロジスティック関数に適用し、両者の利点を生かし欠点をおぎなうモデルである。

#Recommendation

December 16, 2023

A Protocol for Packet Network Intercommunication (1974)

TCPの起源はヴィントン・サーフとロバート・カーンが1974年に出版したA Protocol for Packet Network Intercommunicationにまでさかのぼる。当時、ローカルネットワーク内のコンピュータ同士で通信するためのプロトコルはあったが、ネットワークを横断して通信できるプロコトルはなかった。

#TCP

December 9, 2023

Probablistic Latent Semantic Indexing (1999)

Latent Semantic Analysisは、単語の出現頻度の列ベクトルで文書をあらわす行列を、特異値分解し、潜在的な意味を反映した低ランクな行列を求める方法である。特異値を大きい順に\(k\)個えらぶとき、単語の数を\(t\), 文書数を\(d\)とすれば、左特異ベクトルのサイズは、\(t\times k\), 右特異ベクトルの転置行列のサイズは\(k\times d\)になる。

Probabilistic Latent Smantic Indexingは、各文書が1つのクラスに分類されると仮定し、クラスを示すベクトルを隠れ変数とみなしたEMアルゴリズムで、文書や単語の尤度、クラスの生起確率を求める。これにより、クラス\(z_k\)についての文書\(d_i\)と単語\(w_j\)の尤度を\(P(d_i|z_k)\), \(P(w_j|z_k)\), また\(\hat{\textbf{U}}=(P(d_i|z_k))_{i, k}\), \(\hat{\textbf{V}}=(P(w_j|z_k))_{j, k}\), \(\hat{\Sigma}=\text{diag} (P(z_k))_k\)とすると、同時確率モデルを特異値分解の形式\(P=\hat{\textbf{U}}\hat{\Sigma}\hat{\textbf{V}}^t\)で表すことができる。 Latent Semantic Analysisと違い、\(P\)の固有値や特異ベクトルの要素から確率モデル上の意味を読みとることができる。

#潜在意味解析

December 2, 2023

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications (2001)

\(N\)個のノードからなるChordのクラスタは、キーによるノードの問い合せに、\(O(\log N)\)のノードを介して応答できるPeer-to-peerのプロトコルである。 Consistent Hashingを応用しており、\(2^{m-1}+1\)以上\(2^m\)以下のノードが参加するconsistent hashingクラスタは、\(\mod(2^m)\)の非負の整数をIDとしてキーとノードを管理し、IDの空間上で隣接するノードにキーをわりあてる。 Consistent hashingはキーをほぼ均等に配置でき、ノードの参加、離脱時に移動すべきキー数は\(O(1/N)\)に収まる。

参加、離脱するノードと隣接するノード間でのみキーの移動が生じる。 Chordは、多くのノードが参加できるように、各ノードにもたせるルーティング情報を\(m\)個のほかのノードのみに限定する。クライアントや別のノードからキーを受信したノードは、ルーティング情報にあるノードと自分のID \(\textit{n}\)をキー\(\textit{key}\)と比較する。このとき、\(\textit{key} + x \equiv n_i\mod 2^m\)をみたす最小の非負の整数\(x\)に対応する\(n_i\)が自分のIDであれば、そのノードがキーに対応する。それ以外の場合は、最小の値になるIDをもつノードにキーを転送する。

#Peer-to-Peer

November 23, 2023

Pastry: Scalable Decentralized Object Location and Routing for Large Scale Peer to Peer Systems (2001)

Pastryは、広域ネットーワーク規模のPeer-to-Peerなルーティングのアルゴリズムであり、メッセージをメッセージのキーに最も近いIDをもつノードに転送する。 Pastryに参加するノードは対称的で、すべてのノードは同じアルゴリズムにしたがう。

#Peer-to-Peer

November 7, 2023

DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter (2019)

DistilBERTは、BERTの事前学習に知識の蒸留を適用したモデルである。 DistilBERTの事前学習の損失関数は、BERTの学習に使われるMasked language model, BERTとDistilBERTの隠れ状態のコサイン類似度、BERTとDistil BERTの交差エントロピーの線形結合である。学習時は温度付きソフトマックスを\(T>1\)に設定し、推論時には\(T=1\)として通常のソフトマックスをもちいる。 DistilBERTのアーキテクチャは、セグメントエンベディング、下流タスクにCLSトークンのエンベディングを渡す層、半数の層をBERTから取り除いてできている。

November 4, 2023

An Incremental Approach to Compiler Construction (2006)

An Incremental Approach to Compiler Constructionは、コンパイラの学習を目的としたSchemeのコンパイラの実装方法の解説である。コンパイラの実装に使用する言語もSchemeであり、コンパイラは、Intel-x86のアセンブリコードを出力する。プログラマが普段使用しているコンパイラは、教育用の教材としてのコンパイラと比べて複雑であり、学習には向かない。この商用と学習用のコンパイラの溝を埋めるために、Schemeの仕様の大部分を満たす規模のコンパイラの実装例が示されている。実装手順は24ステップからなり、最後のステップまで実装しなくても、各ステップにある実装を完了すれば、コンパイラが正常に動作するように実装することができる。

#コンパイラ

October 23, 2023

GAUSSIAN ERROR LINEAR UNITS (GELUs) 2016

GAUSSIAN ERROR LINEAR UNITS (GELUs)は、標準正規分布の累積分布関数を\(\Phi(x)\)とおくと、\(\text{GELU}(x)=x\Phi(x)\)で定義される活性化関数である。 GELUsは、Dropout, Zoneout, \(\text{ReLU}(x)=\max(0, x)\)の性質を兼ね備える。 Zoneoutは、RNNむけの正則化であり、ユニットが一つ前の状態を確率的に維持するしくみである。 ReLUは、非線形性により、ニューラルネットワークを非線形関数に近似できる。 ZoneoutやDropoutは正則化の役割をはたす。 ReLUsの出力が入力に依存する一方で、Dropoutの出力は入力に依存しない。 GELUsは、確率\(\Phi(x)\)で1をとるベルヌーイ分布にしたがう0-1マスクを人工ニューロンへの入力に適用することで、非線形関数への近似と正則化の両方を実現する。

#活性化関数

October 21, 2023

A design methodology for reliable software systems (1972)

スタンフォードで数学の博士号を取得したLiskovは以前勤めていたMitre Corporationに戻った後、最初にVenusとよばれるタイムシェアリングシステムの開発プロジェクトを担当し、その次にソフトウェア危機に対処する開発手法の研究に取り組んだ。 A design methodology for reliable software systemsは、Venusの開発から得られた構造化プログラミングの方法論である。

#構造化プログラミング

October 8, 2023