학습의 가장 단순한 형태: 암기식 학습
학습 구조 중 가장 단순한 것은 단순 암기, 즉 기계적 반복 학습(rote learning)입니다. 훈련 데이터로 주어진 사례들을 그대로 기억해 두었다가, 새로운 사례가 등장하면 기억된 훈련 사례들 가운데 가장 유사한 것을 찾아내는 방식입니다.
여기서 핵심 문제는 '유사하다'는 것을 어떻게 정의하느냐입니다. 이는 인스턴스 집합에서 추출한 "지식"을 표현하는 완전히 다른 방법으로, 규칙을 만들려 하지 않고 사례 자체를 저장합니다. 즉, 클래스가 이미 알려져 있는 기존 사례들과 클래스가 아직 알려지지 않은 새로운 사례를 연관 지어 판단하는 것이죠. 이러한 방식을 인스턴스 기반 학습(instance-based learning)이라고 부릅니다.
게으른 학습 vs 열성적인 학습
인스턴스 기반 학습에서 실질적인 모든 작업은 훈련 집합을 처리할 때가 아니라 새로운 인스턴스를 분류해야 하는 시점에 수행됩니다. 다른 접근 방식과의 차이는 바로 "학습"이 일어나는 시점에 있다는 점입니다.
인스턴스 기반 학습은 게으른(lazy) 학습으로, 가능한 한 실제 작업을 뒤로 미룹니다. 반면 다른 방법들은 데이터를 확인하는 즉시 일반화를 수행하는 열성적인(eager) 학습에 해당합니다.
인스턴스 기반 분류에서는 각각의 새로운 인스턴스를 거리 측도(distance metric)를 사용해 기존 인스턴스들과 비교하고, 가장 가까운 기존 인스턴스의 클래스를 새로운 인스턴스에 부여합니다. 이를 최근접 이웃 분류(nearest-neighbor classification) 방법이라고 합니다.
k-최근접 이웃(k-NN) 방법
때로는 하나가 아닌 여러 개의 최근접 이웃을 사용하기도 합니다. 가장 가까운 k개 이웃들의 다수결 클래스(클래스가 수치형 값이라면 거리 가중 평균)를 새로운 인스턴스에 할당하는 방식으로, 이를 k-최근접 이웃(k-nearest-neighbor) 방법이라고 합니다.
거리 측도와 속성 가중치
명목형(nominal) 속성이 존재할 때는 해당 속성의 여러 값들 사이의 "거리"를 정의해야 합니다. 또한 어떤 속성은 다른 속성보다 더 중요할 수 있으며, 이는 보통 거리 측도에 다양한 형태의 속성 가중치(attribute weighting)를 적용해 반영합니다. 따라서 훈련 집합으로부터 적절한 속성 가중치를 학습해 내는 것은 인스턴스 기반 학습의 핵심 과제 중 하나입니다.
명시적 구조의 부재와 결정 경계
인스턴스 기반 표현의 명백한 한계는 학습된 결과로 명시적인 구조를 만들어 내지 않는다는 점입니다. 다만 인스턴스들이 거리 측도와 결합하여 공간을 여러 영역으로 나누고, 이 영역들이 하나의 클래스를 다른 클래스와 구분하는 역할을 하므로, 이 역시 일종의 지식에 대한 표현이라고 볼 수 있습니다.
예를 들어 두 클래스에 대해 각각 하나의 인스턴스만 주어졌다면, 최근접 이웃 규칙은 두 인스턴스를 연결하는 선분의 수직 이등분선을 따라 인스턴스 공간을 나눕니다. 각 클래스마다 여러 개의 인스턴스가 주어진 경우에는, 한 클래스의 인스턴스와 다른 클래스의 인스턴스를 잇는 특정 선분들의 수직 이등분선들로 이루어진 선분 집합이 전체 공간을 분할하게 됩니다.