次模函式是一個集合函式,隨著輸入集合中元素的增加,增加單個元素到輸入集合導致的函式增量的差異減小。 次模函式具有單調遞減的特性,使得它們適用於許多套用,包括近似算法,遊戲理論(作為用戶偏好的函式建模)和電氣網路。 最近,子模函式在機器學習和人工智慧等幾個現實問題中也出現了巨大的實用性,包括自動總結,多文檔總結,特徵提取,主動學習,感測器布置,圖像採集描述等諸多領域。
基本介紹
- 中文名:次模函式
- 外文名:Submodular functions
- 簡介:在理論上極為重要特殊自守函式.
- 作用:可用它來證明皮卡定理.
- 分類:單調函式 非單調函式
- 別名:子模函式
定義,舉例,分類,套用,
定義
定義1:有限集合 和定義在其冪 的一個實函式 ,稱是次模函式若且唯若對於 的任意兩個子集,滿足
定義2:記 ,如果對於 的任意兩個子集 ,且 , , 滿足,那么函式 是次模函式。
舉例
定義為集合元素的個數,即集合的勢,則有
分類
1.單調函式: 是單調的如果對於 ,有
2.非單調函式:例如對稱函式,對於任意的,有
套用
次模函式在經濟學領域、遊戲設計、機器學習和計算機視覺領域中得到廣泛套用。由於次模函式的收益遞減特性,次模函式常用來建立項目成本的建模,因為隨著項目中購買數量的增加,你會有更大的折扣。在最小化問題中,次模函式塑造了複雜性、相似性和協同性。與此同時,在最大化問題中,次模函式塑造了多樣性、信息和覆蓋面的概念。