The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

기술적 요약: 패턴의 포함 깊이(Inclusion Depth) 계산

문제 정의
본 노트는 패턴 식별 문제에 내재된 "마인드 체인지 복잡도(mind-change complexity)"를 포착하기 위해 설계된 지표인 패턴 언어의 **포함 깊이(inclusion depth)**를 계산하는 문제를 다룬다. 핵심적인 질문은 주어진 패턴에 대해 이 깊이가 계산 가능한지, 그리고 특히 패턴의 구조적 특성에 기반한 단순한 조합론적 특징(combinatorial characterization)을 갖는지 여부이다.

형식적으로, $X$를 변수들의 집합이라 하고, $\Sigma$를 최소 두 개의 기호를 가진 유한 알파벳이라 하자. 패턴 $p$는 $X \cup \Sigma$ 위의 유한하고 비어 있지 않은 시퀀스이다. 언어 $L_\Sigma(p)$는 $p$에 있는 각 변수를 $\Sigma^+$ 내의 비어 있지 않은 문자열로 치환하여 생성되는 모든 그라운드 문자열(ground strings)의 집합이다.

포함 깊이 $ID_\Sigma(p)$는 범용 패턴 $L_\Sigma(x_1)$에서 $L_\Sigma(p)$로 이어지는 가장 긴 엄격한 포함 체인(strict inclusion chain)의 길이를 의미한다. 예를 들어, $\Sigma=\{0,1\}$일 때 $p = 0x_11$이라면, 포함 깊이는 $L_\Sigma(x_1)$에서 $L_\Sigma(0x_11)$까지의 네 단계의 엄격한 포함을 나타내는 체인의 길이인 4이다.

방법론 및 가설
본 논문은 포함 깊이의 계산 가능성에 접근하기 위해 직접적인 조합론적 공식을 제안한다. 저자는 포함 깊이가 패턴의 길이($|p|$)와 포함된 서로 다른 변수의 개수($\#var(p)$)에 의해서만 결정된다고 가정한다.

주요 가설인 **질문 2(Question 2)**는 $|\Sigma| \geq 2$인 임의의 알파벳 $\Sigma$에 대하여 다음과 같이 제안한다:
$$ID_\Sigma(p) = 2|p| - \#var(p) - 1$$

만약 이 방정식이 성립한다면, 이는 포함 깊이를 계산하기 위한 선형 시간 알고리즘의 존재를 의미하며, 이를 통해 질문 1(계산 가능한 알고리즘의 존재 여부)에 대해 긍정적인 답변을 제공하게 된다.

이 공식을 검증하기 위해, 본 논문은 패턴 포함에 대한 필요 조건을 설정하는 **가설 1(Conjecture 1)**을 도입한다. 이는 만약 패턴 $p$의 언어가 패턴 $q$의 언어의 엄격한 부분집합($L(p) \subset L(q)$)이라면, 다음의 부등식이 반드시 성립해야 함을 명시한다:
$$2|p| - \#var(p) > 2|q| - \#var(q)$$

저자는 특정 알파벳 $\Sigma$에 대한 의존성을 알파벳이 정확히 두 개의 기호를 포함하는 경우로 줄일 수 있다고 언급하는데, 이는 포함 관계가 알파벳의 부분집합 간에도 보존되기 때문이다.

결과 및 부분적 해법
본 논문은 가설들에 대한 공식적인 증명을 제공하는 대신, 경험적 근거와 이론적 맥락을 제시한다:

• 결정 불가능성 맥락: 패턴 포함 여부를 결정하는 일반적인 문제가 결정 불가능(undecidable)하다는 점은 인정된다. 그러나 저자는 포함 깊이를 계산하는 것이 임의의 두 패턴 사이의 일반적인 포함 문제를 해결할 필요는 없을 수도 있다고 주장한다.
• 경험적 검증: 저자의 프로그램에 의한 전수 계산 결과, 길이가 7 이하인 모든 패턴에 대해 가설 1의 부등식이 성립함을 확인하였다.
• 계산적 한계: 길이가 7보다 긴 패턴에 대한 검증은 계산적으로 실행 불가능한 것으로 간주되었다. 따라서 가설 1에 대한 반례가 존재한다면, 그 반례는 반드시 길이가 7보다 큰 패턴을 포함해야 한다.

의의 및 주장
본 연구의 의의는 패턴 식별의 이론적 복잡도와 실질적인 계산 가능성 사이의 간극을 메우려는 시도에 있다.

• 마인드 체인지 복잡도: 포함 깊이는 초기 증거가 주어졌을 때 패턴을 식별하는 데 필요한 마인드 체인지 복잡도를 정량화하기 위한 것이다.
• 알고리즘적 함의: 제안된 조합론적 특징(방정식 1)이 참으로 증명된다면, 이는 포함 깊이를 계산하기 위한 선형 시간 알고리즘의 구축을 가능하게 할 것이다.
• 학습자 구성: 포함 가능성 문제에 대한 계산 가능성 질문에 대한 긍정적인 해결은, 패턴 식별 문제에 대한 마인드 체인지 상한(mind-change bounds)을 계산하고 **균일하게 마인드 체인지 최적화된 학습자(uniformly mind-change optimal learner)**를 구축하는 것을 용이하게 할 것이다.

본 논문은 이 문제를 열린 문제(open question)로 규정하며, 조합론적 특징을 증명하거나 더 긴 패턴에서 반례를 찾아내는 추가 연구를 제안하며 결론을 맺는다.