서브모듈러 세트 함수

수학에서 서브모듈러 집합함수(submodular set function이라고도 함)는 비공식적으로 입력 집합에 추가할 때 단일 요소가 만드는 함수의 증분값의 차이가 입력 집합의 크기가 증가함에 따라 감소하는 속성을 갖는 집합함수다. 하위 모델 함수는 자연적으로 감소하는 반환 속성을 가지고 있어 근사 알고리즘, 게임 이론(사용자 선호도를 모델링하는 함수로서) 및 전기 네트워크를 포함한 많은 애플리케이션에 적합하다. 최근, 서브모듈러 기능도 자동 요약, 다중 문서 요약, 특징 선택, 능동 학습, 센서 배치, 이미지 수집 요약 및 기타 많은 도메인을 포함한 기계 학습과 인공지능의 몇 가지 실제 문제에서 엄청난 효용성을 발견했다.^[1][2][3][4]

정의

If ${\displaystyle \Omega }$ is a finite set, a submodular function is a set function ${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$, where ${\displaystyle 2^{\Omega }}$ denotes the power set of ${\displaystyle \Omega }$, which satisfies one of the following equivalent conditions.^[5]

1. For every ${\displaystyle X,Y\subseteq \Omega }$ with ${\displaystyle X\subseteq Y}$ and every ${\displaystyle x\in \Omega \setminus Y}$ we have that ${\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)}$.
2. For every ${\displaystyle S,T\subseteq \Omega }$ we have that ${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$.
3. For every ${\displaystyle X\subseteq \Omega }$ and ${\displaystyle x_{1},x_{2}\in \Omega \backslash X}$ such that ${\displaystyle x_{1}\neq x_{2}}$ we have that ${\displaystyle f(X\cup \{$$x_{1}\}+f(X\cup \{x_{2}\})+f$$X\$cup \{x_${1}}\{x_{2}\}}+f$(X$)}$ .

음이 아닌 하위종 함수도 하위종 함수가 되지만 하위종 함수는 하위종 함수가 될 필요가 없다. $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega }$이(가) 유한하다고 가정하지 않으면 위의 조건은 동등하지 않다. $특히{\displaystyle }$,${\displaystyle }S{\displaystyle }$ ${\displaystyle \{\backslash }$$displaystyle S}$이(${\displaystyle 가}$$)$ 유한하다면$$ f ($1}$에 의해 정의된$$ $기능$ f {\$displaystyle$ $f$$(S$$)=$$1$}, S {\$displaystyle$ S$}$이($)$ 무한이면$$$$ $f{\displaystyle }$($)=$이(가)가$$위의 첫 번째 조건을 $만족$하지만, S {\$displaystylease$ S$}$과 S}에 실패한다.${\displaystyle T}$ ${\displaystyle T}$은 교차점이 유한한 무한 집합이다.

하위 모듈 함수의 유형

모노톤

${\displaystyle \mathrm{모든}}$ $T{\displaystyle }$ ${\displaystyle \subseteq }$ S ${\displaystyle T\subseteq S}$에 대해 $f{\displaystyle (T}$) ${\displaystyle \le }$ ${\displaystyle f(S)}$ ${\displaystyle$ f$(T)\leq f(S)}$을 갖는다면 submodular function f ${\displaystystystytle$ f$}$은 다음과 같다$$$.$

선형(모듈러) 함수

$f{\displaystyle (S}$)${\displaystyle }$= ${\displaystyle \underset{}{}}$ i ${\displaystyle \underset{}{\in }}$ ${\displaystyle \underset{}{s}}$ ${\displaystyle \underset{}{}{}_{}}$ ${\displaystyle i_{}}$ ${\$ 형식의 모든 기능을 선형 함수라고$$ 한다. 또한 $\forall {\displaystyle \mathrm{}}$ ${\displaystyle i}$, w ${\displaystyle \mathrm{i}}$ ${\displaystyle {}_{}}$ 0 ${\displaystyle \forall i,w_{i}\geq$ 0$}$인 경우 f는 단조롭다.

예산 추가 기능

Any function of the form ${\displaystyle f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}}$ for each ${\displaystyle w_{i}\geq 0}$ and ${\displaystyle B\geq 0}$ is called budget additive.^{[citation needed]}

커버리지 함수

$\Omega {\displaystyle \mathrm{}}$=${\displaystyle }${ E ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{E\mathrm{}}_{}}$ 2,${\displaystyle \dots ,}$ ${\displaystyle E_{}}$ n ${\displaystyle {}_{}}$ ${\displaystyle$ $\$$Oomega =\{E_{1},E_{2},\ldots$${\displaystyle {,}^{}}$$E_$${$$}\}\}}}}}}$은(는$)$ 일부 접지 집합의 하위 집합 모음입니다$.$ $S{\displaystyle }$ ${\displaystyle \subseteq }$ ${\displaystyle \mathrm{\Omega }}$ ${\displaystyleeq \Oomega }$의 $함수{\displaystyle }$f${\displaystyle }$(${\displaystyle S}$) =${\displaystyle \underset{}{{}_{}e}}$ E ${\displaystyle i_{}{}_{}}${\$displaystyle f($$S$$)=\left \bigcup _{E}\in$ S$}E_{i}\$i}\$right }}}}$은 탐지함수 함수로 불린다. 이는 원소에 음이 아닌 가중치를 추가하면 일반화할 수 있다.

엔트로피

$\Omega {\displaystyle \mathrm{}}$=${\displaystyle }${ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}\dots ,}$ X ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \Oomega =\{X_{1},X_{2},\ldots,X_{n}\}}}}}$을(를) 변수의 집합으로 한다$$. Then for any ${\displaystyle S\subseteq \Omega }$ we have that ${\displaystyle H(S)}$ is a submodular function, where ${\displaystyle H(S)}$ is the entropy of the set of random variables ${\displaystyle S}$, a fact known as Shannon's inequality.^[6] 엔트로피 함수에 대한 추가 불평등은 이질 벡터를 참조하는 것으로 알려져 있다.

마트로이드 계급적 기능.

$\Omega {\displaystyle \mathrm{}}$=${\displaystyle }${ e ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$e ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle }$e ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \Oomega =\{e_{1}, e_{2},\dots ,e_{n}\}}}}}$을(를) 매트로이드 정의가 설정된 지면 세트라고$$ 한다. 그렇다면 매트로이드의 순위함수는 하위함수다.^[7]

논모노톤

모노톤이 아닌 서브모듈라 함수를 비모노톤이라고 한다.

대칭

A non-monotone submodular function ${\displaystyle f}$ is called symmetric if for every ${\displaystyle S\subseteq \Omega }$ we have that ${\displaystyle f(S)=f(\Omega -S)}$. Examples of symmetric non-monotone submodular functions include:

그래프 자르기

$\Omega {\displaystyle \mathrm{}}$=${\displaystyle }${ ${\displaystyle {v\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle {}_{}}$v ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \Oomega =\{v_{1},v_{2},\dots,v_{n}\}}}}}$을(를) 그래프의 꼭지점으로 한다$$. For any set of vertices ${\displaystyle S\subseteq \Omega }$ let ${\displaystyle f(S)}$ denote the number of edges ${\displaystyle e=(u,v)}$ such that ${\displaystyle u\in S}$ and ${\displaystyle v\in \Omega -S}$. This can be generalized by adding non-negative weights to the 가장자리

상호정보

$\Omega {\displaystyle \mathrm{}}$=${\displaystyle }${ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}\dots ,}$ X ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \Oomega =\{X_{1},X_{2},\ldots,X_{n}\}}}}}$을(를) 변수의 집합으로 한다$$. Then for any ${\displaystyle S\subseteq \Omega }$ we have that ${\displaystyle f(S)=I(S;\Omega -S)}$ is a submodular function, where ${\displaystyle I(S;\Omega -S)}$ is the mutual information.

비대칭

대칭이 아닌 비모노톤 서브모듈라 함수를 비대칭이라고 한다.

방향 컷

$\Omega {\displaystyle \mathrm{}}$=${\displaystyle }${ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$v ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ v ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \Oomega =\{v_{1},v_{2},\dots,v_{n}\}}}}}$을(를) 지시된 그래프의 정점이 되도록$$ 한다. For any set of vertices ${\displaystyle S\subseteq \Omega }$ let ${\displaystyle f(S)}$ denote the number of edges ${\displaystyle e=(u,v)}$ such that ${\displaystyle u\in S}$ and ${\displaystyle v\in \Omega -S}$. This can be generalized by adding non-negative weights to the 방향 가장자리

연속연장

로바스 확장

이 확장명은 수학자 Laszlo Lovasz의 이름을 따서 지어졌다. Consider any vector ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$ such that each ${\displaystyle 0\leq x_{i}\leq 1}$. Then the Lovász extension is defined as ${\displaystyle f^{L}(\mathbf {x} )=\mathbb {E}$$({\displaystyle }$$f(\{i x_{i}\geq$ $\lambda$ $\})$ [0${\displaystyle ,}$ ${\displaystyle 1}$ 간격의 균일한 분포에서 선택한$$ $chosen{\displaystyle }$ ${\$$displaystyle [0,1]}$을(를) 초과하는$$ 기대$.$ Lovász 확장은 $f{\displaystyle }$ ${\displaysty f}$가 하위$$ 함수인 경우에만 볼록 함수다.

다선 확장

Consider any vector ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$ such that each ${\displaystyle 0\leq x_{i}\leq 1}$. Then the multilinear extension is defined as ${\displaystyle F$$(\mathbf {x} )=\sum _{S\subseteq \Oomega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin$ S$}(1-x_{i$

볼록 폐쇄

Consider any vector ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$ such that each ${\displaystyle 0\leq x_{i}\leq 1}$. Then the convex closure is defined as ${\displaystyle f^{-}(\mathbf{x})=min(\sum _S{\alpha }_{S}f(S):\sum _S{\alpha }_S{1}_S=\mathbf{x},\sum _S{\alpha }_S=1,}$${\displaystyle f^{-}(\mathbf {x} )=\min \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}$. 세트함수의 볼록한 닫힘은${\displaystyle }$[${\displaystyle 0,}$ ${\displaystyle 1{}^{}}$]${\displaystyle n^{}}${\$displaystyle [0,1]^{n}}$에 걸쳐 볼록하다$.$ 하위함수의 경우$$ ${\displaystyle f^{}}$ $L{\displaystyle {}^{}}$( ${\displaystyle x\mathbf{}}$)${\displaystyle }$= ${\displaystyle {}^{}}$-${\displaystyle {}^{}}$( ${\displaystyle x\mathbf{}}$) ${\displaysty f^{L}(\mathbf {x} )=f^{-}(\mathbf {x})})})}}}}}}}}}}}}}}}}}.$

오목폐쇄

Consider any vector ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$ such that each ${\displaystyle 0\leq x_{i}\leq 1}$. Then the concave closure is defined as ${\displaystyle f^{+}(\mathbf{x})=max(\sum _S{\alpha }_{S}f(S):\sum _S{\alpha }_S{1}_S=\mathbf{x},\sum _S{\alpha }_S=1,}$${\displaystyle f^{+}(\mathbf {x} )=\max \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}$.

특성.

1. 부차함수의 등급은 음이 아닌 선형 조합으로 폐쇄된다. 임의의 하위 함수 $f{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{f\mathrm{}}_{}}$ 2${\displaystyle }$,${\displaystyle }$… , ${\displaystyle {}_{}}$ ${\displaystyle k_{}}${\$displaystyle f_{1},f_{2},\ldots$${\displaystyle ,}$$f_{k},$ 비음수 ${\displaystyle {\alpha 1\mathrm{}}_{}}$ ${\displaystyle {\alpha 2\mathrm{}}_{}}$,${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$을 고려하십시오$.$ 그러면 $g{\displaystyle }$( ${\displaystyle S}$)${\displaystyle }$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{1}}}$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle {\alpha }_{}}$ i ${\displaystyle i_{}}$( ${\displaystyle S}$) = ${\displaystyle g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)}$이(가) 정의한$$ $함수{\displaystyle }$ g$${\$displaystysty g}$이 하위모델로$$ 된다.
2. $모든{\displaystyle }$ 하위 모듈 함수 f ${\$${\displaystyle \mathrm{displaystyle}}$ $f}$에 대해 g$$( $S{\displaystyle }$ )${\displaystyle }$= f (${\displaystyle \mathrm{\Omega }}$ ${\displaystyle (}$S )${\displaystyle }${\$displaystyle g(S)=f(\Oomega \setminus S)}$에 의해 정의된 함수는 하위$$ 모듈이다$.$
3. 함수 $g{\displaystyle }$ (${\displaystyle S}$)${\displaystyle }$= ${\displaystyle \min }$( ${\displaystyle f}$( ${\displaystyle S}$)${\displaystyle }$, c${\displaystyle }$) ${\displaystyle g(S)=\min(f(S),c$ $여기$서 c ${\displaystyle c}$은(는) 실제 숫자이며 $f{\displaystyle }$ ${\displaystyle$ f$}$이(가$$) 단조하수일 때마다 submodular이다. 보다 일반적으로, 감소하지 않는 오목함수 $h{\displaystyle }$ ${\displaystyle$ $g(S)=h(f($$S)}$에 대해 $g{\displaystyle }$(${\displaystyle S}$)${\displaystyle }$= ${\displaystyle h}$(${\displaystyle f)\}}$은(는) 하위모듈이다$.$
4. 확률 p ${\displaystyle$ $p}$과(와) $독립적$으로$$T {\$displaystyle T}$에 $포함$된 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega }$의 각 원소에 대해 $설정$된 T ${\displaystyle$ $T}$을(를) 선택하는$$ 랜덤 프로세스를 고려하십시오$.$ 그 후 다음의 불평등은 $참{\displaystyle \mathbb{}}$E [${\displaystyle f}$ (${\displaystyle T}$ )${\displaystyle }$] ${\displaystyle ]}$ ${\displaystyle p}$p (${\displaystyle \mathrm{\Omega })}$+ (${\displaystyle 1}$ -${\displaystyle }$p )${\displaystyle f}$ (${\displaystyle )}$ ) $\displaystyle$ $\$$mathb {E}[f(T)]]\geqp(\Oomega)+1-p(\$$varnothing$ $)}$이$$빈 집합인$$ 경우다$$. $일반적$으로 S ${\displaystyle S}$이(가) 구성되는 다음과$$ 같은 랜덤 프로세스를 고려하십시오. For each of ${\displaystyle 1\leq i\leq l,A_{i}\subseteq \Omega }$ construct ${\displaystyle S_{i}}$ by including each element in ${\displaystyle A_{i}}$ independently into ${\displaystyle S_{i}}$ with probability ${\displaystyle p_{i}}$. Furthermore let ${\displaystyle S=}$${\displaystyle {\cup }_{}^{}}$ ${\displaystyle i_{}^{}}$= ${\displaystyle 1_{}^{}}$ ${\displaystyle {}_{}^{}{}_{}}$ S ${\displaystyle i_{}}$ ${\$ Then the following inequality is true ${\displaystyle \mathbb {E} [f(S)]\geq \sum _{R\subseteq [l]}\Pi _{i\in R}p_{i}\Pi _{i\notin R}(1-p_{i})f(\cup _{i\in R}A_{i})}$.^{[citation needed]}

최적화 문제

서브모듈라 함수는 볼록함수와 오목함수와 매우 유사한 성질을 가지고 있다. 이러한 이유로 볼록함수 또는 오목함수의 최적화와 관련된 최적화 문제는 일부 제약조건에 따르는 하위함수의 최대화 또는 최소화를 위한 문제라고도 설명할 수 있다.

서브모듈러 세트 기능 최소화

가장 간단한 최소화 문제는 하위 모듈 함수를 최소화하는$$ S $set{\displaystyle \mathrm{\Omega }}$ ${\displaystyle S\subseteq \Oomega }$을(를) 찾는 것이다. 이것이 제약 없는 문제다. 이 문제는 ^[8][9]다항식 시간에 계산할 ^[10][11]수 있다 그래프에서 최소 컷을 계산하는 것은 일반적인 최소화 문제의 특별한 경우다. 그러나 카디널리티 하한과 같은 단순한 제약조건을 추가하면 근사 인자에 대한 다항 인자 하한과 함께 최소화 문제가 어려워진다.^[12][13]

서브모듈러 세트 함수 최대화

최소화의 경우와는 달리, 제한되지 않은 설정에서도 하위 모듈 함수를 최대화하는 것은 NP-hard이다. 서브모듈라(초모듈라) 함수의 로컬 및 글로벌 맥시마(minima)를 찾기 위한 이론 및 열거 알고리즘은 B에서 찾을 수 있다. 골덴고린. European Journal of Operational Research 198(1):102-112, DOI: 10.1016/j.ejor.2008.08.022 예를 들어, 기능이 음이 아닌 경우에만 필요한 경우에도 최대 컷은 특별한 경우다. 제약이 없는 문제는 음성으로 허용될 경우 거의 다루기 어려운 것으로 나타날 수 있다. 함수가 음성이 아닐 때 제한된 하위 함수의 최대화에 대한 광범위한 연구가 있었다. 일반적으로 이러한 문제에 대한 근사 알고리즘은 탐욕스러운 알고리즘이나 로컬 검색 알고리즘에 기초한다. 비 음의 대칭하중함수를 최대화하는 문제는 1/2 근사 알고리즘을 허용한다.^[14] 그래프의 최대 컷을 계산하는 것은 이 문제의 특별한 경우다. 비 음의 하위모형 함수를 최대화하는 보다 일반적인 문제 또한 1/2 근사 알고리즘을 인정한다.^[15] 카디널리티 제약에 따른 단조하함수의 최대화 문제는 $1{\displaystyle \mathrm{}}$- ${\displaystyle 1}$/ ${\displaystyle e}$ ${\displaystyle 1-1/e}$ 근사$$ 알고리즘을 허용한다.^{[16][page needed][17]} 최대 커버리지 문제는 이 문제의 특별한 경우다. 매트로이드 제약을 받는 단조하함수를 최대화하는 보다 일반적인 문제 또한 $1{\displaystyle \mathrm{}}$- 1${\displaystyle }$/ ${\displaystyle e}$ ${\displaystyle 1-1/e}$ 근사$$ 알고리즘을 허용한다.^[18][19][20] 이러한 알고리즘의 대부분은 알고리즘의 반 차이에 기초한 프레임워크 내에서 통일될 수 있다.^[13]

관련 최적화 문제

서브모듈라 최소화와 최대화를 제외하고, 또 다른 자연스러운 문제는 서브모듈라 최적화의 차이다.^[21][22] 불행히도, 이 문제는 NP가 어려울 뿐만 아니라 거의 다루기 어렵다.^[22] 관련 최적화 문제는 서브모듈라 레벨 세트 제약조건(하위모델 커버 또는 서브모듈라 배낭 제약조건에 따른 서브모듈라 최적화라고도 함)에 따라 서브모듈라 함수를 최소화하거나 최대화하는 것이다. 이 문제는 한정된 근사 보증을 허용한다.^[23] 또 다른 최적화 문제에는 평균 복지를 극대화하기 위해 서브모델 함수에 기반한 데이터를 분할하는 것이 포함된다. 이 문제를 하위종류 복지문제라고 한다.^[24]

적용들

하위 모델 기능은 경제학, 게임 이론, 머신러닝, 컴퓨터 비전 등 여러 실제 애플리케이션에서 자연스럽게 발생한다. 수익률이 감소하기 때문에 하위 모델 함수는 종종 더 큰 할인이 발생하며 구매 품목의 증가가 있기 때문에 자연스럽게 품목의 원가를 모델링한다. 하위모델 함수는 복잡성, 유사성 및 협력의 개념을 최소화하는 문제에 나타날 때 모델링한다. 반면에 최대화 문제에서는 다양성, 정보 및 커버리지의 개념을 모델링한다. 특히 기계 학습의 하위 모듈 적용에 대한 자세한 내용은 을 참조하십시오.

참고 항목

• 초모듈러 함수
• 매트로이드, 폴리마트로이드
• 분리할 수 없는 상품에 대한 효용 기능

인용구

참조

• Schrijver, Alexander (2003), Combinatorial Optimization, Springer, ISBN 3-540-44389-4
• Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0-521-01012-8
• Fujishige, Satoru (2005), Submodular Functions and Optimization, Elsevier, ISBN 0-444-52086-4
• Narayanan, H. (1997), Submodular Functions and Electrical Networks, ISBN 0-444-82523-1
• Oxley, James G. (1992), Matroid theory, Oxford Science Publications, Oxford: Oxford University Press, ISBN 0-19-853563-5, Zbl 0784.05002

외부 링크

• http://www.cs.berkeley.edu/~stefje/properties.properties는 더 긴 참고 문헌을 가지고 있다.