単調増加の検出と比較(5)Isotonic programmingと順序・半順序について

  • 単調増加の検出と比較の目次
  • Isotonic regressionWikiはこちら
  • 順序・半順序にあるN個の要素に、実数X=\{x_i\}を当てはめたい
  • N個の要素には順序・半順序があり、Xはこの順序・半順序を満足することとする
  • 実際には、N個のそれぞれの要素には、観測値がw_iあって、その平均がa_iとなっていて、Xの値として、うまい具合になる値を探索したい
  • その探索の条件として\sum_{i=1}^N w_i (x_i-a_i)^2が最小になるようにする
  • 順序・半順序を「サイクルのない有向グラフ」で表すこととすれば
    • グラフG=(V,E)はN個のノードVと、「順序・半順序」に対応する辺Eとからなるものとし
    • min(\sum_{i=1}^N w_i (x_i-a_i)^2);x_i \ge x_j; \forall (i,j) \in EなるN個の実数集合X=\{x_i\};i=1,2,...,Nを見つけることである
  • このXの探索がIsotonic programming