Scatter/Gatherは、ユーザーにクエリを入力するかわりに、システムが提示する文書のクラスタをユーザーに選ばせる情報検索の手法である。 ユーザーが目的の情報にだどりつける適当なクエリをいつも作れるとはかぎらない。 ユーザーが詳しくない分野の情報を調べるときは、クエリにつかえる用語を知らないかもしれない。 また、ある分野の情報を広く浅く収集したいときは、クエリの単語によって検索対象を狭く限定したくないかもしれない。
Pythonであればheap, C++であればsetを2つ使えばよい。 新しい要素を追加する度に、一方に上位kの要素、他方にk+1以降の要素があるように、2つのset, heap間で要素を交換する。 類似の問題をLeetCodeのHard modeで見かけたことがある。
ZooKeeperは、リーダ選出と構成管理の機能を提供するためのインメモリーデータベースである。 データーベースは、ファイルシステムのような階層構造のwait-freeな抽象データ型であり、各ノードにはデフォルトで最大1MBの少量のデータを保存できる。 たとえば、ノードに設定を保存して共有することも、設定ファイルが編集中でないことを示すフラグ代わりのファイルを置くこともできる。
文字数を\(n\)とすると複数のテレビを組合せたときの視聴パターンの重ね方は\(2^n\)個ある。 最大文字数は整数型のビット数より数分の1しかないので、ビット操作ですべての重ね方を試行することを考える。 各重ね方について、パターンを十分に連結した値の論理和に最大文字数以上連続する1があれば、その試行は要件を満たす。
ダイクストラ法を使えば、スタート地点から各区画への最短距離を求められる。 塀に移動にかかる時間を十分に大きい値、かりに\(HM+1\)として、ダイクストラ法適用すると、 ゴール地点が\(3(HM+1)\)以下未満であり、そのときに限り、塀を壊す回数が2回以下でゴール地点に到達できる。
LambdaMARTは、勾配ブースティング決定木(MART)の訓練に、RankNetとLambdaRankを応用したランキング学習である。 RankNetとLambdaRankを以前抄訳で解説した(RankNet, LambdaRank)。 RankNetは、名前にNetがついているが、RankNetの論文で提案されたものは、ネットワークアーキテクチャではなくランキング学習のための損失関数である。 入力されたベクトルをモデルが実数に写像することができれば、ニューラルネットワークでなくてもよい。 RankNetの学習は、モデルの出力する実数をスコアとみなし、あるクエリに該当する2つの事例のうち、より該当する事例に高いスコアを与えられるようにモデルを訓練する。 各訓練データはランキングの異なる2つの特徴とランキングの高い方を示すラベルであり、2つのスコアの差をシグモイドに与えたときの出力を、一方のサンプルが他方よりもランキングが高い確率とみなす。 そして、交差エントロピーが最小になるようにモデルを訓練する。 LambdaRankは、損失の計算を省き、スコアと損失の勾配で重みを更新することで、RankNetの学習を高速化する。 LambdaMARTは、RankNetに勾配ブースティング決定木を使い、残差の計算にLambdaRankを応用したランキング学習のモデルである。
クラッシュしたRDMSのディスクとバッファの状態をクラッシュ前の状態にもどす手法を体系化する。 体系は、Propagation, Buffer handling, EOT Processing, Checkpointingの4要素に着目して技術を分類する。
情報検索の指標は、モデルの返す文書の順序を評価する。 指標の関数自体を損失関数にできれば、重みの更新を指標に最適化できる。 ところが、文書の順序を評価する指標は、重みによる微分が未定義や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の学習は、モデルの出力と訓練データの確率分布の交差エントロピーを最小化する。