0. Summary

기본 정보 : 한국경영과학회 추계학술대회 논문집,2005.10, 혼합정수 선형계획법 기반의 비선형ㆍ비볼록 패턴 분류 기법 (pp. 459–462, 저자 김광수). 같은 연구 흐름의 영문 논문은 Ryoo & Kim, Separation of Data via Concurrently Determined Discriminant Functions, TAMC 2007, LNCS 4484, pp. 533–541, DOI 10.1007/978-3-540-72504-6_48이다. 본 글의 영문 제목은 이 계열 연구를 가리키며, 두 문헌에 공통된 모델 아이디어를 기준으로 정리한다.

연구 배경

패턴 분류를 수리계획법으로 푸는 접근은 1960년대 Mangasarian의 선형계획(LP) 기반 선형 판별 이후 꾸준히 연구되었고, SVM도 이차계획(QP)이라는 수리계획으로 볼 수 있다. 그러나 LP/MILP 기반 분류 연구의 대부분은 하나의 초평면으로 두 집단을 나누는 선형 판별에 머물렀다. 비선형 경계가 필요할 때는 (1) 커널 등으로 특징 공간을 확장하거나, (2) 여러 초평면을 조각별(piecewise)로 이어 붙이는 방법을 썼는데, 후자는 함수 개수가 늘수록 변수와 제약식이 급격히 늘어나고 함수들을 순차적으로 하나씩 결정하면 전체 최적성이 보장되지 않는다. 특히 한 집단이 다른 집단을 둘러싸는 비볼록(nonconvex) 형태는 볼록 결합 기반 모델로는 다루기 어렵다. 즉 “여러 개의 비선형 판별함수를 하나의 최적화 문제 안에서 동시에, 추가 변수·제약 없이 결정하는 방법”이 비어 있었다.

제안 방법

사용자가 제공하는 유한 개의 단순한 비선형 판별함수(일차·이차 함수 등)의 계수와 결정 경계를 하나의 혼합 0-1 정수 선형계획(MILP) 모델 안에서 동시에 결정함으로써, 비선형·비볼록 경계를 가진 두 집단을 분리하는 분류기를 만든다. 판별함수를 계수에 대해 선형인 기저 함수의 결합 $f_k(x)=\sum_j w_{kj}\phi_{kj}(x)+b_k$로 두면 함수 자체는 비선형이어도 결정 변수에 대해서는 선형 제약이 되어 MILP 틀 안에 들어온다. 각 데이터가 어느 함수에 의해 어느 쪽으로 분류되는지를 0-1 변수로 표현하고 함수들의 조합으로 최종 결정 영역을 정의하므로 비볼록 영역도 표현 가능하다. 오차 척도로는 오분류 데이터가 경계에서 떨어진 정도를 $\ell_1$ 거리 노름으로 재는 새로운 척도를 정의해 그 합을 최소화한다. 주어진 판별함수들의 상호작용과 개별 역할을 함께 고려해 데이터를 가장 잘 분리하는 단순한 결정 경계를 구현하는 것이 모델의 핵심이다.

발견 사실

인공적으로 생성한 2차원 데이터, 즉 두 집단의 경계가 비선형이면서 비볼록(한 집단이 다른 집단을 부분적으로 감싸는 형태)인 분류 실험에서, 제안 모델은 주어진 데이터를 가장 잘 분리하는 가장 단순한 비선형·비볼록 결정 경계를 구현한다. 필요 이상으로 많은 함수를 쓰지 않으면서도 선형 모델이나 단일 이차 곡선으로는 불가능한 분리를 달성한다. 후속 영문 논문(Ryoo & Kim, 2007)에서는 같은 모델을 6개의 잘 알려진 데이터마이닝 데이터셋에 적용해 multisurface method, SVM, 문헌의 최고 결과와 비교했고, 지도학습에 효과적이고 유용하다고 결론지었다. 원문 접근이 제한되어 구체적 수치는 본 글에서 다루지 않는다.

핵심 기여

  1. 비선형 판별함수의 동시 결정(concurrent determination) : 여러 판별함수를 순차적으로 구하지 않고 하나의 MILP 안에서 모든 함수의 계수와 각 데이터의 배정을 함께 최적화해, 조각별 접근에서 잃는 전체 최적성을 회복하고 비볼록 결정 영역을 표현했다.
  2. $\ell_1$ 거리 노름 기반 오차 척도 : 오분류 거리를 $\ell_1$ 노름으로 재는 새 척도를 정의해 선형성을 유지하면서 이상치에 덜 민감한 목적함수를 얻었다.
  3. 추가 변수·제약 없는 복잡도 확장 : 기저 함수의 종류만 바꾸면 되므로 복잡도가 올라가도 모델의 변수·제약 구조가 크게 늘지 않으며, 결정 경계가 명시적 수식으로 나와 해석 가능성이 높다.

관련 개념

패턴 분류와 이진 분류

패턴 분류(pattern classification) 는 관측된 데이터(특징 벡터)를 미리 정해진 범주 중 하나에 배정하는 문제입니다. 학습 데이터로부터 범주를 가르는 규칙(분류기, 판별함수)을 찾고, 새 데이터에 그 규칙을 적용합니다.

🎯 1. 이진 분류의 정식화

범주가 두 개($A$, $B$)인 패턴 분류는 판별함수 $f(x)$를 두고 $f(x)\ge0$이면 $A$, $f(x)<0$이면 $B$로 배정하는 식으로, 결정 경계 $f(x)=0$을 학습하는 문제로 귀결됩니다.

판별함수의 형태 결정 경계 대표 방법
$f(x)=w^{T}x+b$ (선형) 초평면 LDA, 선형 SVM, Mangasarian의 LP 판별
$f(x)=\sum_j w_j\phi_j(x)+b$ (기저 함수의 선형 결합) 이차 곡선·곡면 등 이차 판별, 다항 커널 SVM
여러 $f_k$의 논리적 결합 조각별·비볼록 영역 조각별 선형 판별, 본 논문

두 집단이 선형 분리 불가능하면 비선형 판별함수가 필요하고, 한 집단이 다른 집단을 둘러싸면 단일 볼록 영역으로는 분리할 수 없습니다.

📐 2. 학습 문제로서의 분류

분류기 학습은 “학습 데이터에 대한 오분류를 최소화하는 $f$”를 찾는 최적화 문제입니다. 무엇을 오차로 재느냐에 따라 문제의 성격이 달라집니다.

오차 척도 성격
오분류 개수 0-1 손실. 비볼록·불연속이라 직접 최적화가 어려움
경계에서의 위반 거리 합 연속 손실. 노름 선택에 따라 LP($\ell_1$), QP($\ell_2$)로 풀림
마진 기반 SVM의 힌지 손실 + 마진 최대화 정규화

본 논문은 두 번째 범주에 속하며, 0-1 변수로 “어느 함수가 이 데이터를 담당하는가”라는 논리적 선택을 추가합니다.

💡 Key Takeaway 이진 분류는 결국 “결정 경계를 어떤 함수족에서 고를 것인가”와 “오차를 어떻게 잴 것인가”의 조합입니다. 본 논문은 함수족을 비선형 기저의 결합으로, 오차를 $\ell_1$ 거리로 고릅니다.

수리계획법과 혼합정수 선형계획법(MILP)

수리계획법(mathematical programming) 은 목적함수를 제약조건 아래에서 최적화하는 문제를 세우고 푸는 방법론입니다. 선형계획(LP), 정수계획(IP), 혼합정수계획(MIP), 비선형계획(NLP) 등으로 나뉘며, 분류 문제에 적용할 때는 “오분류 오차 또는 오분류 개수를 최소화”하는 목적함수와 “각 데이터가 올바른 쪽에 놓이도록 하는” 제약조건으로 모델을 세웁니다.

🧮 1. MILP의 정의와 분류 문제에의 적합성

혼합정수 선형계획법(MILP) 은 변수 일부는 정수(특히 0-1 이진), 나머지는 연속이며 목적함수와 제약식이 모두 선형인 최적화 문제입니다.

$$\min_{x,z}\ c^{T}x+d^{T}z\quad\text{s.t.}\quad Ax+Bz\le b,\ \ x\in\mathbb R^{n},\ \ z\in{0,1}^{m}$$

0-1 변수로 “이 데이터가 오분류되었는가”, “이 함수를 사용하는가”, “이 데이터는 어느 함수가 담당하는가” 같은 논리적 선택을 표현할 수 있어 분류 문제에 자연스럽게 맞습니다. 전형적으로 big-M 제약 $g(x)\le M\cdot z$ 형태로 “z=0이면 제약이 활성, z=1이면 비활성”을 구현합니다.

⚙️ 2. 풀이와 계산 복잡도

항목 내용
복잡도 일반적으로 NP-hard
알고리즘 branch-and-bound, cutting plane, branch-and-cut
솔버 CPLEX, Gurobi 등 상용 솔버로 중소 규모 문제의 최적해 획득 가능
장점 전역 최적해 또는 최적성 보장(gap)이 있는 해를 얻음. 경사 기반 학습처럼 국소해에 빠지지 않음
단점 데이터 수와 0-1 변수 수에 따라 풀이 시간이 지수적으로 늘어남

📜 3. 수리계획 기반 분류의 계보

시기 연구 내용
1965 Mangasarian, Linear and Nonlinear Separation of Patterns by Linear Programming LP로 선형 판별, 비선형은 특징 변환으로
1990년대 Multisurface method (Mangasarian 등) 여러 초평면을 순차적으로 생성해 조각별 선형 분리
1990년대 SVM (Vapnik 등) QP로 마진 최대화
2005–2007 본 논문 계열 (김광수; Ryoo & Kim) MILP로 비선형 판별함수 여러 개를 동시 결정
2010년대 이후 Optimal decision trees, hyper-box 분류 등 MILP로 해석 가능한 최적 분류기

💡 Key Takeaway MILP는 “무엇을 선택할지”를 0-1 변수로, “얼마나 틀렸는지”를 연속 변수로 함께 다룰 수 있는 언어입니다. 그 대가는 조합적 풀이 시간입니다.

문제 의식: 기존 LP/MILP 분류의 한계

기존 접근의 세 가지 한계가 본 논문의 출발점입니다.

🚧 1. 단일 초평면의 한계

LP/MILP 기반 분류 연구의 대부분은 하나의 초평면으로 두 집단을 나누는 선형 판별에 머물렀습니다. 선형 분리 불가능한 데이터에서는 오분류가 구조적으로 남습니다.

🧩 2. 조각별 접근의 한계

비선형 경계를 위해 여러 초평면을 조각별로 이어 붙이는 방법은 다음 문제를 가집니다.

문제 설명
변수·제약의 폭증 함수 개수가 늘수록 데이터 × 함수 조합만큼 변수와 제약식이 급격히 늘어남
순차 결정의 비최적성 함수들을 하나씩 순차적으로 결정하면 앞 단계의 선택이 뒤 단계를 제약해 전체 최적성이 보장되지 않음
볼록성 가정 볼록 결합 기반 모델은 한 집단이 다른 집단을 둘러싸는 비볼록 형태를 다루기 어려움

🔄 3. 커널 접근과의 대비

커널로 특징 공간을 확장하면 비선형 경계를 얻지만, 결정 경계가 원 공간에서 명시적 수식으로 드러나지 않아 해석 가능성이 떨어지고, 사용자가 “함수 개수 제한”이나 “오분류 비용” 같은 요구를 제약식으로 직접 넣기 어렵습니다. 본 논문은 명시적 비선형 함수 몇 개의 조합으로 경계를 쓰는 길을 택합니다.

💡 Key Takeaway 문제는 “비선형 경계를 만들 수 있는가”가 아니라 “여러 비선형 함수를 동시에, 비볼록하게, 추가 비용 없이 결정할 수 있는가”입니다.

제안 모델의 핵심 아이디어

제안 모델은 네 가지 설계 선택으로 요약됩니다. 아래는 2005년 국내 학회 논문과 2007년 영문 논문에 공통된 모델 아이디어를 재구성한 것이며, 원문의 정확한 기호와 제약식 번호는 접근 제한으로 확인하지 못했습니다.

🧱 1. 단순한 비선형 기저 함수의 결합

판별함수를 일차함수, 이차함수(원·타원·쌍곡선 등) 같은 계수에 대해 선형인 함수들의 모음으로 둡니다.

$$f_k(x)=\sum_{j}w_{kj}\,\phi_{kj}(x)+b_k,\qquad k=1,\dots,K$$

기저 $\phi$는 $x_1,\ x_2,\ x_1^2,\ x_1x_2,\ x_2^2,\dots$처럼 고정하므로, 함수 자체는 $x$에 대해 비선형이어도 결정해야 할 계수 $w,b$에 대해서는 선형 제약이 됩니다. 이 덕분에 MILP 틀 안에서 비선형 경계를 다룰 수 있습니다.

기저 선택 표현 가능한 경계
${x_1,x_2}$ 직선
${x_1,x_2,x_1^2,x_2^2}$ 축에 정렬된 타원·쌍곡선
${x_1,x_2,x_1^2,x_1x_2,x_2^2}$ 일반 이차 곡선

🔗 2. 함수들의 동시 결정 (concurrent determination)

여러 판별함수를 순차적으로 구하지 않고, 하나의 MILP 안에서 모든 함수의 계수와 각 데이터의 배정을 함께 최적화합니다.

  • 데이터 $i$가 어느 함수 $k$에 의해 어느 쪽으로 분류되는지를 0-1 변수 $z_{ik}$로 표현합니다.
  • 함수들의 조합(교집합·합집합)으로 최종 결정 영역을 정의합니다. 예를 들어 “집단 $A$는 $f_1\ge0$ 또는 $f_2\ge0$인 영역”처럼 합집합을 허용하면 비볼록 영역도 표현됩니다.
  • 각 함수의 상호작용(함께 어떤 영역을 만드는가)과 개별 역할(어떤 데이터를 담당하는가)이 하나의 목적함수 아래에서 동시에 평가됩니다.

이것이 영문 논문 제목의 “concurrently determined discriminant functions”가 뜻하는 바이며, 순차 결정의 비최적성을 해소하는 장치입니다.

📏 3. $\ell_1$ 노름 기반 오차 척도

오분류된 데이터가 결정 경계로부터 떨어진 정도를 $\ell_1$ 거리로 측정하는 새로운 오차 척도를 정의하고 그 합을 최소화합니다.

$$\min\ \sum_{i}e_i\quad\text{s.t.}\quad e_i\ \ge\ (\text{데이터 } i\text{의 경계 위반량}),\ \ e_i\ge0$$

노름 성질
$\ell_1$ 절댓값 합. 보조 변수로 선형 제약으로 표현 가능 → LP/MILP 유지. 제곱 오차보다 이상치에 덜 민감
$\ell_2$ 제곱 합. QP가 되어 MILP 틀을 벗어남
$\ell_\infty$ 최대 위반. 선형으로 표현 가능하지만 이상치 하나에 지배됨

🪶 4. 추가 변수·제약 없이 복잡한 분류기 생성

기저 함수의 종류만 바꾸면 되므로, 결정 경계의 복잡도가 올라가도 모델의 변수·제약 구조가 크게 늘지 않는다는 점을 강점으로 내세웁니다. 조각별 초평면 접근에서 함수 수에 비례해 변수가 폭증하던 것과 대비됩니다. 단, 기저 함수의 수는 늘어나므로 각 함수의 계수 변수는 기저 수만큼 증가합니다.

💡 Key Takeaway “비선형이지만 계수에 선형”, “여러 함수지만 한 문제”, “$\ell_1$이라서 선형” 세 가지가 맞물려 비볼록 분류기가 MILP 하나로 들어갑니다.

실험과 결과

실험은 2005년 논문에서는 인공 2차원 데이터, 2007년 영문 논문에서는 공개 데이터마이닝 데이터셋으로 이루어졌습니다. 원문 접근 제한으로 수치는 제시하지 않고 결과의 성격만 정리합니다.

🧪 1. 인공 2차원 데이터 (2005)

  • 데이터 : 두 집단의 경계가 비선형이면서 비볼록이 되도록, 예를 들어 한 집단이 다른 집단을 부분적으로 감싸는 형태로 구성했습니다.
  • 결과 : 제안 모델은 주어진 데이터를 가장 잘 분리하는 가장 단순한 비선형·비볼록 결정 경계를 구현합니다. 필요 이상으로 많은 함수를 쓰지 않으면서도 선형 모델이나 단일 이차 곡선으로는 불가능한 분리를 달성합니다.
  • 의미 : 2차원이라 결정 경계를 그림으로 직접 확인할 수 있어, 모델이 의도대로 비볼록 영역을 만드는지를 시각적으로 검증한 것입니다.

📊 2. 공개 데이터셋 비교 (2007, Ryoo & Kim)

항목 내용
데이터 잘 연구된 데이터마이닝 데이터셋 6개
비교 대상 Multisurface method, SVM, 문헌의 최고 결과
결론 제안 MILP 모델이 지도학습에 효과적이고 유용함

Multisurface method는 같은 수리계획 계보의 조각별 선형 분리 방법이므로, “동시 결정”의 효과를 가장 직접적으로 대비하는 baseline입니다.

✅ 3. 장점 정리

  • 결정 경계가 명시적인 수식(일차·이차 함수의 조합)으로 나오므로 해석 가능성이 높습니다.
  • 오분류 비용, 함수 개수 제한 등 사용자 요구를 제약식으로 바로 추가할 수 있습니다.
  • 전역 최적해(또는 최적성 보장이 있는 해)를 구할 수 있어 경사 기반 학습처럼 국소해에 빠지지 않습니다.

💡 Key Takeaway 실험의 메시지는 “정확도가 가장 높다”보다 “가장 단순한 비볼록 경계를 최적성 보장 아래 찾는다”에 있습니다. 해석 가능한 분류기라는 관점에서 읽어야 합니다.

한계와 열린 방향

제안 모델의 한계는 MILP 접근 일반의 한계와 이 모델 고유의 설계에서 옵니다.

⚠️ 1. 계산 복잡도

MILP는 데이터 수와 0-1 변수 수에 따라 풀이 시간이 지수적으로 늘어납니다. 데이터 $n$개, 함수 $K$개면 배정 변수만 $O(nK)$개의 0-1 변수가 생깁니다. 2차원 인공 데이터에서 보인 결과가 고차원·대규모 데이터로 확장되는지는 논문 범위 밖이며, 2007년 논문의 6개 데이터셋도 중소 규모입니다.

🧑‍🔧 2. 기저 함수의 수동 선택

기저 함수(일차·이차)를 사람이 미리 골라야 하며, 고차 다항식을 넣으면 특징 수가 조합적으로 늘어납니다. $d$차원에서 $p$차 다항 기저의 수는 $\binom{d+p}{p}$로 증가합니다. “어떤 기저를 몇 개 쓸 것인가”는 모델 밖의 선택입니다.

📉 3. 일반화 성능에 대한 논의 부재

학습 데이터에 대한 오차 최소화만 다루므로 과적합에 대한 논의가 없습니다. SVM의 마진 최대화 같은 정규화 장치가 모델에 어떻게 들어갈 수 있을지가 자연스러운 후속 질문입니다. 가능한 방향은 다음과 같습니다.

방향 방법
함수 수 벌점 사용 함수 지시 변수 $u_k\in{0,1}$에 비용을 더해 희소한 경계 유도
마진 항 경계 위반 허용 폭을 변수로 두고 목적에 포함
계수 정규화 $\ell_1$ 노름의 계수 벌점(선형 유지 가능)

🔭 4. 현대적 관점

현대적 관점에서는 “해석 가능한 최적 분류기”를 MILP로 푸는 연구(optimal classification trees, hyper-box 분류, 희소 선형 분류 등)의 초기 형태로 읽을 수 있습니다. 상용 솔버의 성능이 크게 향상된 지금, 당시 2차원에서만 시연된 동시 결정 모델을 더 큰 데이터에 다시 적용해 보는 것도 의미가 있습니다.

📚 5. 참고 문헌과 비고

  1. 김광수, “혼합정수 선형계획법 기반의 비선형ㆍ비볼록 패턴 분류 기법”, 한국경영과학회 2005년 추계학술대회 논문집, pp. 459–462. DBpia
  2. H. S. Ryoo, K. Kim, “Separation of Data Via Concurrently Determined Discriminant Functions”, Theory and Applications of Models of Computation (TAMC 2007), LNCS 4484, Springer, pp. 533–541. DOI
  3. O. L. Mangasarian, “Linear and Nonlinear Separation of Patterns by Linear Programming”, Operations Research, 1965.

비고 : 본 글 작성 시점에 두 원문의 본문(제약식, 실험 수치)에는 접근하지 못했고, DBpia와 Springer의 서지 정보·초록만 확인했습니다. 따라서 모델 수식은 두 초록과 기존 정리 내용에 기반한 재구성이며, 원문의 정확한 정식화와 다를 수 있습니다.

💡 Key Takeaway 이 모델의 가치는 “MILP로 비볼록 경계를 한 번에, 해석 가능하게 찾는다”는 틀에 있고, 한계는 “규모와 일반화”에 있습니다. 둘 다 이후 최적 분류기 연구가 그대로 물려받은 쟁점입니다.