木の上の分布比較 - ryamadaの遺伝学・遺伝統計学メモ

ルートのある２分岐木状の分布があるとする。その分布は、ノード数がnで(エッジ数がn-1)。すべてのサンプルで木のトポロジーは同じとする
各ノードに確率 $p_i;i=1,2,...,n$ があって、 $\sum_{i=1}^n p_i=1,p_i \ge 0$ であるという
また、各エッジには長さ $l_j;j=1,2,...,n-1,l_j \ge 0$ があるという
サンプルことに $\{p_i\},\{l_j\}$ が異なるときに、これをどうやって比較しようかと言う話
木構造の比較は、構造の違いがあるときは、そもそも大変でn-gram/q-gramなど(ここの2013/06/05にやった、参考)で部分分解して比較したりするらしいが、ここでは、構造は対応がついているものとする
使える情報は $p_i,l_j$ の2n-1個の実数値と、与えられた木の構造
木の構造には、ノード・エッジの順序情報がある。ノード・エッジの順序情報はルートから葉ノードへの経路がすべての順序に関する情報を保持している。ただし、葉ノードへの経路同士には重複があるので、重複を省いた持たせ方など、別の扱いかたもあるだろう
昨日などの考えを応用すれば、「近いものと遠いものの両方」を使う方法(線形的扱い)と、「近いもののみ」を使う方法(非線形的扱い)とがありえそうだ
Rでノード間距離を出すのは簡単だから、この距離を基にして統計量を出せばよい(？）

library(igraph)
n <- 20
g <- graph.tree(n, children = 2, mode=c("out"))
plot(g)
# 構造が同じでエッジ長の違う二つのグラフのエッジ長ベクトル
e.w1 <- runif(n-1)
e.w2 <- runif(n-1)

sh.p1 <- shortest.paths(g,weight=e.w1)
sh.p2 <- shortest.paths(g,weight=e.w2)

線形的にやる場合
- ノードの値とノード間距離について $\sum_{i_1,i_2} (p_{i_1} - p_{i_2})(L_{i_1,i_2})$ というような値(ただし $L_{i_1,i_2}$ は向きのあるノード間距離)を考慮するのだろう
- このようにすると、すべてのエッジに共通の係数がついた「回帰」のようなこともできるだろう
- また、エッジごとに(向きに配慮した制約を入れた係数)を入れて回帰モデルを複雑に(自由度を上げる)こともできるだろう。
- エッジごとに入れる係数制約を緩めてやれば、上ったり下ったりが任意のモデルにもできそうだが、そうなると、次項の非線形的なやり方と変わらなくなってくる？
非線形的にやる場合
- kNNのようなやり方で局所濃度を推定して、それに基づいてエントロピーを計算することもできそうだ
- kNN局所濃度推定を介する方法をとるとすれば、k近接ノードとの比較をすることになる
- 閾値によって近傍を定義してそれにより局所濃度を推定する方法も取れるだろう。以降の処理は同様にエントロピーベースのそれが簡単そうだ