Catalan Numbers(2016)
カタラン数は、いくつかの組合せの問題の解で知られる自然数の系列である。 \(n\)個の対応する括弧"(, )“からなる文字列の組合せの数や、一辺の長さが\(n\)の格子の左上から右下への対角線より上を通る最短経路の数は、\(n\)番目のカタラン数である。 このページでは、この2つの問題の解がカタラン数であるとして、漸化式と二項係数の2つの形式によるカタラン数の一般項を求める。
Posts
Abstract Syntax Networks for Code Generation and Semantic Parsing
Abstract Syntax Networksは、非構造的な文章などの入力から、抽象構文木(AST)にしたがう系列を生成できるencoder decoderである。 decoderは、ASTの生成規則にある記号に対応するモジュールを再帰的に構成したネットワークである。 モジュールは、右辺のどの生成規則を選択すべきか推定する。 そして、選択した規則のモジュールをさらに再帰的に選択することで、ASTにしたがう出力を生成する。
Fibonacchi Heaps and Their Uses in Improved Network Optimization Algorithms(1987)
Fibonacci heaps(F-heaps)は、ダイクストラアルゴリズムの高速化ために開発された木構造の抽象データ型である。 ノードは、1つの値を保存し、親へのポインタをもつ。 また、2つのポインタによって、同じ階層にある兄弟ノードからなる双方向リストに組み込まれる。 ルート階層にあるノードはいずれも親をもたない。 そのほかにも、削除時に使用されるboolean型の変数がノードごとに1つある。 ヒープにある要素の数\(n\)に対して、要素を償却時間計算量\(O(\log n)\)でき、また、定数の償却時間計算量でほかの主要な操作を行える。
Layer Normalization (2016)
Universal Classes of Hash Functions(1977)
値の保存と参照からなる任意のリクエストの系列を、系列長の時間計算量で処理できるハッシュ関数と連想配列を示す。 求めるハッシュ関数の集合があるとき、各ハッシュ関数の時間計算量の平均がリクエストの系列長に等しくなる。
Unsupervised Cross-lingual Representation Learning at Scale (2020)
多言語モデルを大規模なコーパスで訓練し、含意関係認識、質問応答、固有表現抽出において、多言語版のBERTを上まわる予測性能を実現した。 モデルのアーキテクチャはRoBERTaで、Lample and Conneau, 2019に近い方法でモデルを訓練する。 LampleとConneauの手法を含む従来の多言語の言語モデルの評価実験では、WikipediaやWikipediaと同程度の大きさのコーパスが使われていた。 従来の訓練データに対し、100言語からなる2.5TBのCommonCrawlをコーパスに使い、コーパスを大規模化することによるモデルへの影響を分析した。 パラメタ数などのモデル大きさを固定し、言語の種類数を30まで増やしたところ、コーパスの小さい言語の性能が向上したが、それ以上増やすと逆に予測性能が低下した。
A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases(1979)
データベースを同期するためのアルゴリズムmajority consensusを提案する。 アプリケーションは任意のデータベースに更新リクエストを送信でき、データベースは更新リクエストの処理について含意をとる。 データベースは、タイムスタンプのついたレコードの集合である。 タイムスタンプは、レコードの値の更新時刻をあらわす。
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を越える汎化性能を発揮した。