독립(independence)이란 무엇인가 (4): 그리디 알고리즘 예시와 서브 모듈러 함수

그래픽 매트로이드 사례: 크루스칼 알고리즘

크루스칼 알고리즘에 대해 알기 위해 먼저 그래프의 한 종류인 최소 신장 트리(MST)를 알아야 한다.

그래프 $G = (V, E)$가 주어져 있다고 하자.
각 간선 $e \in E$에는 비용(weight)이 존재한다.
우리는 다음 조건을 만족하는 간선 집합을 찾고자 한다:

• 모든 정점이 연결되어 있어야 한다 (연결 그래프)
• 사이클이 없어야 한다 (트리 구조)
• 간선들의 비용 합이 최소여야 한다 (최소 비용)

이러한 간선 집합을 최소 신장 트리(Minimum Spanning Tree, MST)라고 한다.
MST는 항상 정점 수가 $|V|$개일 때 간선 수는 $|V| - 1$개이다.

정점과 간선이 주어져 있을 때,
크루스칼 알고리즘(Kruskal's Algorithm)은 MST를 구하기 위한 대표적인 탐욕 알고리즘이다.
작동 방식은 다음과 같다:

• 모든 간선을 비용 오름차순으로 정렬한다.
• 정렬된 간선들 중에서 하나씩 순서대로 다음 조건을 확인한다:
  → 이미 선택한 간선들과 함께 사이클이 생기는가?
• 사이클이 생기지 않으면 간선을 선택한다.
• 사이클이 생기면 그 간선은 건너뛴다.
• 선택된 간선이 $|V| - 1$개가 될 때까지 위 과정을 반복한다.

이 방식은 매 순간 가장 “저렴한” 간선을 고르고 선택된 간선 집합의 독립성(사이클 없음)을 유지하는 그리디한 접근 방식이다.

간선 집합의 독립성 – 그래픽 매트로이드 관점

앞서 우리는 그래프에서 사이클이 없는 간선 집합이 독립이라는 사실을 확인했다.
이는 정확히 그래픽 매트로이드(Graphic Matroid)의 정의와 일치한다.

정의:
그래프 $G = (V, E)$에 대해,
간선 집합 $I \subseteq E$가 사이클을 포함하지 않을 때 이를 독립 집합이라고 정의하면 $(E, \mathcal{I})$는 매트로이드를 이룬다.

즉, 사이클 없음 $\iff$ 독립성
→ 크루스칼 알고리즘은 매 단계마다 이 조건을 검사하는 것이다.

---

매트로이드 공리와 크루스칼 알고리즘의 일치

매트로이드는 다음 세 가지 공리를 만족해야 한다.
크루스칼 알고리즘은 이 공리들과 정확히 일치한다:

(1) 공집합은 항상 독립이다
→ 아무 간선도 선택하지 않은 초기 상태는 자명하게 사이클이 없음

(2) 독립 집합의 모든 부분집합도 독립이다
→ 사이클이 없는 간선 집합의 일부를 골라도 역시 사이클 없음

(3) 확장 가능성 공리
→ 더 큰 독립 집합이 있다면
→ 그 중 일부는 현재 집합에 추가해도 여전히 독립이다

크루스칼 알고리즘은
→ 매트로이드의 세 공리를 모두 만족하는
→ 그래픽 매트로이드의 독립 집합 위에서의 그리디하게 확장하는 과정이다.

---

Greedy Optimality – 왜 항상 최적인가?

매트로이드 위에서는

• 선택이 항상 독립성을 유지하고
• 더 큰 독립 집합으로 확장 가능한 구조이므로
  → 탐욕적으로 선택을 누적해도 전역 최적 해에 도달할 수 있다.

즉, 크루스칼 알고리즘은 다음을 보장한다:

• 비용이 가장 낮은 간선부터 선택하되
• 사이클이 생기지 않도록 선택하며
• 이 과정이 항상 전체 최적 구조로 확장된다.

MST를 만드는 크루스칼 알고리즘의 예시

이번 예시는 간선의 비용은 낮지만
선택 순서에 따라 사이클이 유발될 수 있는 구조를 포함한다.
크루스칼 알고리즘이 어떻게 가중치 오름차순 + 사이클 조건만으로 선택을 누적하며,
결국 전역 최적의 최소 신장 트리(MST)를 완성하는지 보여준다.

정점: A, B, C, D, E, F
간선 및 가중치는 다음과 같다:

간선	연결	가중치
e₁	A–B	1
e₂	A–C	1
e₃	B–C	1
e₇	E–F	1
e₄	B–D	2
e₅	C–E	2
e₉	C–F	2
e₆	D–E	3
e₈	A–F	4

크루스칼 알고리즘의 작동 과정:

1. e₁(A–B): 비용 1, 사이클 없음 → 선택
2. e₂(A–C): 비용 1, 사이클 없음 → 선택
3. e₃(B–C): 비용 1, A–B–C가 이미 연결됨 → 사이클 발생 → 제외
4. e₇(E–F): 비용 1, E–F 모두 고립 → 사이클 없음 → 선택
5. e₄(B–D): 비용 2, D는 아직 미연결 → 사이클 없음 → 선택
6. e₅(C–E): 비용 2, C–A–B–D와 E–F가 분리됨 → 사이클 없음 → 선택
7. e₉(C–F): 비용 2, C와 F는 이미 연결됨 → 사이클 발생 → 제외
8. e₆(D–E): 비용 3, D와 E는 이미 연결됨 → 사이클 발생 → 제외
9. e₈(A–F): 비용 4, A와 F는 이미 연결됨 → 사이클 발생 → 제외

최종 선택 간선: e₁, e₂, e₇, e₄, e₅
총 비용: 1 + 1 + 1 + 2 + 2 = 7
정점 수: 6 → 간선 수 5 → MST 조건 만족
사이클 없음 + 전체 연결 + 비용 최소 → MST 완성

이 예시는 크루스칼 알고리즘이
단순히 비용 순으로 탐색하면서도 매번 사이클 조건 하나만으로 정확한 선택을 한다는 점을 보여준다.
이는 매트로이드 관점에서 보면 그래픽 매트로이드의 독립 조건을 만족시키는 과정과 정확히 일치한다.

1. 그래픽 매트로이드란 무엇이고, 구조란 무엇인가

어떤 그래프 G = (V, E)가 있다.

이 그래프에서 사이클이 없는 간선 집합들은 모두 독립 집합이라 부른다.

이때 이 독립 집합들의 집합 전체를 ℐ라 하고 (E, ℐ)는 매트로이드가 된다.

즉, 그래픽 매트로이드란 ‘사이클이 없는 간선들의 집합’을 독립 집합으로 간주하는 구조이다.

‘구조적 제약만으로 탐욕 선택을 보장’한다는 말의 정확한 뜻은 다음과 같다.

선택 가능한 조합(즉 독립 집합들)의 모양이 매트로이드라는 특수한 구조를 갖고 있으면 가중치 기준으로 탐욕적으로 항목을 선택해도 항상 최적 해가 된다.

예: Prim 알고리즘은 항상 가중치가 가장 낮은 경계 간선을 하나씩 추가한다. 탐욕적 선택이 잘못되지 않으려면 현재까지의 선택에 새로운 간선을 추가하더라도 여전히 독립 집합(사이클이 없는 집합)으로 남아야 한다. 그리고 항상 그렇게 확장 가능한 구조가 매트로이드 구조이다.

이 구조는 ‘기여도’를 평가하지 않는다. Prim 알고리즘은 ‘지금 어떤 간선이 연결되면 가장 적은 비용으로 연결되냐’만 본다. 각 간선이 전체에 얼마나 이득을 주는가 얼마나 유용한가라는 함수적 개념은 전혀 없다. 단지 지금 사이클만 안 생기면 되고 가장 비용이 적으면 고른다.

2. Submodular 함수는 왜 필요한가

현실의 많은 문제는 다음과 같이 구성된다.

• 어떤 항목(예: 센서 피처 광고 팀원 등)을 선택한다.
• 항목들을 여러 개 조합할 수 있다.
• 각 조합에 대해 전체 성과를 평가하는 함수 f(S)가 있다.
• 우리는 이 성과를 최대화하려고 한다.

이때는 단순히 ‘이 항목을 고르면 독립이냐 아니냐’가 중요한 게 아니다. 이 항목을 추가하면 전체 성과가 얼마나 증가하는가가 핵심이다.

예를 들어 광고 세트를 고를 때 유사한 광고는 중복이 많아 성과가 떨어질 수 있다. 센서를 고를 때 서로 가까운 센서는 유사한 데이터를 제공해 기여도가 떨어진다. 피처를 고를 때 이미 비슷한 피처가 선택되어 있으면 성능 향상 폭이 작다.

이처럼 항목을 고를수록 한계 기여(marginal gain)가 줄어드는 함수 구조가 바로 Submodular 함수이다.

매트로이드가 ‘선택 가능한 조합의 구조’를 다루는 것이라면 Submodular 함수는 ‘선택된 조합의 성과를 어떻게 계산할 것인가’를 다룬다.

구분	매트로이드	Submodular 함수
관점	어떤 조합이 유효한가 (선택 구조)	각 조합이 얼마나 좋은가 (성과 평가)
주 대상	독립 집합 (사이클 없음 선형 독립 등)	기여도 함수 f: 2^E → ℝ
탐욕 선택의 결과	항상 전역 최적 해	근사 최적 해 (1 − $\frac{1}{e}$ 비율)
예시	Prim 알고리즘 Kruskal 알고리즘	피처 선택 센서 배치 집합 커버 문제

Prim 알고리즘과 Submodular 함수 기반 확장

앞서 우리는 그래픽 매트로이드 구조 위에서 Prim 알고리즘이 어떻게 작동하는지를 분석하였다. Prim 알고리즘은 최소 신장 트리(MST)를 구성하는 알고리즘으로 현재 선택된 정점 집합에서 연결 가능한 간선들 중 가중치가 가장 낮은 간선을 반복적으로 선택하여 신장 트리를 확장해 나간다. 이러한 선택 과정이 항상 전역 최적 해인 MST를 산출할 수 있는 이유는 그래픽 매트로이드의 공리 구조가 Prim 알고리즘의 탐욕적 선택 방식과 정확히 대응되기 때문이다.

Prim 알고리즘 – 매트로이드 공리 대응

Prim 알고리즘의 탐욕적 구조가 매트로이드의 세 가지 공리와 어떻게 맞닿는지를 구체적으로 짚어보자.

• 공집합 독립성 Prim 알고리즘의 초기 상태에서는 하나의 시작 정점 u₀만이 선택되어 있고 이 상태에서는 어떠한 간선도 포함되지 않는다. 이 상태는 당연히 사이클을 형성하지 않으므로 그래픽 매트로이드에서의 공집합 독립성 공리를 만족한다.
• 부분집합 보존성 Prim 알고리즘이 선택한 간선 집합이 독립 집합이었다면 그 어떤 부분집합도 역시 사이클을 포함하지 않게 된다. 이는 매트로이드의 두 번째 공리 즉 독립 집합의 부분집합은 여전히 독립이라는 성질과 일치한다.
• 확장 가능성 현재 선택된 독립 집합이 있고 그보다 더 큰 독립 집합이 존재한다면 매트로이드 구조에서는 항상 현재 집합의 원소 하나를 대체하여 더 큰 집합으로 확장할 수 있다. 이 공리는 이미 설명한 바와 같이 Prim 알고리즘의 순차적 확장 과정에 직접적으로 대응된다. Prim은 항상 독립 조건(사이클 없음)을 유지하면서 새로운 간선을 추가할 수 있기 때문이다.

이러한 세 가지 공리와의 대응은 다음 사실을 보장한다. → Prim 알고리즘이 선택할 수 있는 간선들이 그래픽 매트로이드 위의 독립 집합을 이루고 있으며 각 단계의 선택이 항상 그 독립성을 유지하도록 구성되어 있다는 점이다.

따라서 가중치가 모두 양수이고 그래프가 연결되어 있는 경우 Prim 알고리즘은 반복적인 지역 최적 선택만으로도 전역 최적 해인 MST를 정확히 산출할 수 있다.

---

관점을 전환하며: 선택 구조에서 선택 기여로

우리는 지금까지 탐욕 알고리즘이 작동하기 위한 구조적 조건에 집중했다. 예를 들어 그래픽 매트로이드에서는 사이클이 없는 간선 집합만을 선택할 수 있고, 이러한 선택 가능성 자체의 구조가 최적성을 보장하는 핵심이었다.

그러나 현실의 많은 문제는 단지 무엇이 선택 가능한가뿐 아니라 선택한 항목이 얼마나 성과에 기여하는가를 함께 고려해야 한다. 즉, 선택 가능성만으로는 충분하지 않고 각 항목이 얼마나 유용한지를 평가할 수 있는 함수적 기준이 요구된다.

이제 우리는 그러한 기여도를 수치화하여 평가하고 그것을 기반으로 탐욕적으로 항목을 선택하는 함수 중심의 탐욕 알고리즘으로 시선을 옮긴다.
이때 등장하는 개념이 바로 Submodular 함수이다.

Submodular 함수는 매트로이드처럼 가능한 조합의 모양에 주목하는 것이 아니라 각 조합의 기여도를 직접 평가하는 방식이다. 즉, 어떤 항목을 추가했을 때 전체 성과가 얼마나 향상되는지를 계산하며, 이를 통해 탐욕 알고리즘이 어느 정도 성능을 보장할 수 있는지 설명하는 수학적 틀을 제공한다.

매트로이드 기반 탐욕 알고리즘
→ 선택의 가능성에만 집중
→ “적은 비용이라면 넣고 사이클만 안 생기면 된다”
→ 기여도를 묻지 않는다
→ 그런데도 항상 최적 해를 구할 수 있다 (매트로이드 구조 덕분)

Submodular 함수 기반 탐욕 알고리즘
→ 선택의 기여도에 집중
→ “지금 넣었을 때 얼마나 도움이 되는가”를 매번 계산
→ 구조 제약도 함께 고려 가능 (예: 매트로이드 조건과 함께 사용)
→ 최적은 아니지만 (1 − $\frac{1}{e}$) 정도의 근사 보장이 가능

Submodular 함수 – 정의와 수학적 성질

우선 개념부터 정확히 정리한다.

• E는 선택 가능한 전체 항목들의 집합이다.
• 이 집합 E의 부분집합들 2^E에 대해 실수 값을 대응시키는 함수 f: 2^E → ℝ를 고려한다.
• 함수 f가 다음 두 조건을 만족하면 Submodular하고 단조 증가하는 함수라 한다.

단조 증가성 (Monotonicity)

∀ A ⊆ B ⊆ E에 대해 f(A) ≤ f(B)

Submodularity (아첨성 또는 준볼록성)

∀ A ⊆ B ⊆ E, x ∉ B에 대해 f(A ∪ {x}) − f(A) ≥ f(B ∪ {x}) − f(B)

이는 항목 x를 선택했을 때의 한계 이득(marginal gain)이 기존 선택 집합이 작을수록 더 크고 클수록 작아진다는 뜻이다.

Submodular 함수의 예시 – 센서 배치 문제

센서를 배치하여 정보를 최대한 수집하고자 하는 문제를 가정하자. 설치 가능한 센서의 집합을 E = {s₁, s₂, s₃}라 하자.

각 센서 조합에 대한 정보량 함수 f는 다음과 같다.

선택 집합	f(S) (정보량)
{s₁}	5
{s₂}	4
{s₃}	3
{s₁, s₂}	8
{s₁, s₃}	7
{s₂, s₃}	6
{s₁, s₂, s₃}	9

s₁부터 순차적으로 선택할 때의 한계 이득은 다음과 같다.

• Δ₁ = f({s₁}) − f(∅) = 5
• Δ₂ = f({s₁, s₂}) − f({s₁}) = 3
• Δ₃ = f({s₁, s₂, s₃}) − f({s₁, s₂}) = 1

이처럼 선택이 진행될수록 한계 이득이 5 → 3 → 1로 감소함을 볼 수 있다. 이것이 Submodular 함수의 핵심적 특징이다.

---

Submodular 함수 위에서의 탐욕적 선택 – 근사 보장

지금까지 Submodular 함수의 정의와 성질을 살펴보았다. 이제 이 함수를 기반으로 하는 탐욕 알고리즘이 어떤 조건 하에서 성능을 보장받을 수 있는지 즉 최적 해에 얼마나 가까운 결과를 산출할 수 있는지를 수학적으로 분석한다. 이를 위해 다음과 같은 조합 최적화 문제를 고려한다.

• 전체 항목 집합 E 중에서 k개를 선택하여 f(S)가 최대가 되도록 한다.
• 단 선택 제약은 매트로이드의 독립 집합 조건을 만족해야 한다.

이때 탐욕 알고리즘은 매 단계마다 아직 선택되지 않은 항목 중에서 현재 집합 S에 추가했을 때 한계 이득 f(S ∪ {x}) − f(S)가 가장 큰 항목 x를 선택한다. 이 과정을 k번 반복한다.

그 결과 얻어진 집합을 g라 하고 전역 최적 해를 opt라 하면 다음이 성립한다.

f(g) ≥ (1 − $\frac{1}{e}$) · f(opt)

이 보장은 다음 조건에서만 성립한다.

• f는 Submodular하고 단조 증가한다
• 선택 제약은 매트로이드 구조이다
• 선택 가능한 항목 수는 k개로 제한된다

이 보장은 교환 논증에 기반하여 증명된다. 탐욕 해 g와 최적 해 opt 간의 차이를 항목 단위로 비교하고 서로 교환할 때 성능 손해가 얼마나 줄어드는지를 단계별로 분석한다. 그 결과 누적 성능 차이가 기하급수적으로 줄어들며 (1 − $\frac{1}{e}$) 비율까지 수렴한다.

사례

집합 커버 문제 예시:

전체 원소 집합 U = {a, b, c, d, e}가 있고 부분집합의 모음 𝒮 = {S₁, S₂, S₃}가 다음과 같다고 하자.

• S₁ = {a, b}
• S₂ = {b, c, d}
• S₃ = {d, e}

각 부분집합을 하나의 항목으로 간주하고 함수 f(S)는 선택한 집합들의 합집합 원소 개수로 정의된다.

f(S) = |⋃_{Sᵢ ∈ S} Sᵢ|

이 함수는 다음과 같은 성질을 가진다.

• 집합을 더 많이 선택할수록 커버하는 원소 수는 증가한다 → 단조 증가
• 이미 많이 커버한 상태에서는 새로운 집합 하나의 기여가 작아진다 → Submodular

피처 선택 문제 예시:

예측 모델을 학습할 때 사용할 수 있는 피처들이 E = {x₁, x₂, …, xₙ}이라 하자. 함수 f(S)는 선택된 피처 집합 S를 사용하여 학습된 모델의 검증 정확도 또는 R² score로 정의된다.

현실에서는 새로운 피처를 추가할수록 모델 성능은 상승하지만 이미 중요한 피처가 포함된 경우 그 상승폭은 작아지는 경향이 있다.

따라서 실제 데이터 기반에서 학습된 f는 다음을 만족하는 경향이 있다.

• A ⊆ B일 때 f(A) ≤ f(B) → 단조 증가
• A ⊆ B, x ∉ B일 때 f(A ∪ {x}) − f(A) ≥ f(B ∪ {x}) − f(B) → Submodular

이 함수 f는 이론적으로 항상 Submodular 함수로 보장되지는 않는다. 그러나 실제 머신러닝 문제에서는 많은 경우 선택된 피처 집합이 커질수록 추가 피처의 기여도가 감소하는 경향이 관측된다. 즉 경험적으로 Submodular 구조에 근사하게 작동하는 경우가 많다. 이러한 성질 덕분에 탐욕 기반 피처 선택 알고리즘이 높은 성능을 보이는 구조적 근거가 된다.