Principles of Transaction-Oriented Database Recovery(1983)
クラッシュしたRDMSのディスクとバッファの状態をクラッシュ前の状態にもどす手法を体系化する。 体系は、Propagation, Buffer handling, EOT Processing, Checkpointingの4要素に着目して技術を分類する。
Posts
抄訳 Learning to Rank with Nonsmooth Cost Functions (2006)
情報検索の指標は、モデルの返す文書の順序を評価する。 指標の関数自体を損失関数にできれば、重みの更新を指標に最適化できる。 ところが、文書の順序を評価する指標は、重みによる微分が未定義や0になりえるので、損失関数には使えない。 LambdaRankは損失関数に直接は使えない関数を学習に応用するアルゴリズムである。 RankNetをLambdaRankで学習することで、学習時間を短縮し、NDCGを向上できた。
Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web(2002)
分散システムは一貫性、可用性、分断耐性を同時に満たすことができない。 この予想は、2000年のPODCでBrewerが発表したCAP定理として知られている。 しかし、Brewerの講演では厳密な定義や証明はない。 そこで、それを補うために、ある2つの計算モデルでCAPが成立することを証明する。 計算モデルは、asynchronous network modelとpartially synchhronous modelである。 asynchronouse network modelでは、モデルのノードは、クロックをもたず、受信したメッセージとノード内の計算のみで出力を決定する。 partially synchronous modelでは、各ノードは、一定間隔で単調増加するクロックをもち、処理をタイムアウトしたり、スケジューリングしたりできる。 ただし、ノード間でクロックが同期されているとは限らない。
抄訳 Learning to Rank using Gradient Descent (2005)
ランキング学習のニューラルネットワークRankNetを提案する。 RankNetは、ベクトルから実数を出力し、その出力が大きいほどランキングが高いと予測する。 損失関数には、ある2つのベクトルのうち片方が他方よりもランキングが高い確率をあたえる。 確率とみなす値は、両ベクトルのモデルの出力の差をシグモイド関数に入力したときの出力である。 RankNetの学習は、モデルの出力と訓練データの確率分布の交差エントロピーを最小化する。
抄訳 PROGRAMMING WITH ABSTRACT DATA TYPES (1974)
高水準言語は、実装の詳細を意識せずに使える操作、データ構造、while文などの制御構造を提供する。 この3つを抽象とよぶ。 プログラミング言語から提供される抽象だけではプログラムを実装できないので、開発者は、足りない抽象を実装しなければならない。 抽象データ型は、言語から提供される抽象を組合せて作るデータ構造である。 抽象データ型に対する操作の実装は外部に公開されず、抽象データ型の特徴は抽象データ型に可能な操作によって決まる。 構造化プログラミングと抽象データ型を提供するプログラミング言語を開発し、抽象データ型を使うプログラムのソースコードを例示することで、ほとんどの処理が抽象データ型だけで実装可能なことを示唆した。
抄訳 A taxonomy of web search(2002)
Web検索をnavigational, informational, transactionalの3つに分類する。 Navigationalは、ユーザーに訪問したい特定のサイトがあり、そのサイトを開くための検索である。 Informationalは、ユーザーに収集したい情報があり、その情報があると思われるサイトを検索する。 情報が断片的であれば、複数のサイトを訪問することもある。 Transactionalは、検索や種々のダウンロードなどインタラクションを要するサイトを訪問するための検索である。 ユーザーは、最終的な目的の情報のために訪問先のサイトでさらに検索をする。 たとえばECサイトへの検索が該当する。
Epidemic Algorithm for Replicated Database Maintenance(1987)
Epidemic Algorithmは、データベース間の差分を解消するために、データベースがランダムに選んだ別のデータベースと同期する手法である。 Epidemicを邦訳すると伝染性である。 ここではデータベースにはマスタースレーブの区別はなく、任意のサーバーがレコードの変更リクエストを受理できる。 Epidemic Algorithmには、定期的にデーターベース全体を同期する手法と、変更を受理したときに当該の変更のみを別のデータベースに伝搬させる手法の2つがある。 前者は、データベース全体を同期するので変更のとりこぼしがいずれは解消されるが、同期に時間がかかる。 後者は、時間はかからないが、伝搬を終えるまでに同期できなかった変更があれば、その齟齬が残りつづける。 データベースがある時点で最新の変更をもたない確率を仮定し、その確率で次の同期で変更を取得できる確率を表し、手法間の同期する収束の速さを比較した。
抄訳 Syntactic Clustering of the Web(1997)
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)|\)と定義する。
An Improved Data Stream Summary: The Count-Min Sketch and its Applications(2005)
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: Identifying Density-Based Local Outliers(2000)
局所外れ値因子法(LOF)は、あるインスタンスが外れ値であるかを、その周囲のインスタンスとの距離から判定する。 異常検知の手法の中には異常か正常かの二値を出力するものがあるが、LOFは[0,1]区間の値を出力する。 1に近いほど正常とみなす。 要素間の距離が近くて密度の高いクラスタと低いクラスタがあり、密度の高いクラスタの少し遠くに外れ値とみなすべきインスタンスがあるとする。 このとき、密度の低いクラスタのインスタンス間の距離を基準にすると、密度の高いクラスタのインスタンスと外れ値のインスタンス間の距離は大きいとみなせない。
他方で、外れ値のインスタンスのそばの密度の高いクラスタの距離を基準にすれば、外れ値のインスタンスは周囲のインスタンスから遠いとみなせる。 このように、密度の違うクラスタがあるデータセットでも、インスタンスに近いサンプル間の距離を基準にすることで、他のクラスタの密度で測れば正常なインタンスと判定される外れ値を検出できる。