NP-hard 란? Linear Classification의 NP-hard 문제

머신러닝 이론 공부 중, Linear Classification의 문제점으로 NP-hard 문제가 나왔는데 

뭔지 짚고 넘어가고자 포스팅한다.

---

사전 지식

결정성(deterministic) 알고리즘 VS 비결정성 알고리즘

1) 결정성 알고리즘

: input에 따라 결과가 정해져있는 알고리즘. 즉, A -> B로 결정되어 있는 알고리즘이다.

2) 비결정성 알고리즘

: 답이 유일하게 결정되지 않는 알고리즘이다. A -> B,C,D 인지 정해지지 않음.

 

NP의 반대 개념, P (polynomial)

NP전에 우선 P를 알아야 한다.

P는 결정론적 (deterministic) 알고리즘을 사용해서 다항 시간 내에 답을 구할 수 있는 문제의 집합이다.

즉, P는 yes/no 로 답할 수 있는 문제이다.

​​

# NP (Nondeterministic polynomial)​

NP는 비결정론적 알고리즘을 사용해서 다항 시간 내에 답을 구할 수 있는 문제의 집합이다.

 

다시 말하면, yes 또는 no로 답할 수 있는 문제에서 yes라고 답을 주었을 때,

그 답이 정말 yes가 맞는지를 polynomial time안에 확인할 수 있으면 그 문제를 NP문제라고 한다.

간단하게 설명하자면 polynomial time내에 해결할 수 있는 방법이 있지는 않지만

만약에 solution을 찾게 되면 polynomial time내에 해결이 가능하다라고 이해하면 된다.

​

Continue...

NP문제 중에서도 답을 polynomial time 안에 찾을 수 있으면 그 문제를 P문제 라고 한다. 그래서 P는 NP의 부분집합이 된다. 오늘날의 컴퓨터는 P(Polynomial)에 관한 문제는 일정 term을 주면 해결가능 할 것이다. 하지만 NP는 그와 반대로 엄청난 실행 사이클을 잡아 먹을 것이다.

​

NP는 NP-complete와 NP-hard로 나뉜다.

​

---

NP-complete 문제

(가볍게 읽어보기)

NP-complete 문제는 NP-hard이며 NP 부류에 속하는 문제로서 만약 이 문제를 해결하는 다차 함수 시간 결정성 알고리즘이 존재한다면 NP에 속한 각 문제를 해결하는 다차 함수 시간 결정성 알고리즘이 존재한다.

현재 NP-complete 문제를 위한 모든 알려진 알고리즘들은 문제의 크기에서 지수적인 (exponential) 시간을 요구한다. NP-complete에 대해서는 완전한 진짜 정답을 찾기 보다는 훨씬 적은 양의 계산을 통해서 정답에 가까운 값을 찾는데 만족한다. 어떤 더 빠른 알고리즘이 있는지는 모른다. 그러므로 어떤 명백하지 않은 (non-trivial) 문제 크기의 NP-complete 를 해결하기 위해서, 다음과 같은 접근 방법중의 하나가 사용된다.

​

1) 근사 (Approximation) : 어떤 알려져 있는 적절한 범위내에 있는 차선의 (suboptimal) 해결책을 빠르게 찾는 알고리즘. 모든 NP-complete 문제가 good approximation algorithms 을 가진 것은 아니며, good approximation algorithm 을 발견한 문제도 문제 그 자체를 해결하기에 충분하지는 않다.

2) 확률 (Probabilistic) : 문제의 instance 에 대한 확률 분포 (이상적으로는 "hard" 입력에 대해 낮은 확률을 할당하는) 에 대해 훌륭한 평균 runtime behavior 를 낳는다고 입증된 알고리즘

3) Special cases: 문제의 instance 가 어떤 특별한 경우에 속한다면 빠르다는 것이 입증된 알고리즘

4) 휴리스틱 (Heuristic) : 많은 경우에 "reasonably well" 작동하지만, 항상 빠르다는 증명은 없는 알고리즘

​

NP-complete의 예로 해밀턴 경로 문제가 있다. 모든 점을 명확하게 한번씩 지나가는 경로가 존재하는가에 대한 문제이다. 다른 예로 해킹이 있다. 해킹은 모든 비밀번호를 대입해보는 방법이므로 brutal force말고는 적절한 알고리즘이 없으므로 NP-complete라고 한다. 또 다른 예로 팩토리얼이 좋은 예이다.

​

NP-hard 문제

다항 시간 내에 풀 수 없는 문제를 말한다. 다항 방정식 대신에 지수 방정식으로 풀 수 있는 문제를 말한다.

즉 결정석 다항식으로 구성할 수 없다는 것이다. NP-hard라고 해서 다항식이 아니라는 것은 아니다. 다만 다항식으로 표현될 수 있을 지의 여부가 아직 알려지지 않았다라는 것이다.

즉, NP-Hard란 TSP문제와 같이 모든 경우의 수를 일일히 확인해보는 방법 외에는 다항식 처럼 답을 풀이 할 수 없는 문제들을 말한다. NP-hard의 예로 외판원 문제가 있다.

---

그래서, Linear Classification이 왜 NP-hard 문제인데?

선형 분류(Linear Classification) 모델은 모든 데이터를 완전히 O/X로 분류하는 솔루션을 단번에 찾기는 어려움. (== NP-hard)

그래서 Ein을 최대한 작게 만드는 게 최고 솔루션.

→ 그래서 PLA 또는 Pocket 알고리즘과 같은 알고리즘을 통해 Ein을 가장 작게 만드는 가중치 w를 찾는다.

(하나하나 확인해봐야 한다)