劣モジュラ関数最小化のお勉強(Minimum Norm Point) - wildpieの日記最近、劣モジュラ最適化と機械学習という本を買いました。その２章まで読んだので、劣モジュラ関数の最小化を試してみます。ちなみに２章は最小化、3章は最大化がテーマです。 劣モジュラ 集合を入力とする関数f()が劣モジュラ性(Sub modular)を持つのは以下の不等式を満たすときです。 $$ \begin{equation} f(S)+f(T)\geq f(S \cup T)+f(S \cap T) (\forall S,T \subseteq V) \end{equation} $$ ここでVはとりうる最大の集合で、V={1}とか{1,2}とか{1,2,3}とかです。SとTはそれに含まれる集合なのでV={1,2,3}のときS={1,2}などがあり得ます。具体的な意味は[3]がわかりやすいです。イメージとしては大きな集合を入力したときほど、新たな要素を追加しても変化が小さい関数が劣モジュラ関
