Simple is not easy — 단순함을 찾는 어려움과 사고 도구

core-thesis-expressive-then-simple가 두 단계 분리를 제시했다. occam-mdl-kolmogorov가 단순함의 철학적 정당화를, vc-dimension-and-generalization이 수학적 정당화를, regularization-as-unified-pattern이 도구의 통합 시각을 다뤘다. 이 노트는 그 위에서 한 가지 사실을 직시한다 — 그렇다면 단순한 답은 어떻게 찾는가? 그리고 그게 왜 어려운가.

답: 어렵다. 매우. ML 전반에 깔린 greedy heuristic, convex relaxation, gradient descent + 정규화, 베이지안 샘플링은 모두 이 어려움을 우회하는 도구다. "단순함은 사고의 종착지가 아니라 정교한 도구를 통해 나오는 결과물"이라는 게 이 노트의 핵심.

한 그림으로

이 그림이 ML 도구 catalog의 숨은 구조다. 책에서 따로따로 배우는 알고리즘들이 사실 같은 어려움을 다른 방향에서 우회하는 도구들.

왜 단순한 답을 찾기가 어려운가

세 종류의 어려움이 ML 전반에 흩어져 있다.

어려움 1 — 조합론적 폭발

Decision tree에서 최소 트리 찾기는 NP-complete (Hyafil & Rivest, 1976). 이미 decision-tree-structure-and-hypothesis에서 본 사실. 이걸 다시 보는 이유는 — 같은 어려움이 다른 모델에서도 반복된다.

공통점: "단순함"의 정의가 조합론적이라는 것. 노드 수, 0이 아닌 파라미터 수, leaf 수 — 모두 정수 단위의 개수. 이런 정수 단위 최적화는 본질적으로 어렵다 (mixed integer programming).

어려움 2 — Non-convex 최적화

NN 같은 모델은 단순함이 연속적인 양 (weight norm 등)이지만, 데이터 적합 부분이 non-convex다.

$\underbrace{L(w, D)}_{\text{non-convex}} + \lambda \|w\|^2$

Penalty가 convex라도 전체가 non-convex면 global minimum 보장이 없다. Local minimum, saddle point에 갇힐 수 있다. 그런데 실무에서는 이게 거의 작동한다 — 왜?

이게 modern ML의 신비 중 하나. Loss landscape가 우호적이라는 가설들이 있지만, 완전히 풀린 문제는 아니다.

어려움 3 — 가설 공간이 무한

함수 학습은 본질적으로 무한 차원 문제. 어떤 함수든 표현할 수 있는 가설 공간이라면 (예: 깊은 NN, kernel space), 그 안에서 단순한 함수를 어떻게 정의하고 찾는가?

이론적으로는 RKHS norm, function smoothness 등으로 정의되지만, 실제 알고리즘은 그 추상을 직접 못 푸는 경우가 많다.

우회 도구 — 어려움별로

Workaround 1 — Greedy heuristic

조합론적 어려움(어려움 1)을 피하는 가장 흔한 도구. 전역 최적을 포기하고, 매 단계 국소적으로 최선의 선택.

이론적 보장은 약하다 — global optimum과 임의로 멀어질 수 있다. 그러나 실용적으로는 잘 작동한다는 게 ML의 경험적 사실. 이 gap이 흥미로운 연구 영역.

Workaround 2 — Convex relaxation

NP-hard인 단순함 척도(L0 norm = 0이 아닌 원소 수)를 convex 근사(L1 norm = 절대값 합)로 바꾼다.

놀라운 결과(Donoho, Candès, Tao, ~2006): 특정 조건에서 L1 minimization의 해가 L0 minimization의 해와 일치한다. 이게 compressed sensing의 토대. NP-hard를 직접 풀지 않고 LP/QP로 풀 수 있다는 발견.

이 발상은 다른 영역에도 — semidefinite programming, sum-of-squares 등은 NP-hard 문제의 polynomial-time 근사 도구.

Workaround 3 — Gradient descent + regularization

비convex 어려움(어려움 2)을 정면 돌파하지 않고, 충분히 좋은 local minimum을 찾는 데 만족한다.

NN 학습이 정확히 이 형태:

• Loss landscape이 비convex
• SGD를 충분히 많은 step
• explicit + implicit regularization
• Local minimum에 도달하지만, 그게 generalization을 잘 함

이게 작동하는 이유는 modern ML의 미해결 문제. 가설:

• Loss landscape이 over-parameterized 영역에서 매우 평탄 (Hochreiter & Schmidhuber, 1997)
• SGD noise가 narrow minimum을 회피 (Keskar et al., 2017)
• Implicit bias of SGD가 low-norm 영역으로 흐름 (Soudry et al., 2018)

→ 이론이 따라잡지 못하는 동안 실용에서 먼저 작동한 사례.

Workaround 4 — Sampling and variational methods

Bayesian 시각으로 가면 단순함이 prior, 적합도가 likelihood. 그러나 posterior $P(h \mid D)$ 자체가 일반적으로 closed form 없음.

각 도구가 본질적인 어려움(posterior 자체의 복잡성)을 다른 방식으로 우회.

결국 단순함은 사고의 종착이 아니라 도구의 결과

이 노트의 핵심 명제:

"단순한 답"은 단순한 사고로 도달하지 않는다. 정교한 알고리즘 도구의 결과로 emergent하게 나타난다.

ML이 처음 사람을 헷갈리게 하는 부분이 여기. "단순한 모델이 좋다"는 격언과 "단순함을 찾기 위해 비convex SGD를 돌린다"는 실무 사이의 간극.

이 간극을 인지해야 ML을 사용하는 자세가 바뀐다:

• 모델 선택은 결과의 단순함을 추구하되, 그 단순함을 찾는 도구는 단순할 필요가 없다
• 정교한 도구의 hyperparameter는 단순함의 정도를 조절하는 dial
• 디버깅할 때 "이 도구가 어떤 종류의 단순함을 강제하고 있는가?"를 묻기

소프트웨어 공학과의 평행 — 왜 이 thesis가 ML 너머로 옮겨지는가

이 사고 패턴은 simple-not-easy (research/ai-era-software-fundamentals)에서 다룬 소프트웨어 공학 thesis와 정확히 같은 형태다.

같은 사고 형태: 표현력은 풍부하게 두되 (모델은 크게 / 코드는 풀어서 작성하되), 그 안의 단순한 영역을 정교한 도구로 찾아간다 (regularization / TDD + refactor + ADR).

이 평행이 우연이 아니다. 두 분야 모두 본질적으로 같은 인식론적 문제 — "데이터/요구사항이 underdetermine하는 가설 공간 안에서 단순한 답을 어떻게 고르는가" — 를 다루기 때문.

사고 도구로 일반화

새 ML 모델/방법을 만나거나 자기 모델을 디버깅할 때 쓸 수 있는 질문들.

1. 이 모델의 hypothesis space는? (core-thesis-expressive-then-simple 단계 1)
2. 그 안에서 무엇을 단순함으로 정의하나? (regularization-as-unified-pattern)
3. 그 단순함을 어떻게 찾는가? 어떤 도구로? (이 노트)
4. 그 도구가 부과하는 inductive bias는 뭔가? (greedy의 path-dependence, SGD의 implicit bias)
5. 이게 깨지는 영역은? (4번 축 — over-parameterization, double descent)

5번까지 답할 수 있으면 모델을 deep하게 이해한 것. 1-3만 답할 수 있으면 강의 수준, 4까지면 실무 수준, 5까지면 연구 수준.

약점 — 단순함을 강제하면 표현력이 망가진다

이 thesis의 가장 큰 한계이자 4번 축 follow-up의 출발점.

지금까지 논리: 표현력 큰 $H$ + 단순함 우회 도구 → generalization. 그런데:

• 표현력을 너무 작게 하면 underfitting (이건 이미 다룬 함정)
• 단순함을 너무 강하게 강제해도 underfitting
• 단순함을 너무 작게 강제하면? 즉 over-parameterized 모델을 거의 regularization 없이 두면?

직관적으로 답: overfitting. 그러나 modern NN의 경험적 사실은 다르다 — over-parameterized 모델이 implicit하게 일반화한다. 이게 occam-mdl-kolmogorov 4단계의 incomputable 처방을 modern ML이 몸으로 풀어낸 것일 수도 있고, 단순함 thesis가 깨지는 새 영역일 수도 있다.

이 균열의 형식화:

• Double descent (Belkin et al., 2019)
• Lottery ticket hypothesis (Frankle & Carbin, 2019)
• Scaling laws (Kaplan et al., 2020)
• Implicit regularization in SGD

→ 4번 축 follow-up에서 본격 다룰 영역.

인사이트 — 이 deep dive 전체의 종합

다섯 노트를 통해 도달한 명제들.

1. 표현력과 단순함은 분리된 두 결정. 이걸 두 단계로 명시화하는 게 ML 모델 분석의 출발 (core-thesis-expressive-then-simple).

2. 단순함은 미적 선호가 아니라 정보이론적 명제. Solomonoff prior가 그 이론적 정점, regularization이 그 실용적 그림자 (occam-mdl-kolmogorov).

3. 표현력이 generalization gap을 결정한다. PAC bound가 simple-vs-expressive thesis의 수학 (vc-dimension-and-generalization).

4. 모든 regularizer는 한 원리의 변형. Penalty / constraint / Bayesian prior 동등성, 그리고 effective hypothesis space 축소라는 공통 메커니즘 (regularization-as-unified-pattern).

5. 단순한 답은 정교한 도구의 결과물. Greedy / convex relaxation / SGD / sampling이 본질적 어려움을 다른 방향에서 우회 (이 노트).

6. 이 사고 형태는 ML 너머로 일반화된다. 소프트웨어 공학의 simple-not-easy가 같은 인식론을 공유.

7. 그러나 thesis의 한계가 있다. Modern NN의 over-parameterization 영역이 이 처방을 흔든다 — 4번 축 follow-up.

연결

• 핵심 명제 → core-thesis-expressive-then-simple
• 철학적 뿌리 → occam-mdl-kolmogorov
• 수학적 토대 → vc-dimension-and-generalization
• 도구의 통합 → regularization-as-unified-pattern
• 소프트웨어 공학 평행 → simple-not-easy (research/ai-era-software-fundamentals)
• 강의 맥락 → bias-variance-tradeoff, decision-tree-structure-and-hypothesis
• 다음 deep dive (4번 축) → double descent, lottery ticket, scaling laws, implicit regularization