ただのメモ

他の人に見せても良い方のメモ

階層的な話

  • 木構造を上手く埋め込む方法について勉強する。
  • こちら
  • その前に、医療行為について考えてみる。
  • 医者(たち)は、患者が来た時、検査や診察をする
    • 患者にまつわるあらゆる情報の組が、高次元空間にあるとする
      • 一つ一つの検査・診察は、その高次元空間の部分空間を指定する
        • 例えば、
          •  男か女かという情報と、年齢という情報の組が作る空間は、2次元空間にあるとする。
          • そこで、医者が、男か女かを聞く。患者は男という。
          • その時、男という情報が確定して、患者の情報の組の片方が指定される。
          • それにより、後は、年齢という情報の作る、1次元空間のみを考えることになる。
        • その空間が膨大なので、木にしたり、して、気にすることの数を制限している。
        • 病気が高次元空間にあり、詐病が原点にある。とすると、座標の取り方はどうしたらよいか。どこにどんな病気があるか。各病気は、点か、広がりか、付加的構造はあるか?ということが気になる。
      • 木にしたときに、もとの空間では、どんな配置だっただろうか、ということが気になることがある。
        • 葉の距離が気になるとき
          • 木での距離と、高次元空間での距離との違い
  • まえおきが長くなったが、とりかかるとする。
  • 次元削減
    • 概要
      • 高次元データがある。 
        • そのデータは、固有の低次元での表現がある。
        • 低次元での表現は、もとの構造を保持している
          • 大概、全ての構造を保持するのは、無理。
          • なの上手く埋め込む方法について勉強する。
          • こちら。
          • その前に、医療行為について考えてみる。
          • 医者(たち)は、患者が来た時、検査や診察をする
          • 患者にまつわるあらゆる情報の組が、高次元空間にあるとする
          • 一つ一つの検査・診察は、その高次元空間の部分空間を指定する
          • 例えば、
          •  男か女かという情報と、年齢という情報の組が作る空間は、2次元空間にあるとする。
          • そこで、医者が、男か女かを聞く。患者は男という。
          • その時、男という情報が確定して、患者の情報の組の片方が指定される。
          • それにより、後は、年齢という情報の作る、1次元空間のみを考えることになる。
          • その空間が膨大なので、木にしたり、して、気にすることの数を制限している。
          • 病気が高次元空間にあり、詐病が原点にある。とすると、座標の取り方はどうしたらよいか。どこにどんな病気があるか。各病気は、点か、広がりか、付加的構造はあるか?ということが気になる。
          • 木にしたときに、もとの空間では、どんな配置だっただろうか、ということが気になることがある。
          • 葉の距離が気になるとき
          • 木での距離と、高次元空間での距離との違い
  • まえおきが長くなったが、とりかかるとする。
    • 次元削減
      • 概要
        • 高次元データがある。 
          • そのデータは、固有の低次元での表現がある。
          • 低次元での表現は、もとの構造を保持している
          • 大概、全ての構造を保持するのは、無理。
          • なので、取り出したい構造に合わせて、手法を変える必要がある。
            • 料理
              • 食材の全ての味を引き立てることは難しい。
              • 引き出したい味に合わせて調理法を変える
      • 線形な方法
        • PCA
        • MDS
        • 距離を保つ
      • 非線形な手法
        • 多様体学習
        • グラフを用いた学習
    • 埋め込みの混雑問題
      • 低次元に埋め込むことで、クラスター(塊)が出来る。
      • しかし、低い次元だと、埋め込めるスペースが狭くなり、結果的に混ざったクラスターが出来やすい
    • Force based
      • SNEとその類い
        • 近い点には、引力を、遠い点には、斥力を与えることで、近さ、遠さを保持した埋め込みをする
        • 斥力と引力とのバランスを保つのが難しい
          • 斥力が弱いと、混ざるし、
          • 斥力が強いと、塊ができすぎる
      • クラスタリングは、混ぜるか離すかの制御が難しい。
    • Tree Preserving Embedding
      • Force basedの弱点を補強する
        • 近さと遠さを維持させる仕組みと、塊を保持する仕組みの療法を使う
      • クラスタリングと樹形図を両立する。
        • 別々にやると、同じでないことがある。
      • SL樹形図
        • 樹形図、最小全域木
        • ある高さで、樹形図を切る
          • 不安定
        • 一方のTPEは、どの高さで切っても、良い
    • 単語を拾う
      • 各頂点が、p次元ベクトル、n個の点
      • ユークリッド空間
      • 頂点の間の似てなさを決める行列(n×n) 
      • ε結合
        • 2点がε結合である、とは、iとjの間に、道があり(辺を通って行くことが出来て)、各辺の頂点の組に対して、(似てなさ、距離)がε以下であるようなもの
        • 似てなさという行列からグラフをイメージ。同様に、距離を成分とする行列からグラフをイメージする。
          • それが、今回2つの種類のε結合を用意した理由
      • Single Linkage
      • Ultrametric distance
        •  min_{j \in S} max_{l=1}^{m-1} D_{\alpha_l, \alpha_{l+1}}
      • 最小全域木
        • 道が最短距離
        • ありうる最小の道の可能性の1つ。
      • Lij結合であり、ε結合(ただしεはLijより小さい)
  • アルゴリズム
    • 初期化 
    • 合体させるくらすたーの組を作る
      •  a_k, b_k = argmin_{a,b \in I_k, a \neq b }\Delta (S_a, S_b)
      •  \Delta_k = \Delta (S_a_k, S_b_k)
    •  合体させる
      •  S_{n+k} = S_a_k \Cup S_b_k
      • 指標を更新する
    • 合体させたクラスターに対してultrametric distanceを見つける
    • 埋め込む
    • 埋め込みしたものをを返す
  • 描こうと思ったが、階層的クラスタリングの勉強がまだなので、その時にする。

バイバイ!