A Protocol for Packet Network Intercommunication (1974)
TCPの起源はヴィントン・サーフとロバート・カーンが1974年に出版したA Protocol for Packet Network Intercommunicationにまでさかのぼる。 当時、ローカルネットワーク内のコンピュータ同士で通信するためのプロトコルはあったが、ネットワークを横断して通信できるプロコトルはなかった。
Posts
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\)の固有値や特異ベクトルの要素から確率モデル上の意味を読みとることができる。
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をもつノードにキーを転送する。
LoRA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS
Li et al. (2018)とAghajanyan et al. (2020)は、Large Language Models (LLM)のファインチューニングにかかる計算資源は大きいが、下流タスクに必要なパラメータ数はLLMのパラメタ数よりもはるかに少ないと主張した。 LoRAは、この仮説によりファインチューニングを避け、LLMの重みと線形結合すると下流タスクに最適な重みに近似できる小さな行列を求める。 LLMの重みを\(W_0\in\mathbb{R}^{d\times k}\)とすると、\(W_0+BA\ (B\in\mathbb{R}^{d\times r}, A\in\mathbb{R}^{r\times k}, r \ll\min (d, k))\)が下流タスクに最適な重みに近づくように、ファインチューニングにかわって\(W_0\)を更新せず\(B,\ A\)のみを更新する。 \(r\)が\(d, k\)よりも小さいので、ファインチューニングよりも学習時間は短い。 また、複数の下流タスクを入力に適用する場合、\(W_0x\)を共有できるので、推論に必要な計算も\(W_0\)を更新するファインチューニングより少ない。
Pastry: Scalable Decentralized Object Location and Routing for Large Scale Peer to Peer Systems (2001)
Pastryは、広域ネットーワーク規模のPeer-to-Peerなルーティングのアルゴリズムであり、メッセージをメッセージのキーに最も近いIDをもつノードに転送する。 Pastryに参加するノードは対称的で、すべてのノードは同じアルゴリズムにしたがう。
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から取り除いてできている。
An Incremental Approach to Compiler Construction (2006)
An Incremental Approach to Compiler Constructionは、コンパイラの学習を目的としたSchemeのコンパイラの実装方法の解説である。 コンパイラの実装に使用する言語もSchemeであり、コンパイラは、Intel-x86のアセンブリコードを出力する。 プログラマが普段使用しているコンパイラは、教育用の教材としてのコンパイラと比べて複雑であり、学習には向かない。 この商用と学習用のコンパイラの溝を埋めるために、Schemeの仕様の大部分を満たす規模のコンパイラの実装例が示されている。 実装手順は24ステップからなり、最後のステップまで実装しなくても、各ステップにある実装を完了すれば、コンパイラが正常に動作するように実装することができる。
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マスクを人工ニューロンへの入力に適用することで、非線形関数への近似と正則化の両方を実現する。
A design methodology for reliable software systems (1972)
スタンフォードで数学の博士号を取得したLiskovは以前勤めていたMitre Corporationに戻った後、最初にVenusとよばれるタイムシェアリングシステムの開発プロジェクトを担当し、その次にソフトウェア危機に対処する開発手法の研究に取り組んだ。 A design methodology for reliable software systemsは、Venusの開発から得られた構造化プログラミングの方法論である。
BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension (2019)
BARTはTransformerをつかった系列変換モデルの事前学習である。
ノイズを入れたテキストからもとのテキストを復元できるようにモデルを訓練する。
BARTの特徴は、ノイズの作り方に制限がないところにある。
比較したノイズの作り方は、ランダムに選んだトークンから文書を始めることで回転する、BERTとおなじトークンのマスキング、トークンの一部の削除、文書中の文の順序の入れ換え、ある区間中にあるトークンをまとめて1つの[MASK]に置き換える方法の5種類である。
最後のトークンを1つのマスクキングするときに最もよい結果になった。
マスクに置き換える区間の長さは\(\lambda = 3\)のポアソン分布によって決まる。