Submodularity·한계 이득·Greedy 커버리지

겹치는 정보의 수익 체감

센서는 정보가 거의 없을 때 유용하지만 다른 센서들이 이미 대상을 덮었다면 중복될 수 있습니다. 따라서 센서 집합의 가치는 센서별 고정 가치를 더한 값과 다릅니다. 대표 데이터나 관측 위치를 고를 때도 비슷한 현상이 나타납니다. 다만 목적함수의 구조를 확인해야 하며 정보를 다양하게 고른다는 말만으로 submodularity가 증명되지는 않습니다.

이 단원은 센서 네 개와 대상 네 개를 사용합니다. 센서의 대상 mask는 비트 1,2,4,8의 합입니다. 센서 집합 mask의 비트 i는 센서 i를 선택한다는 뜻입니다. 센서를 고르는 mask와 그 센서들이 덮는 대상의 합집합 mask를 구분해야 합니다. 조회 집합 A와 B는 정의를 확인하는 입력이며 최적화 예산 k와 독립입니다.

집합 함수와 한계 이득

센서 i가 덮는 대상을 T_i라 할 때

$$f(S)=\left|\bigcup_{i\in S}T_i\right|,\qquad \Delta(e\mid S)=f(S\cup\{e\})-f(S)$$

로 정의합니다. 빈 집합의 값이 0이라 정규화된 함수입니다. 센서를 더해도 이미 덮인 대상을 잃지 않으므로 단조 증가합니다. 한계 이득은 e가 덮지만 S에서는 아직 덮이지 않은 대상의 수입니다. e 자체가 빈 센서가 아니어도 이득은 0일 수 있습니다.

화면의 값은 정확한 작은 정수입니다. 표본 잡음이나 학습된 점수, 숨은 불확실성 모형이 있는 예제는 아닙니다. 학습한 surrogate 목적함수에 적용하려면 구조와 추정 오차를 새로 분석해야 합니다.

Submodularity는 조건이 있는 비교입니다

수익 체감 정의의 전제와 결론은

$$A\subseteq B,\quad e\notin B \quad\Longrightarrow\quad \Delta(e\mid A)\ge\Delta(e\mid B).$$

커버리지에서는 B에서도 덮이지 않은 대상이 A에서도 덮이지 않은 대상의 부분집합입니다. 두 집합을 T_e와 교집합하고 원소 수를 세면 부등식을 얻습니다. 기존 센서가 더 많다고 이미 알려진 대상이 다시 새로운 대상이 되지는 않습니다.

동치인 집합 격자 정의는

$$f(A)+f(B)\ge f(A\cup B)+f(A\cap B).$$

입니다. 커버리지에서는 대상마다 확인할 수 있습니다. A와 B 양쪽에서 덮인 대상은 왼쪽에 2를 기여하며 오른쪽에서는 합집합에 1, 교집합에 최대 1을 기여합니다. 한쪽에서만 덮인 대상은 양변에 1입니다. 유한 집합 함수에서 두 정의는 동치지만 정규화와 단조성은 별도의 성질입니다.

일부러 비교 조건이 틀린 입력도 허용합니다. 원래 한계 이득은 계산하되 A⊆B 및 e∉B가 성립하지 않으면 인증된 차이는 제공하지 않습니다. 전제를 만족하지 않은 비교가 정리의 반례인 것은 아닙니다.

더하기 모형과 상보성

Modular 함수는 원소별 고정 가치를 더하며 집합 격자 부등식이 등호입니다. 겹치는 커버리지는 일반적으로 단순 합이 아닙니다. 반대로 상보성이 있으면 다른 원소를 고른 뒤 추가 이득이 커질 수 있습니다. 예를 들어 센서 0과 1을 모두 고를 때만 1, 아니면 0인 h(S)를 생각해 봅시다. 정규화되고 단조 증가하지만 센서 1의 이득은 빈 집합에서 0, 센서 0을 고른 뒤에는 1입니다. Submodular가 아닙니다.

이 상보성 함수는 개념 반례이며 실습의 대체 목적함수로 구현한 것은 아닙니다. 단조성만으로 아래 greedy 보장을 적용할 수 없는 이유를 설명합니다.

현재 이득으로 고르는 Greedy

개수 제약 |S|<=k에서 greedy는 빈 집합으로 시작해 현재 한계 이득이 가장 큰 미선택 센서를 반복해서 추가합니다. 정확한 동률이면 작은 번호를 고릅니다. 선택 계산은 정확 최적해를 참조하지 않습니다. 이득이 0이어도 예산만큼 고르며 이 단조 모형에서는 0에서 멈추어도 가치는 같습니다.

별도 전수 열거는 센서 부분집합 16개 중 크기가 k 이하인 집합을 평가합니다. 최적값과 가능한 최적 집합들을 구하고, 대표는 크기가 작고 그다음 mask가 작은 집합으로 고릅니다. 한 대표를 표시했다고 유일해가 되는 것은 아닙니다. 작은 예제라 최적값을 확인할 수 있는 것이며 일반 문제에서 greedy가 정확한 해법이라는 뜻은 아닙니다.

Greedy가 정확하지 않은 손계산

대상 mask (3,5,10,1)은 T0={0,1}, T1={0,2}, T2={1,3}, T3={0}입니다. 예산 2에서 센서 0·1·2의 첫 이득은 모두 2라 번호가 작은 센서 0을 고릅니다. 다음에는 센서 1·2의 이득이 각각 1이므로 센서 1을 고릅니다. 센서 mask는 3, 대상 합집합 mask는 7이며 가치는 3입니다.

반면 센서 1과 2를 고르면 모든 대상을 덮어 최적 센서 mask 6, 가치 4를 얻습니다. 관측 비율은 3/4, 가산 손실은 1입니다. A가 빈 집합, B가 센서 0을 포함하고 e=1이면 한계 이득은 2와 1입니다. A={0}, B={0,1}, e=3이면 대상 0이 이미 덮여 두 이득은 모두 0입니다.

A={1}, B={0}, e=1로 바꾸면 원래 이득은 0과 1입니다. 하지만 A⊆B가 아니라 submodularity 위반이 아닙니다. 인증된 비교는 제공하지 않습니다.

가정에서 Greedy 경계를 유도하기

정규화·단조 증가·submodular 함수와 개수 제약 k>=1을 가정합니다. 최적 집합을 O, i단계의 greedy 집합을 G_i라 하면 단조성과 수익 체감으로

$$f(O)-f(G_i)\le\sum_{e\in O\setminus G_i}\Delta(e\mid G_i) \le k\max_{e\notin G_i}\Delta(e\mid G_i).$$

Greedy는 이 최대 이득을 고릅니다. 따라서 다음 남은 간극은 이전 간극의 1-1/k배 이하입니다. 빈 집합 값 0에서 k번 진행하면

$$f(G_k)\ge\left[1-\left(1-\frac1k\right)^k\right]f(O) \ge(1-1/\mathrm e)f(O).$$

마지막 식의 수학적 e는 지수함수의 밑이며 조회 센서 e와 다릅니다. k=2의 finite-k 계수는 3/4이고 위 예제가 그 경계에 도달합니다. 보장은 성능의 하한이지 항상 같은 비율이거나 정확 최적이라는 약속이 아닙니다. 다른 제약, 비단조 목적함수나 상보성에는 다른 분석이 필요합니다.

k=0에서는 greedy와 가능한 최적값이 모두 0이고 계수 식을 계산하지 않습니다. 최적값이 0이면 관측 비율은 0/0이라 제공하지 않습니다. 양의 k에서 보장 가치는 0일 수도 있습니다. 임의로 완벽한 비율 1을 넣지 않고 경우를 구분합니다.

두 도식과 예산 곡선 읽기

행렬은 각 센서가 덮는 대상을 보여줍니다. 왼쪽 A/B 표시는 센서 집합의 구성이고 파란 행 테두리는 조회할 e입니다. 아래 채움 원은 기존 커버리지, 점선 원은 새로 덮인 대상입니다. 두 번째 도식은 greedy가 고른 순서·이번 이득·누적 가치를 보여주며 현재 예산을 파란 테두리로 표시합니다.

아래 곡선은 시간 대신 센서 예산을 바꿉니다. 파랑은 greedy, 주황은 독립 최적값입니다. 관측 비율, 일반 보장 계수, 보장 가치를 별도 readout으로 제공합니다. 한 예제에서 관측 비율과 경계가 같다고 모든 예제가 최악 경계에 도달하는 것은 아닙니다.

문제와 해설

문제: 모든 대상 mask가 0이고 k=2이면 최적값·비율·보장은 무엇일까요?

해설: 두 값은 모두 0, 비율은 제공하지 않으며 finite-k 계수는 3/4, 보장 가치는 0입니다. Greedy는 영 이득 센서 두 개를 고를 수 있지만 대표 정확 최적해는 빈 집합입니다.

문제: 대상이 겹치지 않는 (1,2,4,8)에서는 greedy가 정확할까요?

해설: 센서마다 새로운 대상 하나가 생기므로 두 값 모두 k입니다. 이득이 같다고 최적 집합이 유일한 것은 아닙니다.

문제: Submodularity면 센서를 추가할 때 반드시 엄격히 좋아질까요?

해설: 아닙니다. 단조성은 영 이득을 허용하며 중복 커버리지는 완전히 불필요할 수 있습니다. Submodularity 자체는 음이 아닌 이득조차 요구하지 않습니다. 여기의 커버리지에는 단조성도 추가로 성립합니다.

연구와 연결하기

Nemhauser·Wolsey·Fisher의 원 논문은 명시된 가정 아래 고전적인 greedy 경계를 분석합니다. 네 센서 구성과 조건부 진단은 교재를 위한 구체적인 예제입니다. AI 데이터 선택 목적함수에 옮길 때는 커버리지라는 이름만으로 보장을 옮기지 말고 실제 구조적 가정을 증명하거나 점검해야 합니다.