単調増加の検出と比較(5)Isotonic programmingと順序・半順序について
- 単調増加の検出と比較の目次
- Isotonic regressionのWikiはこちら
- 順序・半順序にあるN個の要素に、実数
を当てはめたい
- N個の要素には順序・半順序があり、
はこの順序・半順序を満足することとする
- 実際には、N個のそれぞれの要素には、観測値が
あって、その平均が
となっていて、
の値として、うまい具合になる値を探索したい
- その探索の条件として
が最小になるようにする
- 順序・半順序を「サイクルのない有向グラフ」で表すこととすれば
- グラフ
はN個のノードVと、「順序・半順序」に対応する辺Eとからなるものとし
なるN個の実数集合
を見つけることである
- グラフ
- この
の探索がIsotonic programming