最適ハッシュテーブルの定義と決定木の必要性

理想的なハッシュテーブルでは、１つの領域は１つのデータしか含んでいない (purity)。しかし、一般にそういったパーティショニングは不可能であるため、 可能な限りモデルの LFS の格納数が少なくなるようなパーティショニング方 法を考えなければいけない。

ここで領域の purity をエントロピーによって表現する。ある領域のエントロ ピーは、全ての LFS の生起確率分布がその領域で重なりあっている時に最大 になる。最小（０）になるのは、領域が１つの LFS しか含んでいないときで ある。

$$H(\mbox{bin}_{i})=- \sum^{J}_{j=1} \left\{ \begin{array}{@{\,... ...ox{ ,if} P() \ne 0\\ 0 \mbox{ ,if} P() = 0 \end{array}\right.$$

$J$ はモデルの LFS の数で、 $P(\mbox{LFS}_{j}\vert\mbox{bin}_{i})$ は領域 $\mbox{bin}_{i}$に落ちたサンプル点が $\mbox{LFS}_{j}$に属する確率であ り、ベイズの定理より下のように表される。

$$\begin{eqnarray*} P(\mbox{LFS}_{j}\vert\mbox{bin}_{i}) & = & \frac { P(\mbox{bin... ...bin}_{i}) & = & \sum^{J}_{j=1} P(\mbox{LFS}_{j}, \mbox{bin}_{i}) \end{eqnarray*}$$

$P(\mbox{bin}_{i})$ は、全ての LFS の分布から１つサンプルを取った時に、 それが領域 $\mbox{bin}_{i}$に落ちる確率である。 $P(\mbox{bin}_{i}\vert\mbox{LFS}_{j})$は、 $\mbox{LFS}_{j}$の分布からランダ ムに１つのサンプルを取った時に、それが領域 $\mbox{bin}_{i}$に落ちる確率 である。 $P(\mbox{LFS}_{j})$ は $\mbox{LFS}_{j}$ が画像中で観察される確 率を示す前もって与えられる値で、下のように表現される。

$$\begin{eqnarray*} P(\mbox{LFS}_{j}) & = & \sum^{\mbox{\char93 models}}_{k=1} P(\... ...}_{k=1} P(M_{k}) = 1 \mbox{and} P(\mbox{LFS}_{j}\vert M_{k}) = 1 \end{eqnarray*}$$

$P(\mbox{LFS}_{j}\vert M_{k})$ は、モデル $M_{k}$を様々な視点から見た時に、 $\mbox{LFS}_{j}$が観測される確率である。$P(M_{k})$は、モデル$M_{k}$が 画像中で観測される確率である。これらに関して前もって知識が与えられてい なければ、 $P(\mbox{LFS}_{j})=1/J$ となる（$J$は全ての LFSs の数）。

$P(\mbox{bin}_{i}\vert\mbox{LFS}_{j})$は、トレーニング時に次のように計算さ れる。

$$\begin{eqnarray*} P(\mbox{bin}_{i}\vert\mbox{LFS}_{j}) & = & \int^{u_{1}}_{l_{1}... ...prod^{q}_{i=q} \int^{u_{i}}_{l_{i}} f^{i}_{j}(a_{i})\delta a_{i} \end{eqnarray*}$$

$A$ は全ての属性からなるベクトルで、$f_{j}$は $\mbox{LFS}_{j}$ に対応 する生起確率分布、$f^{i}_{j}$ は属性$a_{i}$ 軸上での生起確率分布である。 属性は互いに相関の無いもの（２次以下）を選んでいるため、 $P(\mbox{bin}_{i}\vert\mbox{LFS}_{j})$ は各属性毎の確率分布の積で表すこと ができる。

そして、次の $E$ が最小になるようにハッシュテーブルを構築する。

$$E = \sum^{\char93 bins}_{i=1} P(\mbox{bin}_{i})H(\mbox{bin}_{i})$$

これでテーブル同士を比較する指標を手にいれたが、次に最適なテーブルを探 索する手法を見つける必要がある。brute force による全探索を行う方法もあ るが、ここでは属性 $a_{i}$ が $n_{i}$ 個に量子化されるとし、この属性軸 上では最大 $n_{i}$ 個の領域に分割されるとする。すると、全属性値空間で 構築しうる領域分割のし方の総数は下のように表される。

$$\begin{eqnarray*} \prod^{\mbox{\char93 attributes}}_{i=1} \sum^{n_{i}}_{k_{i} = ... ...=1} O(2^{n}) \\ & = & O(2^{n \times \mbox{\char93 attributes}}) \end{eqnarray*}$$

$n$ は最も大きい $n_{i}$ と同じオーダーである。これから、直接的な探索 の計算量が、属性数と量子数の積の指数のオーダーであることが分かる。

これは明らかに望ましくないため、MULTI-HASH では決定木を使ってハッシュ テーブルを構築する。しかし、最適の基準が分類誤りを最小にしかつ必要なテ ストの数を最小（木の深さを最小）にすることである場合、最適な２分決定木 を得る問題は NP-hard であることが分かっており、ここでは最適ではないが 良い決定木を生成するヒューリスティックなアルゴリズムを使用する。