Diffusion Map은 두 관측에서 출발한 랜덤 워크(random walk)가 비슷한 이웃에 도달하면 두 관측을 가깝게 놓습니다. 가까운 점 사이의 연결을 반복해서 따라가며 전체 구조를 만드는 방법입니다. 이번 강의의 전이행렬은 데이터를 탐색하는 규칙입니다. 세포나 대화가 실제로 이동한 기록과는 구분해야 합니다.

선수 지식: PCA 고유벡터, 거리, 조건부확률, 4강의 kNN 그래프. 90분 구성: 직관과 장난감 예제 15분, 행렬 구성 20분, 스펙트럴 좌표 20분, Python 25분, 해석 10분. 학습 목표는 유효한 전이행렬과 정상분포를 계산하고, diffusion step을 실제 시간과 구분하는 것입니다.

공통 실습 환경과 데이터 계약을 먼저 읽습니다. lesson05.py는 전체 실습 묶음 안에서 실행합니다.

1. 휘어진 팔을 따라 걷기

2차원 평면에 U자 모양으로 점을 놓아 봅시다. 양 끝은 직선으로 보면 가깝지만, 주변 점만 따라가면 U의 바닥을 돌아야 합니다. 각 끝에 놓인 두 사람이 한 걸음 후 도달할 수 있는 이웃은 다릅니다. 여러 걸음 후에는 두 사람 모두 U 전체를 돌아다닐 수 있습니다.

먼저 A–B–C라는 세 점의 경로만 생각합니다. 모든 간선의 가중치는 1입니다. A에서는 반드시 B로 가고, B에서는 절반의 확률로 A 또는 C로 갑니다.

$$P_0=\begin{pmatrix}0&1&0\\1/2&0&1/2\\0&1&0\end{pmatrix}.$$

오래 관찰하면 B를 더 자주 방문합니다. 간선이 두 개이기 때문입니다. 정상분포(stationary distribution)는 $(1/4,1/2,1/4)$이며, 세 점에 균일하지 않습니다. 이 그래프는 홀수와 짝수 걸음에서 방문 가능한 쪽이 번갈아 바뀌는 주기성도 갖습니다. 절반의 확률로 제자리에 머무르는 lazy walk를 사용하면 이 문제를 피할 수 있습니다.

2. 유사도를 전이확률로 바꾸기

스케일링과 PCA를 거친 관측을 $r_i$라 합시다. 두 점 중 하나라도 다른 점의 $k$개 최근접 이웃이면 연결합니다. 연결된 곳에서

$$W_{ij}=\exp(-\|r_i-r_j\|^2/\sigma^2),\qquad W_{ii}=0$$

로 정의합니다. $W$가 클수록 더 가깝습니다. 구현에서는 방향별 kNN 가중치의 최댓값을 취해 $W$를 대칭화합니다. 그다음 degree와 대각행렬을 만듭니다.

$$d_i=\sum_j W_{ij},\quad D=\operatorname{diag}(d_i),\quad P_0=D^{-1}W,\quad P=\tfrac12(I+P_0).$$

$P$의 각 행의 합은 1입니다. 연결된 그래프에서 유일한 정상분포는 $\pi_i=d_i/\sum_jd_j$입니다. $\pi_iP_{ij}=\pi_jP_{ji}$라는 상세균형(detailed balance)도 성립합니다. 우리가 만든 랜덤 워크가 가역적이라는 말이며, 실제 세포 분화가 되돌아간다는 뜻은 아닙니다.

연결 성분이 여러 개면 성분 사이를 이동할 수 없습니다. 고유값 1에 대응하는 고유벡터도 여러 개이고, 성분별 정상분포를 섞는 비율은 유일하지 않습니다. 고립된 점에서는 degree가 0이라 나눗셈 자체가 불가능합니다. 좌표를 그리기 전에 연결 성분부터 확인해야 하는 이유입니다.

3. Laplacian에서 느린 좌표까지

그래프 Laplacian은 $L=D-W$입니다. 각 점에 숫자 $f_i$를 하나씩 붙이면

$$f^TLf=\frac12\sum_{ij}W_{ij}(f_i-f_j)^2$$

가 됩니다. 강하게 연결된 점들의 숫자가 서로 비슷할수록 값이 작습니다. 작은 고유값에 대응하는 좌표가 그래프를 따라 부드럽게 변한다는 직관을 여기서 얻을 수 있습니다.

대칭 정규화 Laplacian은

$$L_{\rm sym}=I-D^{-1/2}WD^{-1/2}$$

입니다. $L$과 같은 행렬이 아니며, degree 정규화는 풀고 있는 문제를 바꿉니다. 실습에서는 lazy walk와 대응하는 대칭행렬 $S=I-L_{\rm sym}/2$를 풉니다. $Su_\ell=\lambda_\ell u_\ell$이면

$$\psi_\ell(i)=\frac{u_\ell(i)}{\sqrt{\pi_i}}$$

가 $P$의 오른쪽 고유벡터입니다. 이 스케일을 사용하면 정상분포 가중 내적에서 정규직교합니다.

상수 좌표인 $\lambda_0=1$을 제외하고 다음 좌표를 사용합니다.

$$\Phi_t(i)=\big(\lambda_1^t\psi_1(i),\ldots,\lambda_m^t\psi_m(i)\big).$$

작은 고유값에 해당하는 변화는 빨리 줄어듭니다. $t$를 늘리면 천천히 섞이는 큰 구조가 강조되지만, 유용한 세부 구조도 사라질 수 있습니다. 이 스펙트럴 구성과 여러 스케일의 해석은 Diffusion Maps 원논문에서 전개됩니다.

좌표가 근사하는 거리는 다음과 같습니다.

$$D_t^2(i,j)=\sum_k\frac{(P^t_{ik}-P^t_{jk})^2}{\pi_k}.$$

출발점이 달라도 도착 확률이 비슷하면 거리가 작습니다. 연결된 가역 랜덤 워크에서 모든 비상수 고유벡터를 쓰면 이 값과 diffusion 좌표의 유클리드 거리 제곱이 같습니다. 두 축만 쓰는 것은 근사입니다. $P^t$의 두 행에 평범한 유클리드 거리를 적용하면 분모의 정상분포 가중치를 놓칩니다.

4. Python: 그림보다 먼저 확률을 검증하기

전체 코드는 sparse affinity를 만들고 eigsh로 $S$를 풉니다. 아래 코드는 압축을 푼 실습 디렉터리에서 실행하며, 다운로드 스크립트의 핵심 계산과 같습니다.

from common import make_dataset, prepare_embedding
from lesson05 import affinity_graph, diffusion_coordinates
import numpy as np

data = make_dataset()
_, Z, _, _ = prepare_embedding(data, n_components=6)
W = affinity_graph(Z, k=48)
Dmap, values, P, pi, components = diffusion_coordinates(W, time=4)
print(components, values)
print(np.max(np.abs(np.asarray(P.sum(axis=1)).ravel() - 1)))
print(np.max(np.abs(np.asarray(pi @ P).ravel() - pi)))

python lesson05.py --output outputs로 실행합니다. JSON의 행 합 오차와 정상분포 오차는 부동소수점 정밀도 수준으로 작아야 합니다. PNG에서는 PCA 두 축과 diffusion 좌표를 비교합니다. 시간 색상은 계산 후 해석을 위해 붙이며 그래프를 만드는 데 쓰지 않습니다.

공통 합성 데이터의 PCA와 diffusion 좌표

스케일러와 PCA는 학습 세션으로만 적합하지만, 그래프에는 평가 세션의 관측도 들어갑니다. 따라서 이 결과는 관측 전체를 함께 분석하는 transductive 탐색입니다. 새로운 세션의 미래를 예측한 결과가 아닙니다. 새 점을 처리하려면 별도의 확장 규칙과 평가 설계가 필요합니다.

5. 세포와 캐릭터 대화에 적용하기

세포에서는 적절히 전처리한 발현량의 이웃이 분화 연속체를 드러낼 수 있습니다. 반대로 라이브러리 크기, 배치 효과, 샘플링 밀도가 이웃을 지배할 수도 있습니다. Diffusion Map 자체가 이런 문제를 자동 제거하지는 않습니다. 밀도 정규화 커널은 별도로 선택해야 할 모델링 방법입니다.

캐릭터 채팅에서는 동일한 인코더와 같은 기준의 대화 구간을 사용합니다. 비슷한 관계 긴장도나 이야기 단계가 이웃을 형성할 수 있습니다. 하지만 그래프의 한 걸음은 다른 사용자의 세션으로 이동할 수 있습니다. 실제 다음 턴 전이는 8강에서 세션 내부의 순서로 따로 추정합니다.

공통 데이터는 $k=24$에서 연결 성분이 4개, $k=48$에서 1개입니다. 실습은 명시적으로 선택한 48을 쓰고, 그래프가 끊겨 있으면 전체 diffusion map 계산을 중단합니다. 몰래 연결선을 추가하지 않습니다. 이 민감도는 조사할 결과이지 큰 $k$가 생물학적으로 옳다는 증거가 아닙니다.

$k$, bandwidth, diffusion time을 함께 바꿔 보세요. 이웃이 너무 적으면 연속체가 끊기고, 너무 많으면 지름길이 생깁니다. 멋진 branch 그림 하나보다는 여러 설정에서 유지되는 구조와 독립적인 도메인 증거가 중요합니다.

6. 연습문제와 해설

  1. A에서 시작한 lazy walk의 한 걸음은? A에 1/2, B에 1/2입니다. 정상분포는 여전히 $(1/4,1/2,1/4)$입니다. 제자리에 머무르는 연산은 정상분포를 바꾸지 않습니다.
  2. $t=1,4,16$을 비교하면 무엇이 달라지나요? 각 축에 고유값의 해당 거듭제곱이 곱해집니다. 빠른 모드는 먼저 줄어들며, 실제 시간 관측이 새로 추가되는 것은 아닙니다.
  3. 세포 발달의 방향을 반대로 정하면 이 그래프도 달라지나요? 점과 거리가 같으면 달라지지 않습니다. 대칭 유사도에는 발달 방향이 없습니다. 초기 상태, 순서 관측, 방향성 측정 같은 추가 정보가 필요합니다.

다음 강의에서는 같은 이웃 그래프를 재사용해 어떤 상태 집단을 구분할지 살펴봅니다.