情報検索の指標は、モデルの返す文書の順序を評価する。 指標の関数自体を損失関数にできれば、重みの更新を指標に最適化できる。 ところが、文書の順序を評価する指標は、重みによる微分が未定義や0になりえるので、損失関数には使えない。 LambdaRankは損失関数に直接は使えない関数を学習に応用するアルゴリズムである。 RankNetをLambdaRankで学習することで、学習時間を短縮し、NDCGを向上できた。
分散システムは一貫性、可用性、分断耐性を同時に満たすことができない。 この予想は、2000年のPODCでBrewerが発表したCAP定理として知られてる。 Brewerの講演では厳密な定義と証明がなく、それを補うために、2つの計算モデルにおいてCAPが成立することを証明する。 計算モデルは、asynchronous network modelとpartially synchhronous modelである。 asynchronouse network modelでは、モデルのノードは、クロックをもたず、受信したメッセージとノード内の計算のみで出力を決定する。 partially synchronous modelでは、各ノードは、一定間隔で単調増加するクロックをもち、処理をタイムアウトしたり、スケジューリングしたりできる。 ただし、ノード間でクロックが同期されているとは限らない。
ランキング学習のニューラルネットワークRankNetを提案する。 RankNetは、ベクトルから実数を出力し、その出力が大きいほどランキングが高いと予測する。 損失関数には、ある2つのベクトルのうち片方が他方よりもランキングが高い確率をあたえる。 ここでの確率には、両ベクトルのモデルの出力の差をシグモイド関数に入力したときの出力を使う。 RankNetの学習は、モデルの出力と訓練データの確率分布の交差エントロピーを最小化する。
高水準言語は、実装の詳細を意識せずに使える操作、データ構造、while文などの制御構造を提供する。 この3つは抽象とよばれる。 実装に必要なすべての抽象が言語から提供されることはないので、開発者は足りない抽象を実装しなければならない。 抽象データ型は、言語から提供される抽象を組合せて作るデータ構造であり、開発対象の問題領域にあてはまる抽象を実現する手段でもある。 抽象データ型に対する操作の実装は外部に公開されず、抽象データ型の特徴は抽象データ型に可能な操作によって決められる。 構造化プログラミングと抽象データ型を提供するプログラミング言語を開発し、抽象データ型を使うプログラムのソースコードを例示することで、ほとんどの処理を抽象データ型で実装できることを示唆した。
Web検索をnavigational, informational, transactionalの3つに分類する。 Navigationalは、ユーザーに訪問したい特定のサイトがあり、そのサイトを開くための検索である。 Informationalは、ユーザーに収集したい情報があり、その情報があると思われるサイトを検索する。 情報が断片的であれば、複数のサイトを訪問することもある。 Transactionalは、検索や種々のダウンロードなどインタラクションを要するサイトを訪問するための検索である。 ユーザーは、最終的な目的の情報のために訪問先のサイトでさらに検索をする。 たとえばECサイトへの検索が該当する。
Epidemic Algorithmは、データベース間の差分を解消するために、データベースがランダムに選んだ別のデータベースと同期する手法である。 ここではデータベースにはマスタースレーブの区別はなく、任意のサーバーがレコードの変更を受理できる。 Epidemic Algorithmには、定期的にデーターベース全体を同期する手法と、変更を受理したときにその変更のみを別のデータベースに伝搬させる手法の2つがある。 前者は、データベース全体を同期するので変更のとりこぼしがいずれは解消されるが、同期に時間がかかる。 後者は、時間はかからないが、伝搬を終えるまでに同期できなかった変更があれば、その齟齬が残りつづける。 データベースがある時点で最新の変更をもたない確率を仮定し、その確率で次の同期で変更を取得できる確率を表し、手法間の同期する収束の速さを比較した。
2つのWeb文書から抽出したn-gramの集合を比較し、文書の包含関係と類似度を測定する。 はじめに、大文字をすべて小文字にしたり、htmlタグを除外したりして文書に前処理をかける。 次に文書\(A\)からnグラムの集合\(S(A)\)を抽出する。 このとき、文書\(A\)と\(B\)間の類似度を\(|S(A)\cap S(B)|/|S(A) \cup S(B)|\)、\(A\)の\(B\)への包含の度合いを\(|S(A) \cap S(B)|/|S(A)|\)と定義する。
Count-Min Sketch(CM Sketch)は、単位時間ごとに1要素ずつ更新される\(n\)次元のベクトルの要素を\(n\)の劣線形の計算量で集計できるデータ構造である。 空間の大きさはパラメタで指定する誤差大きさと誤差の生じる確率に依存する。 誤差と確率のパラメタを\(\epsilon\)と\(\delta\)とすると、CM sketchは\(\lceil{\ln \frac{1}{\delta}\rceil}\times \lceil\frac{e}{\epsilon}\rceil\)の二次元行列である。 \(\ln\)の底は\(e\)である。 要素の値、ベクトルの内積、ある範囲の要素の和を劣線形の計算量で求めることができる。 また、これらと二分探索を応用すれば、指定した値よりも大きい要素のみからなる範囲や分位数も計算できる。
局所外れ値因子法(LOF)は、あるインスタンスが外れ値かを、その周囲のインスタンスとの距離をもとに判定する。 異常検知の手法の中には異常か正常かの二値を出力するものがあるが、LOFは[0,1]区間の値を出力する。 L1に近いほど正常とみなす。 密度の高いクラスタと低いクラスタがあり、密度の高いクラスタの少し遠くに外れ値とみなすべきインスタンスがあるとする。 このとき、密度の低いクラスタのインスタンス間の距離を基準にすると、密度の高いクラスタのインスタンスと外れ値のインスタンス間の距離は大きいとみなせない。しかし、外れ値のインスタンスのそばの密度の高いクラスタの距離を基準にすれば、外れ値のインスタンスは周囲のインスタンスから遠いとみなせる。 このように、密度の違うクラスタがあるデータセットでも、インスタンスに近いサンプル間の距離を基準にすることで、他のクラスタの密度で測れば正常なインタンスと判定される外れ値を検出できる。
MillWheelはGoogleで開発されたストリーミング処理のフレームワークである。 開発者が羃等な処理をノードとする有向グラフを実装すれば、MillWheelがデータをノードに正確に一回だけ配信する。 データは、キー、値、論理的な時刻の3組からなるレコードを単位として、ノードからノードに出力される。 向き先のノードは、レコードからキーへの関数を、根のノードから出力されるレコードに適用し、期待するキーに対応するレコードをノードに集約する。