Chapter Content
음, 자, 여러분, 오늘은요, 문제 해결에 있어서 진짜 중요한 핵심 용어들 있잖아요. 문제, 과정, 답, 그리고 해결책, 요거에 대해서 한번 썰을 풀어볼까 해요. 그러니까, 문제가 뭐냐? 우리가 해결하려고 애쓰는 그 상황, 그게 바로 문제죠. 쉽게 말해서, 숙제 같은 거? 그리고 과정은, 음, 해결책을 찾는 방법, 외부적인 방법일 수도 있고, 아니면 그 찾은 해결책이 어떻게 작동하는지, 내부적인 방법일 수도 있어요. 답은, 당연히 문제가 해결됐다는 걸 확인해주는 최종적인 상태고요. 마지막으로 해결책은, 그 문제를 해결하는 내부 과정을 실제로 구현하는 물리적인 어떤 것, 이라고 할 수 있겠네요.
예를 들어서, 다리를 생각해 봅시다. 다리의 문제는 뭐예요? 차나 사람들이 안전하고 효율적으로 강이나 계곡, 도로를 건너도록 해주는 거죠. 외부 과정은, 시행착오를 거쳐서 최종적인 다리 구조를 찾아내는 과정이고요. 내부 과정은, 다리 부품들이 서로 연결되어서 다리가 제대로 작동하게 만드는 인과 관계라고 할 수 있겠어요. 답은? 당연히 차나 사람들이 강 건너편에 있는 걸 보는 거겠죠. 그리고 해결책은, 바로 그 다리 자체, 우리가 다리라고 부르는 그 최종적인 구조물이 되는 겁니다.
딥러닝 모델을 예로 들어볼까요? 얼굴 인식 문제가 있다고 칩시다. 외부 과정은, 좋은 모델을 만들기 위해서 학습하는 단계가 될 거고요. 내부 과정은, 모델이 수렴했을 때, 그 모델이 어떤 식으로든 계산을 수행하는 방식이 되겠죠. 답은, 인식된 얼굴에 대한 정확한 이름이고요. 해결책은, 배포된 모델, 이미 발견된 파라미터(가중치 및 편향) 세트를 가지고 실제로 제품에 적용된 모델이 되는 겁니다.
하나 더 해볼까요? 루빅스 큐브, 다들 아시죠? 루빅스 큐브의 문제는, 여섯 면을 모두 맞춰서 각 면이 단색으로 이루어지도록 하는 거예요. 외부 과정은, 시행착오, 아니면 체계적인 접근 방식을 사용해서 큐브를 풀 수 있는 일련의 단계를 찾는 거죠. 내부 과정은, 그 발견된 단계, 즉 "알고리즘"을 따라서 큐브를 푸는 과정에서 일어나는 일이고요. 답은, 각 면이 단색으로 맞춰진 최종적인 상태이고요. 해결책은, 다른 사람들이 큐브를 풀 수 있도록 발견된 일련의 단계, 아마 종이에 적힌 그런 것일 수도 있겠죠.
요약하자면, 문제는 우리가 해결해야 할 상황이고요. 외부 과정은 해결책을 찾는 방법(예: 연역 또는 시행착오)이고, 내부 과정은 찾아낸 해결책이 실제로 구현되는 방식(예: 단계별 또는 다른 방식)입니다. 답은 해결을 확인해주는 최종 상태이고, 해결책은 문제를 해결하는 데 사용되는 프로세스를 수행하기 위해 배포되는 물리적 객체(예: 종이에 적힌 규칙, 소프트웨어에 배포된 모델)입니다. 이제 문제 해결에 대해 이야기할 언어를 갖게 되었으니, 어려운 문제에 대한 확실한 직관을 개발해 봅시다.
그럼, 뭐가 문제를 "어렵게" 만드는 걸까요? 사람들은 보통 바로 해결책이 떠오르지 않는 문제를 "어렵다"고 하죠. 즉시 사용할 수 있는 해결책이 없는 곤경은 대개 어렵거나 난처한 상황으로 간주됩니다. 하지만, 컴퓨터 과학적으로 "어렵다"는 말은 좀 더 구체적인 의미를 가져요. 어떤 문제가 컴퓨터로 효율적으로 풀기 매우 어렵거나 사실상 불가능할 때, 그 문제를 컴퓨터 과학적으로 어려운 문제라고 합니다. 이런 문제는 계산하는 데 많은 자원, 즉 많은 시간과/또는 메모리를 필요로 합니다.
계산적으로 어려운 문제들은, 입력 크기가 커질수록 난이도가 빠르게 증가하는 경향이 있어요. 보통 지수적인 형태로 증가하는데, 문제 크기가 조금만 커져도 문제를 푸는 데 필요한 시간이 폭발적으로 늘어나는 거죠. 지수적 증가는 종이를 계속 접는 걸 생각하면 이해하기 쉬울 거예요. 종이를 접을 때마다 몇 겹씩 더해지는 게 아니라, 곱절로 늘어나잖아요. 예를 들어서, 종이를 42번 접으면 지구에서 달까지의 거리를 넘을 정도라고 하니까요.
컴퓨터 과학에서 종이 접기 같은 현상은, 알고리즘이 해결책을 찾기 위해 거쳐야 하는 가능한 경로의 폭발적인 증가를 의미합니다. 어려운 문제들은 처리해야 할 요소가 많다는 걸 기억하세요. 더 긴 다리는, 그것이 해결하는 과제와 관련된 추가적인 요소를 고려해야 하기 때문에 더 많은 부품을 가지고 있습니다. 얼굴 인식은, 얼굴을 얼굴답게 만드는 데 관여하는 요소의 수가 엄청나기 때문에 계산적으로 어렵습니다.
문제를 계산적으로 어렵게 만드는 핵심 개념은 바로 "가능성 공간"입니다. 가능성 공간은, 주어진 문제와 관련하여 존재할 수 있는 모든 가능한 조합, 배열 또는 상태의 집합입니다. 즉, 시스템이 가질 수 있는 모든 가능한 구성의 집합인 거죠. 체스판을 예로 들면, 가능성 공간은 모든 말을 배열할 수 있는 모든 방법이 되는 겁니다. 문제와 관련된 가능성 공간이 클수록, 그 문제를 풀려고 시도하는 알고리즘이 탐색해야 하는 공간도 더 커지겠죠. 바로 이 탐색해야 하는 공간의 증가가, 문제를 근본적으로 어렵게 만드는 핵심 요소입니다.
가능한 모든 구성의 우주 안에서 작업하는 것은 비현실적이기 때문에, 모델과 알고리즘은 가능성 공간에서 작동하지 않습니다. 대신 어려운 문제에 대한 축소된 가능한 특징 집합을 정의하고 해당 축소된 공간 내에서 작동하려고 시도해야 합니다. 이 축소된 공간을 특징 공간이라고 하며, 문제에 중요하다고 간주하는 특징으로 만들어집니다.
겨울 동안 손을 따뜻하게 유지하는 문제를 생각해 봅시다. 임의의 물체를 섞어서 손에 감싸는 대신, 고려할 가치가 있는 속성을 고려할 것입니다. 이러한 속성은 두께, 다락성, 흡수성 수준 및 강도와 같은 것일 수 있습니다. 이러한 특징을 플롯으로 만들면 4개의 축이 생깁니다. 우리 문제에 대한 해결책은 해당 4개 축의 범위로 깎아낸 공간 어딘가에 존재할 것입니다. 장갑이 제대로 작동하도록 재료를 올바르게 조합하면 적절한 두께, 다락성, 흡수성 수준 및 강도를 가질 수 있기 때문입니다. 각 특징은 특징 공간에 차원을 제공하고, 모든 특징의 조합은 솔루션이 상주하는 고차원 공간을 만듭니다. 문제가 "고차원적"이라는 말을 들으면 이것이 의미하는 바입니다. 즉, 특징 공간에 많은 차원이 포함되어 있고 솔루션이 해당 공간 어딘가에 있는 문제.
문제를 근본적으로 어렵게 만드는 것은 문제의 특징 공간 내에서 솔루션이 있는 위치를 찾는 데 관련된 어려움입니다. 어려운 문제에 대한 특징 공간은 광대한 영역으로, 구불구불한 경로와 장애물이 얽힌 패치워크로 구성됩니다. 어려운 문제에서는 솔루션을 찾을 수 있는 위치를 알려주는 명확한 표지판이 없습니다.
어려운 문제의 특징 공간을 탐색하기 어렵게 만들고 솔루션을 찾기 어렵게 만드는 데는 3가지 주요 어려움이 있습니다. 이는 1) 특징 공간 자체의 본질적인 복잡성, 2) 서로 다른 특징 간의 눈에 보이는 인과 관계 부족, 3) 만들 수 있는 모든 가능한 조합에 비해 실행 가능한 특징 조합(실용적인 솔루션)의 수가 적습니다.
특징 공간의 본질적인 복잡성은 특징 간의 상호 작용 및 종속성에서 발생합니다. 손을 따뜻하게 유지하는 문제에서 더 두꺼운 재료는 더 많은 단열을 제공하지만 손재주를 줄일 수도 있습니다. 흡수성이 높은 재료는 습기를 제거하는 데 좋지만 젖으면 추워질 수도 있습니다. 특징 공간의 복잡성은 반드시 특징 공간을 더 크게 만드는 것은 아니지만 솔루션으로 이어지는 경로를 찾기가 더 어렵습니다. 복잡한 특징 공간 안에서 잘못된 길로 빠지기 쉽습니다. 한 특징의 값을 높이면 한 측면에서 성능이 향상되지만 다른 측면에서는 성능이 저하될 수 있는 내재적 절충을 고려하십시오. 답을 찾아 복잡한 특징 공간을 이동하는 것은 다시 또 다시 베드로를 털어 바울에게 주는 것입니다.
일반적으로 특징 수가 증가함에 따라 해당 특징이 독립적일 가능성이 줄어듭니다. 이것이 고차원 공간이 진정으로 복잡한 시스템의 특징이며, 그에 관련된 어려운 문제인 이유입니다. 이것은 또한 복잡성이 단순히 많은 조각에 관한 것이 아니라 결정적으로 그 조각 간의 상호 작용에 관한 이유이기도 합니다.
문제 어려움의 두 번째 원인은 특징 공간에서 특징 간의 눈에 보이는 인과 관계가 손실되는 것입니다. 손을 따뜻하게 유지하는 문제로 돌아갑니다. 여기서 우리는 두께, 다락성, 흡수성 수준 및 강도가 어떻게 함께 작동하여 문제를 해결하는지 쉽게 상상할 수 있습니다. 우리는 연역을 사용하여 특징 공간을 이동하고 작동하는 구성에 도달할 수 있습니다. 우리는 먼저 추위를 자연적으로 차단하는 일부 동물 가죽을 가져와서 동물 힘줄 조각에 연결하여 재료를 묶고 원하는 모양을 유지할 수 있습니다. 우리는 동물 섬유로 채워진 가죽 2층이 동물 가죽 단독보다 더 나은 단열재 역할을 할 것이라고 쉽게 추론할 수 있습니다.
손을 따뜻하게 유지하는 문제는 특징 공간에 내재된 복잡성이 있음에도 불구하고 비교적 간단한 문제입니다. 이는 특징의 수가 적고(저차원), 특징 간의 절충이 최소화되면 인간이 단순한 연역을 통해 솔루션을 찾을 수 있음을 보여줍니다. 첫 번째 솔루션이 가장 좋은 솔루션은 아니지만 작동합니다. 솔루션 조각 간의 인과 관계가 명확하기 때문에 연역이 여기서 작동합니다.
하지만 이제 더 어려운 문제를 고려해 봅시다. 눈사람을 만드는 동안 손을 따뜻하게 유지하는 문제에 대한 해결책을 찾아야 한다고 상상해 보세요. 이제 문제에 대한 제약 조건이 더 많습니다. 손을 따뜻하게 유지해야 할 뿐만 아니라 건조하게 유지하고 눈을 다룰 수 있을 만큼 충분한 손재주를 가져야 합니다. 문제에 대한 이러한 추가 제약 조건은 고려할 가치가 있는 특징의 수를 늘릴 수도 있고 늘리지 않을 수도 있지만 추가 절충이 발생할 가능성이 높습니다. 이로 인해 특징 간의 인과 관계 구조가 더 이상 명확하지 않기 때문에 솔루션을 추론하는 능력이 저하되기 시작합니다.
특징 공간의 본질적인 복잡성과 눈에 보이는 인과 관계의 손실 사이에는 밀접한 관계가 있습니다. 특징이 상호 작용을 통해 서로 "대화"할수록 더 많은 절충이 발생하여 솔루션을 찾기가 점점 더 어려워집니다. 따뜻하게 유지하고 손재주가 좋은 재료를 선택하면 너무 쉽게 젖는다는 것을 알 수 있습니다. 방수 재료를 찾는 순간 손재주를 잃습니다. 더 많은 제약 조건은 실행 가능한 솔루션을 찾는 길을 어렵게 만드는 모순, 딜레마, 역설 및 수렁을 악화시킵니다.
어려움의 마지막 원인은 솔루션 공간이라는 또 다른 공간과 관련이 있습니다. 솔루션 공간은 문제의 기준 또는 제약 조건을 충족하는 가능한 구성의 하위 집합인 특징 공간(자체가 가능성 공간 내에 있음) 내에 있습니다. 더 간단히 말해서 솔루션 공간은 문제에 대한 실행 가능한 솔루션을 생성하는 가능한 모든 구성의 공간입니다.
큰 솔루션 공간은 문제를 해결하는 가능한 솔루션이 더 많다는 것을 의미하고, 작은 솔루션 공간은 솔루션이 더 적다는 것을 의미합니다. 가능성 공간에 비해 큰 솔루션 공간을 가진 문제는 솔루션을 실행하기 전에 추상적으로 기동할 공간이 적기 때문에 검색하는 데 시간이 덜 걸립니다. 손을 따뜻하게 유지하는 것과 관련된 문제는 문제를 해결할 수 있는 재료 조합이 많기 때문에 솔루션 공간이 큽니다. 우리 조상들이 일찍이 괜찮은 벙어리장갑을 우연히 발견했을 가능성이 높다는 점을 고려하십시오.
이것을 루빅스 큐브와 같은 것과 비교하십시오. 이 특징 공간 내부의 점은 26개의 "큐비"의 고유한 구성이 될 것이며, 각 큐비는 위치 및 방향과 관련된 값 세트를 가지고 있습니다. 이러한 값의 혼합은 손을 따뜻하게 유지하는 문제에서 두께, 다락성, 흡수성 수준 및 강도의 혼합에 대한 루빅스 큐브 버전입니다. 루빅스 큐브의 솔루션 공간은 동일한 최종 답을 생성할 수 있는 가능한 모든 알고리즘 집합입니다.
루빅스 큐브에 대한 솔루션을 찾는 데 오랜 시간이 걸리는 이유는 특징 공간의 복잡성 때문입니다. 내가 솔루션을 찾으라는 말을 할 때 이것이 큐브처럼 이미 발견된 알고리즘을 따르는 것을 의미하지는 않습니다. 저는 처음으로 단계 집합을 발견하는 것에 대해 이야기하고 있습니다. 루빅스 큐브는 특징에 절충이 있기 때문에 특징 공간에 내재된 복잡성이 있습니다. 큐비를 주어진 위치에 놓으면 이전에 배치된 큐비 하나 이상을 쉽게 망칠 수 있습니다.
그러나 루빅스 큐브는 근본적으로 어려운 문제가 아닙니다. 루빅스 큐브는 여전히 합리적인 시간 내에 해결할 수 있는 어려운 징후를 보이기 시작하는 문제로 생각하는 것이 가장 좋습니다. 체스는 훨씬 더 크고 복잡한 가능성 공간을 가지고 있습니다. 체스는 우리를 진정으로 어려운 문제에 더 가깝게 만듭니다. 물론 루빅스 큐브도 체스도 자연적으로 어려운 문제는 아닙니다. 서론에서 언급했듯이 자연적으로 어려운 문제는 우리가 만든 게임이 아니라 자연 환경 내에서 제시되는 문제입니다. 자연적으로 어려운 문제는 컴퓨터 과학의 복잡성 클래스에 깔끔하게 들어맞지 않습니다. 자연적으로 어려운 문제의 가능성 공간은 효과적으로 무한한 크기와 복잡성을 가집니다. 그러나 루빅스 큐브와 체스는 모두 더 간단한 문제(손을 따뜻하게 유지하는 문제와 같은)에서 진정한 어려움에 접근하는 문제로의 전환을 보는 좋은 방법입니다.
요약하자면 문제를 정의하는 데 사용하는 추상 공간의 3가지 주요 측면은 어려움으로 이어집니다. 1) 공간 자체의 복잡성(상호 의존적인 특징), 2) 공간 내부의 특징 간의 인과 관계 저하, 3) 전체 공간에 비해 솔루션 공간의 작은 크기입니다. 근본적으로 어려운 문제는 이러한 3가지 측면이 높은 정도를 가지고 있습니다.
어려운 문제에서 탐색할 공간이 얼마나 많은지 살펴보면 답을 찾을 수 없을 것 같습니다. 루빅스 큐브는 43경이 넘는 가능한 구성을 가지고 있습니다. 체스는 훨씬 더 많습니다. 그러나 이들은 여전히 실제 상황에 비해 차원이 축소된 게임일 뿐입니다. 인간의 발명에 의해 제한되지 않는 자연 환경에서 가능한 구성의 수는 거의 이해할 수 없는 수준의 복잡성을 가지고 있습니다. 따라서 이 공간의 문제는 게임에서 볼 수 있는 것과는 다릅니다.
그러나 인간은 항상 자연적으로 어려운 문제에 대한 솔루션을 찾습니다. 이러한 거대한 가능성 공간은 어떻게 억제되고 다루기 쉽게 만들어질 수 있을까요?
문제가 어려울수록 검색은 더 부드러워집니다.
루빅스 큐브에서 발생하는 조합 폭발로 인해 가능한 모든 구성이 시도되는(정확한 구성이 발견될 때까지) 완전 검색 방법은 가장 빠른 컴퓨터를 사용하더라도 불가능하다는 점에 유의하는 것이 중요합니다. 솔루션을 찾기 위해 가능한 모든 구성을 계산하는 데 수십억 년이 걸릴 것입니다.
이것이 루빅스 큐브를 푸는 컴퓨터가 가능성 공간을 보다 효과적으로 검색하기 위해 휴리스틱과 패턴 인식을 사용해야 하는 이유입니다. 휴리스틱은 사람들이나 기계가 명시적인 분석 없이도 어려운 문제를 해결할 수 있도록 하는 일반적인 경험 법칙 또는 지름길입니다. 체스 그랜드마스터가 일반적인 오프닝과 같은 보드의 인식 가능한 패턴을 사용하여 최고의 수준에서 플레이하는 방법을 고려하십시오. 이것은 체스 조각의 명시적인 집계가 아닙니다. 이것은 플레이어를 좋은 움직임으로 안내하는 패턴의 빠른 인식입니다.
다시 말하지만 루빅스 큐브는 진정으로 어려운 문제가 아니지만 문제의 어려움이 증가함에 따라 문제 해결 접근 방식이 더 부드러워져야 함을 보여줍니다. 여기서 더 부드러움은 문제에 대한 부분을 자세히 분석하기보다는 휴리스틱 및 패턴 인식과 같은 것에 의존하는 것을 의미합니다. 문제가 더 어려울수록 가능성 공간이 더 크고 복잡해지며 해당 공간을 검색해야 합니다. 즉 문제가 더 어려울수록 검색 방법에 대해 분석적일 수 없습니다. 손을 따뜻하게 유지하는 문제에서 검색은 약간의 시행착오와 함께 연역으로 쉽게 수행되었습니다. 눈사람 문제는 인과 관계가 저하되어 연역이 덜 유용해졌기 때문에 더 많은 시행착오가 필요했습니다. 루빅스 큐브는 새로운 솔루션을 찾기 위해 훨씬 더 많은 시행착오가 필요합니다. 체계적으로 수행되더라도 휴리스틱을 사용해야 합니다. 다시 말하지만 솔루션을 찾을 때까지 가능한 모든 구성을 시도하는 무차별 대입 접근 방식은 실현 가능하지 않습니다.
자연적으로 어려운 문제, 즉 실생활에서 발견되는 문제는 가장 부드러운 접근 방식으로만 해결할 수 있다는 것이 합리적입니다. 그리고 물론 이것이 우리가 보는 것입니다. 인간은 자세한 분석이 아닌 휴리스틱과 패턴 인식을 사용하여 모든 어려운 문제를 해결하도록 진화했습니다. 인간이 사용하는 감정적 단서와 직관은 휴리스틱의 진화된 버전입니다. 따라서 어려운 문제의 원래 정의에 따라 인간이 만든 컴퓨터만이 계산하는 것은 아닙니다. 자연은 계산합니다. 그리고 자연은 모든 어려운 문제를 해결하는 데 필요한 것을 보여줍니다. 우리는 시스템 외부, 신중한 분석 영역 외부로 나가서 시행착오, 휴리스틱 및 패턴 인식을 사용하여 광대한 가능성 공간을 탐색해야 합니다.
이것이 딥러닝이 여기 있는 이유입니다. 분석적 접근 방식과 규칙 기반 컴퓨팅은 진정으로 어려운 문제를 해결할 수 없습니다. 딥러닝은 분석이나 규칙에 관한 것이 아니라 시행착오, 휴리스틱 및 패턴 인식의 계산 버전을 포용합니다. 딥러닝은 잠재적으로 새로운 솔루션을 찾기 위해 루빅스 큐브 문제에 적용할 수 있습니다. 이러한 응용 프로그램이 일반적인 문제 해결과 관련된 귀중한 통찰력, 전략 또는 혁신을 밝힐 수 있다는 희망으로 동기 부여되어 수행되었습니다. 딥러닝은 인간이 하는 것처럼 부드럽고 외부적으로 가능성 공간을 검색합니다.
그러나 딥러닝에서 사용하는 검색 프로세스가 개념적으로 인간이 사용하는 검색 프로세스와 유사하지만 발견된 솔루션에 대해서는 동일하다고 말할 수 없습니다. 인간과 전통적인 컴퓨팅은 다른 사람들이 따를 수 있는 이해 가능한 일련의 지침(즉, 큐브 알고리즘)으로 제시할 수 있는 솔루션을 찾습니다. 그러나 딥러닝은 매우 다른 것을 생성합니다. 눈에 보이는 일련의 단계 대신 딥러닝 솔루션은 이러한 방식으로 볼 수 없습니다. 딥러닝 솔루션은 인과적으로 불투명하고 대체로 해석할 수 없습니다. 즉 배포된 솔루션이 큐브를 풀 때 딥러닝이 무엇을 하고 있는지 모릅니다. 여기서 분명한 질문은 2개의 다른 시스템(인간과 AI) 간의 동일한 전체 접근 방식이 왜 그렇게 다른 솔루션을 생성할까요?