劣モジュラ関数

画像処理などで用いられるグラフカットや、機械学習などで
「劣モジュラ性」
とか
「劣モジュラ関数」
というキーワードが登場する。

劣モジュラ性という性質を持つ関数を劣モジュラ関数と呼ぶわけだけど、なにそれ？

一般的には、次のように説明されることが多い。

＝＝
X,Y ⊆ V であり、X ⊆ Y であるとして、集合関数Fが次の性質を満たすとき、この関数Fは劣モジュラ関数と呼ばれる。

＝＝

まず、集合関数というものを理解する必要がある。

集合関数とは、集合を引数にとる関数のこと。

高校レベルでF(x)と書いた時のxは実数と思うし、大学に入って、ベクトルを引数にとる関数を習ったりするけど、ここでは集合が引数。
で、値は実数。

へえ、集合を引数にとるような関数があるんだね。

プログラミングぽく書けば、こんな感じ

double F(set X); 

もう一回、改めて式を見てみる。

何かイメージできるだろうか。

上式のX,Yは、X ⊆ Y を満たす集合だから、具体例として、X={a,b}, Y={a,b,c,d} のように書いたらわかりやすい。

書き直してみる。

もうちょっと書き直す。

ちょっとわかりやすくなった。
これから、何が読み取れるだろうか。

劣モジュラ関数の性質を言葉で書くと、次のような感じになる。

「集合 Y に要素 v を加えた時の増分よりも、より小さい集合 X に要素 v を加えた時の増分の方が大きい」

大きい集合に1つ追加したって大した変化はないけど、小さい集合に1つ追加したら変化は大きいよね。ということで、直観的にもわかりやすい。
「劣モジュラ性」なんて名前は仰々しいけど、そんなに理解が難しい性質じゃない。

※次のように定義されることもある

参考：
・大阪大学 河原吉伸, 機械学習における劣モジュラ性の利用http://jpn.nec.com/rd/datamining/images/nec_datamining_seminar8.pdf
・劣モジュラ性 (Machine Learning Advent Calendar の 4 日目) - blog.sparsegraph.com http://blog.sparsegraph.com/2012/12/machine-learning-advent-calendar-4.html

パターン認識と機械学習 上

基礎からわかる画像処理―画像処理のアルゴリズムを理解する (I・O BOOKS)