分散システムのプロセス間で時刻が常に同期しているとは限らない。 プロセスの時刻から判断すると、プロセスでは、ほかのプロセスのイベントと比べてどちらが先に起きたか分からないイベントが起きえる。 Lamportは、各プロセスに単調増加する論理的な時刻をもたせ、メッセージとともに時刻をプロセス間で交換することで、イベントの依存関係と矛盾せずにイベントを全順序に並べる手法を提案した。 先行するイベントは、必ず後続のイベントよりも小さい時刻をもつ。 しかし、逆は必ずしも成り立たない。 先行する場合もあれば、前後関係がないこともある。 Virtual Time and Global States of Distributed Systemsは、各プロセスの時刻を、プロセス数とおなじ数の長さの配列で表現する。 これにより、時刻の前後関係が定義されていることがイベント間に前後関係があることの必要十分条件であることを可能にした。
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\)である。
単射のハッシュ関数は完全である。完全ハッシュ関数により、衝突することのないハッシュテーブルのデータ構造と計算時間量の証明を示す。 データ構造は、はじめに、\(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\)があることを示す。
Zero-shotかつマルチタスク用のモデルとしてGPT-1の後経のGPT-2を提案した。 マルチタスク学習は、複数のタスクむけにモデルを訓練する手法である。 特徴の入力形式はタスクによらず同じであり、タスク間で知識を補うことで各タスクの汎化性能を向上させる。 GPT-1の用途がファインチューニングであるため、GPT-1とGPT-2では解けるタスクが違う。 学習のために、45,000,000件のリンクを含む高品質なコーパスであるWebTextを人の手もかりて用意した。 GPT-2のアーキテクチャは、GPT-1に層正規化の位置を変え、residual layerの重みをスケールしただけであり、GPT-1と大きな違いはない。
マルチプロセスプログラムの正しさを証明するための公理を提案する。 正しさの条件は、プログラムが安全性と活性を満たすことである。 安全はプログラムが特定の状態になりえないことを、活性はプログラムが特定の状態に必ず到達することを意味する。 たとえば、キューにメッセージを配信するproducerとキューから取り出すconsumerがあるとする。 このとき、容量以上のメッセージがキューに蓄積しない性質が安全性に、キューが満杯時にconsumerがメッセージを消費する性質が活性になりえる。 プログラム、安全性、活性を形式化し、安全性と活性を証明することで、プログラムの正しさを示す。
エージェントの行動を撮影した2つのビデオクリップから良い方を人間に選ばせ、報酬関数の学習データを生成する。 テーブルを掃除するロボットの制御などは、報酬関数の設計が難しい。 そこで、2つのビデオクリップとその選好を1つのサンプルとする訓練データで、モデルに報酬関数を学習させる。
環境の状態と状態下での行動のペアの系列を生成し、1秒から2秒間のビデオクリップとして記録する。 そして、人間に、2つのビデオクリップをうち良い方を選んでもらう。 2つのビデオクップのうち一方が他方よりも良い確率を出力できるようにモデルを訓練する。
XとYは互いに干渉しないので、独立してX, Yを考えることができる。 \(x_i, x_{i+1}\)の間に最適な\(X\)があるとすると、\(X\)の位置を\(x_i, x_{i+1}\)を境界として三分探索で求めることができる。 これをすべての\(i\)について試行すればいい。
非同期処理を、スターバックスの注文からコーヒーの提供までの流れにたとえたアネクドートである。 注文をうけたレジの店員は、どの客の注文か分かる目印をコーヒーカップに書き、カップをエスプレッソマシンの上にならべる。 客はバリスタのいるカウンターに移動し、レジの店員は次の顧客の注文をうけつける。 バリスタは、ならべられたカップをとり、コーヒーを注ぎ、客に提供する。
レジの店員とバリスタは非同期にはたらいている。 バリスタのコーヒーの提供が滞っても、レジの店員は注文をうけることができる。 カップの列が長くなれば、バリスタの人数を増やせば、レジの店員に影響することなく、より速くコーヒーを提供できる。 それはキューで通信するプロデューサーとコンシューマーのようである。
特異値分解を応用した潜在的な意味にもとづく文書検索の手法である。 文書を、単語の出現回数が成分の列ベクトルとしてあつかう。 その列ベクトルからなる文書集合の行列に特異値分解(Singular Value Decomposition, SVD)を適用する。 大きい順に\(k\)個の特異値とその特異ベクトルを選んで、低ランクの行列をつくり、もとの行列を近似する。 単語の数が\(t\), 文書数が\(d\)のとき、低ランクの行列の左特異ベクトルの行列\(T\)と右特異ベクトルの転置行列\(D’\)のサイズは、それぞれ、\(t\times k\), \(k \times d\)になる。
ARIES(Algorithm for Recovery and Isolation Exploiting Semantics)は、ログ先行書き込み(write-ahead-logging, WAL)によるSAVEPOINTまでの部分的なトランザクションのロールバック、レコード単位のロック、回復のためのアルゴリズムである。 ログの対象と粒度はページの更新であり、レコードには単調増加するLSN(Log Sequence number)をわりあてる。 レコードは直前の更新のレコードへのポインタであるPrevLSNも含み、あるレコードから以前の更新のレコードへ遡行できる。
ロールバックやリスタート時の更新は、通常時の更新とは別に、保証ログレコード(compensation log record, CLR)に記録される。 ARIESのCLSに記録された更新はUNDOされない。 一方、IMS, AS/400, DB2のCLSは、あるトランザクションが何度もロールバックされると、対応するCLSの更新をUNDOすることがある。