A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases(1979)
データベースを同期するためのアルゴリズムmajority consensusを提案する。 アプリケーションは任意のデータベースに更新リクエストを送信でき、データベースは更新リクエストの処理について含意をとる。 データベースは、タイムスタンプのついたレコードの集合である。 タイムスタンプは、レコードの値の更新時刻をあらわす。
Posts
WORD TRANSLATION WITHOUT PARALLEL DATA(2018)
対訳コーパスを使わずに、ある言語のエンベディングから別の言語のエンベディングへの写像を学習する。 はじめに、敵対的生成ネットワークで写像を学習する。 次に、出現頻度の高い単語について、写像されたエンベディングと目的言語のエンベディングにプロクラステス分析を適用し、より正確な写像関数を求める。
Skip Lists: A Probabilistic Alternative to Balanced Trees(1990)
Skip Listsは、バランス木の代用になるアルゴリズムである。 Skip listsのノードは、ランダムに選ばれた後続のノードへのポインタをもつ。 ランダムに参照するノードを選ぶことで、バランス木よりも単純なアルゴリズムで、計算量を均衡をでき、さらに最悪計算量をより小さくできる。
AN IMAGE IS WORTH 16x16 WORDS: TRANSFORMERS FOR IMAGE RECOGNITION AT SCALE(2021)
画像認識にTransformerを使う手法を提案し、Big TransferとNoisy Studentと比較した。 論文が発表された2021年でも、画像認識にニューラルネットワークを使う場合、畳込みニューラルネット(CNN)が基本の選択肢になる。 自己注意機構を使った画像処理の先行研究はあるが、スケールするアーキテクチャではない。
AN IMAGE IS WORTH 16x16 WORDSは、分割した画像をトークン（単語）のようにTransformerへ入力することで、Transformerを画像認識へ応用できるこを示した。 TransformerはCNNのように画像の向きや局所性を帰納バイアスにもたず、データが不十分でないと汎化性能は低い。 しかし、学習データを14M-300Mまで増やすと、CNNを越える汎化性能を発揮した。
Virtual Time and Global States of Distributed Systems(1988)
分散システムのプロセス間で時刻が常に同期しているとは限らない。 プロセスの時刻から判断すると、プロセスでは、ほかのプロセスのイベントと比べてどちらが先に起きたか分からないイベントが起きえる。 Lamportは、各プロセスに単調増加する論理的な時刻をもたせ、メッセージとともに時刻をプロセス間で交換することで、イベントの依存関係と矛盾せずにイベントを全順序に並べる手法を提案した。 先行するイベントは、必ず後続のイベントよりも小さい時刻をもつ。 しかし、逆は必ずしも成り立たない。 先行する場合もあれば、前後関係がないこともある。 Virtual Time and Global States of Distributed Systemsは、各プロセスの時刻を、プロセス数とおなじ数の長さの配列で表現する。 これにより、時刻の前後関係が定義されていることがイベント間に前後関係があることの必要十分条件であることを可能にした。
Generating Long Sequences with Sparse Transformers(2019)
TransformerのQKV注意機構に入力するベクトルを限定し、長さ\(n\)の系列をQKV注意機構に入力したときの空間計算量を\(\mathcal{O}(n\sqrt{n})\)まで減らした研究である。 Transformerであれば、系列の要素は、要素自体の位置と以前の要素すべてを注意し、時間と空間計算量は\(\mathcal{O}(n^2)\)になる。 Sparse Transformerは、\(p\)個のパターンを用意し、パターンに該当する要素のみを各注意機構に入力し、\(p\)個の注意を生成する。 そして、\(p\)個の注意を合成し、1つの注意に変換する。 パターンは、画像やテキストなど、入力するデータの種類によって決めておく規則であり、たとえば、直近にある一定数の要素や等間隔に離れた要素を指定するパターンがありえある。 パターンが\(p\)であれば、計算量は\(\mathcal{O}\sqrt[p]{n}\)になる。実験の設定は\(p=2\)である。
Storing a Sparse Table with O(1) Worst Case Access Time(1984)
単射のハッシュ関数は完全である。完全ハッシュ関数により、衝突することのないハッシュテーブルのデータ構造と計算時間量の証明を示す。 データ構造は、はじめに、\(U(|U|=m)\)の部分集合\(S\)(\(|S|=n\))の要素\(x\)をハッシュテーブルに格納するとき、ある\(U\)の要素\(k\)を使った関数\(f(x)=(kx\mod p)\mod n\)で\(x\)を格納するブロック\(W_j(0\le j < n)\)を決める。 \(p\)は\(p=m+1\)の素数である。 次に\(U\)の要素\(k'_j\)をもちいた関数\(g(x) = ((k'_jx) \mod p)\mod |W_j|^2\)で、\(x\)のエントリを特定する。 データ構造の証明は、\(f, g\)によって重複なくエントリを特定できる\(k\), \(k'_j\)があることを示す。
概要 Language Models are Unsupervised Mmultitask Learners(2018)
Zero-shotかつマルチタスク用のモデルとしてGPT-1の後経のGPT-2を提案した。 マルチタスク学習は、複数のタスクむけにモデルを訓練する手法である。 特徴の入力形式はタスクによらず同じであり、タスク間で知識を補うことで各タスクの汎化性能を向上させる。 GPT-1の用途がファインチューニングであるため、GPT-1とGPT-2では解けるタスクが違う。 学習のために、45,000,000件のリンクを含む高品質なコーパスであるWebTextを人の手もかりて用意した。 GPT-2のアーキテクチャは、GPT-1に層正規化の位置を変え、residual layerの重みをスケールしただけであり、GPT-1と大きな違いはない。
Proving the Correctness of Multiprocess Programs (1977)
マルチプロセスプログラムの正しさを証明するための公理を提案する。 正しさの条件は、プログラムが安全性と活性を満たすことである。 安全はプログラムが特定の状態になりえないことを、活性はプログラムが特定の状態に必ず到達することを意味する。 たとえば、キューにメッセージを配信するproducerとキューから取り出すconsumerがあるとする。 このとき、容量以上のメッセージがキューに蓄積しない性質が安全性に、キューが満杯時にconsumerがメッセージを消費する性質が活性になりえる。 プログラム、安全性、活性を形式化し、安全性と活性を証明することで、プログラムの正しさを示す。
概要 Deep Reinforcement Learing from Human Preferences (2017)
エージェントの行動を撮影した2つのビデオクリップから良い方を人間に選ばせ、報酬関数の学習データを生成する。 テーブルを掃除するロボットの制御などは、報酬関数の設計が難しい。 そこで、2つのビデオクリップとその選好を1つのサンプルとする訓練データで、モデルに報酬関数を学習させる。
環境の状態と状態下での行動のペアの系列を生成し、1秒から2秒間のビデオクリップとして記録する。 そして、人間に、2つのビデオクリップをうち良い方を選んでもらう。 2つのビデオクップのうち一方が他方よりも良い確率を出力できるようにモデルを訓練する。