Fibonacci heaps(F-heaps)は、ダイクストラアルゴリズムの高速化ために開発された木構造の抽象データ型である。 ノードは、1つの値を保存し、親へのポインタをもつ。 また、2つのポインタによって、同じ階層にある兄弟ノードからなる双方向リストに組み込まれる。 ルート階層にあるノードはいずれも親をもたない。 そのほかにも、削除時に使用されるboolean型の変数がノードごとに1つある。 ヒープにある要素の数\(n\)に対して、要素を償却時間計算量\(O(\log n)\)でき、また、定数の償却時間計算量でほかの主要な操作を行える。
値の保存と参照からなる任意のリクエストの系列を、系列長の時間計算量で処理できるハッシュ関数と連想配列を示す。 求めるハッシュ関数の集合があるとき、各ハッシュ関数の時間計算量の平均がリクエストの系列長に等しくなる。
多言語モデルを大規模なコーパスで訓練し、含意関係認識、質問応答、固有表現抽出において、多言語版のBERTを上まわる予測性能を実現した。 モデルのアーキテクチャはRoBERTaで、Lample and Conneau, 2019に近い方法でモデルを訓練する。 LampleとConneauの手法を含む従来の多言語の言語モデルの評価実験では、wipediaやwikipediaと同程度の大きさのコーパスが使われていた。 従来の訓練データに対し、100言語からなる2.5TBのCommonCrawlをコーパスに使い、コーパスを大規模化することによるモデルへの影響を分析した。 パラメタ数などのモデル大きさを固定し、言語の種類数を30まで増やしたところ、コーパスの小さい言語の性能が向上したが、それ以上増やすと逆に予測性能が低下した。
データベースを同期するためのアルゴリズムmajority consensusを提案する。 アプリケーションは任意のデータベースに更新リクエストを送信でき、データベースは更新リクエストの処理について含意をとる。 データベースは、タイムスタンプのついたレコードの集合である。 タイムスタンプは、レコードの値の更新時刻をあらわす。
対訳コーパスを使わずに、ある言語のエンベディングから別の言語のエンベディングへの写像を学習する。 はじめに、敵対的生成ネットワークで写像を学習する。 次に、出現頻度の高い単語について、写像されたエンベディングと目的言語のエンベディングにプロクラステス分析を適用し、より正確な写像関数を求める。
Skip Listsは、バランス木の代用になるアルゴリズムである。 Skip listsのノードは、ランダムに選ばれた後続のノードへのポインタをもつ。 ランダムに参照するノードを選ぶことで、バランス木よりも単純なアルゴリズムで、計算量を均衡をでき、さらに最悪計算量をより小さくできる。
画像認識にTransformerを使う手法を提案し、Big TransferとNoisy Studentと比較した。 論文が発表された2021年でも、画像認識にニューラルネットワークを使う場合、畳込みニューラルネット(CNN)が基本の選択肢になる。 自己注意機構を使った画像処理の先行研究はあるが、スケールするアーキテクチャではない。
AN IMAGE IS WORTH 16x16 WORDSは、分割した画像をトークン（単語）のようにTransformerへ入力することで、Transformerを画像認識へ応用できるこを示した。 TransformerはCNNのように画像の向きや局所性を帰納バイアスにもたず、データが不十分でないと汎化性能は低い。 しかし、学習データを14M-300Mまで増やすと、CNNを越える汎化性能を発揮した。
分散システムのプロセス間で時刻が常に同期しているとは限らない。 プロセスの時刻から判断すると、プロセスでは、ほかのプロセスのイベントと比べてどちらが先に起きたか分からないイベントが起きえる。 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\)である。