인접성 성분 분석

다음에 대한 시리즈 일부
머신러닝 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 탐지 데이터 클리닝 자동ML 연결 규칙 강화학습 구조 예측 피쳐 엔지니어링 피처러닝 온라인 학습 반감독학습 무감독 학습 순위 매기기 문법 유도
감독 학습 (계속 • 회귀) 의사결정 나무 앙상블 바깅 부스팅 랜덤 포리스트 k-NN 선형 회귀 분석 순진한 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) SVM(지원 벡터 머신)
클러스터링 버치 치료하다 계층적 k-16 기대-최대화(EM) 디스캔 광학 평균 이동
차원성 감소 인자분석 CCA ICA LDA NMF PCA PGD t-SNE
구조 예측 그래픽 모델 베이즈 그물 조건부 랜덤 필드 히든 마르코프
이상 탐지 k-NN 국부 특이치 인자
인공신경망 오토인코더 인지 컴퓨팅 심오한 학문 딥드림 멀티레이어 퍼셉트론 RNN LSTM GRU ESN 제한 볼츠만 기계 간 somerset. 콘볼루션 신경망 유넷 변압기 비전 스파이킹 신경망 멤트랜지스터 전기화학 RAM(ECRAM)
강화학습 Q-러닝 사사 시간차(TD)
이론 커널 시스템 바이어스-분산 트레이드오프 계산학습이론 경험적 위험 최소화 오캄 학습 PAC 학습 통계학 VC 이론
기계 학습 장소 뉴럽스IPS ICML ML JMLR ArXiv:cs.LG
관련기사 인공지능 용어집 기계 학습 연구를 위한 데이터셋 목록 기계학습 개요
v t

인접성 성분 분석은 다변량 데이터를 데이터에 대한 주어진 거리 측정 기준에 따라 구별되는 등급으로 분류하기 위한 감독된 학습 방법이다.기능적으로는 K-가장 가까운 이웃 알고리즘과 같은 목적을 가지며, 확률적 가장 가까운 이웃이라고 하는 관련 개념을 직접 이용한다.

정의

인접성 성분 분석은 변환된 공간에서 평균 LAO(Lep-One-out) 분류 성능이 극대화되도록 입력 데이터의 선형 변환을 찾아 거리 메트릭을 "학습"하는 것을 목표로 한다.알고리즘에 대한 주요 통찰력은 $변환$에 해당하는$$ 매트릭스 $A{\displaystyle }$ ${\displaystyle A$에 대해 서로 다른 목표 함수를 정의한 다음, 결합 구배 강하와 같은 반복 용해제를 사용하면 변환에 해당하는 매트릭스 A ${\displaystyle A}$을(를) 찾을 수 있다는 것이다.이 알고리즘의 이점 중 하나는 $클래스{\displaystyle }$ k ${\$$displaystyle k}$의 수를 스칼라 상수까지 A $\{\backslash$$displaystyle A}$의 함수로 결정할 수 있다는 것이다$$.따라서 알고리즘의 이러한 사용은 모델 선택 문제를 다룬다.

설명

$A{\displaystyle }$ ${\displaystyle A}$을(를$)$ 정의하기 위해 변환된 공간의 분류 정확도를 설명하는 객관적 함수를 정의하고 이 객관적 함수가 최대화되도록$$ $∗{\$ A$^{*}$를 결정하려고 한다.

${\displaystyle A^{*}={\mbox{argmax}_{A}f(A)}$

leave-one-out(LO) 분류

$주어진{\displaystyle }$ 거리 메트릭을 가진 가장 가까운$$ k ${\displaystyle k}$의 일치에 의해 단일 데이터 포인트의 클래스 레이블을 예측하는 것을 고려해 보십시오.이것을 일탈 분류라고 한다.그러나 $가장{\displaystyle {}_{}}$ 가까운 C i{\$displaystyle C_{i}}$의 세트는 선형 변환을 통해 모든 포인트를 통과시킨 후 상당히 달라질 수 있다$$.특히 점의 인접 집합은 점의 인접성에 기초한$$ 객관적 함수 $f{\displaystyle }$ (${\displaystyle \cdot }$) ${\displaystyle f(\cdot )}$이(가) 조각적으로 일정하므로 서로 다를 수 없음을 $의미$하는 A$$${\displaystyle A}$ 요소의 원활한 변화에 대응하여 이산적인 변화를 겪을 수 있다.

해결책

우리는 확률적 경사 강하로부터 영감을 받은 접근법을 사용하여 이러한 어려움을 해결할 수 있다.LOE 분류에서$$ $각{\displaystyle }$ 변환$$지점에서 가장 $가까운$ k {\$displaystyle$ k$}$을(를) 고려하기보다는 전체 변환된 데이터 세트를 확률적 가장 가까운 인접 네트워크로 간주할 것이다.변환된 공간에서 주어진 LO-분류 지점과 서로 다른 지점 사이의 제곱 유클리드 거리의 소프트맥스 함수를 사용하여 다음을 정의한다.

${\displaystyle p_{ij}={\begin{cases}{\frac {e^{- Ax_{i}-Ax_{j} ^{2}}}{\sum _{k}e^{- Ax_{i}-Ax_{k} ^{2}}}},&{\mbox{if}}j\neq i\\0,&{\mbox{if}}j=i\end{cases}}}$

데이터 점 $i{\displaystyle }$ ${\displaystyle i}$을(를) 올바르게 분류할 확률은 동일한$$ 등급 $C{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$:

${\displaystyle p_{}}$ ${\displaystyle i_{}}$= ${\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{j}}$ ${\displaystyle \underset{}{\in }}$ ${\displaystyle \underset{}{{}_{}}}$ ${\displaystyle \underset{}{i_{}}}$ ${\displaystyle \underset{}{{}_{}}{}_{}}$ ${\displaystyle j_{}}$ $displaystyle p_{i}=\sum_{j\in C_{i}p_${ij$}\quad$}}. 여기서$$ $p{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ ${\displaystyle p_$${ij}}$는 점 $}$의 인접 j ${\displaystyle$ j$}$을 분류할 확률이다$.$

이번에는 전체 데이터 세트를 확률적 가장 가까운 이웃으로 사용하여 LOE 분류를 사용하여 목표 기능을 정의하십시오.

${\displaystyle f(A)=\sum _{i}\sum _{j\in C_{i}p_{ij}=\sum _{i}p_{i}}}}$

확률적으로 가장 가까운 이웃에 대한 단일 $지점{\displaystyle }$ i ${\displaystyle i}$에 대한 컨센서스 클래스는 인접 $지점{\displaystyle }$ j ${\displaystyle \in }$ ${\displaystyle C_{}}$ ${\displaystyle {}_{}}${\$displaystyle$ j$\in C_{i}}$에 대한 분포에서 추출한 샘플의 무한 개수의 한계에서 점 클래스의 기대 값이라는$$ 점에 유의하십시오.${\$$=클래스(X_{j})=p_{ij$따라서 예측 클래스는 각 $j{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle C_{}}$ j ${\$ j$\in C_{j}$에 대한 소프트맥스 함수에 의해 가중된 모든 다른 지점의 클래스의 어핀 조합이며, $여기$서 C ${\displaystyle j_{}}$ ${\$는 이제 전체 변환된 데이터 집합이다$$.

이러한 객관적 함수의 $선택$은 A$${\$displaystyle$A}에 대해 구별이 가능하기 때문에 바람직하다($$$x{\displaystyle {}_{}}$= ${\displaystyle x_{}}$ i${\displaystyle {}_{}}$- ${\displaystyle {}_{}}$ ${\displaystyle j_{}}${\$displaystyle x_{ij}=x_{i}-x_{j}}).$

${\displaystyle {\frac {\partial f}{\partial A}=-2A\sum _{i}\sum_{j\in C_{i}p_{ij}\left(x_{ij}x_{ij}}^{ij}}^{}}}T}-\sum _{k}p_{ik}x_{ik}x_{ik}^{{ik}^T}\오른쪽)$

${\displaystyle =2A\sum _{i}\{i}\sum _{k_{ik}x_{ik}x_{ik}x_{T}^{j\in C_{ij}x_{ij}x_{ij}^{ij}}^{{ij}}}^{{{}}}}}}}}}}}}}^{{}}}}}}}}}}}}}}}}^{{{}}}}}}}}}}}}}}}}}}T}\오른쪽)$

${\displaystyle A}$의 그라데이션 획득은 콘게이트 그라데이션 강하와 같은 반복적 용해제로 찾을 수 있음을 의미한다$$.실무에서 대부분의 구배 내측 용어들은 관심 지점에서 멀리 떨어진 지점의 기여도가 급격히 감소하기 때문에 미미한 기여도에 대해 평가한다는 점에 유의한다.즉, 그라데이션의 내부 합계를 잘라서 큰 데이터 집합에서도 합리적인 계산 시간을 얻을 수 있다.

대체 제형

"최대화 $f{\displaystyle }$ $){\$$displaystyle f(\$$cdot )}$는 예측된 클래스 분포와 실제 클래스 분포 사이의 $거리$$($즉, $A{\displaystyle }$ ${\displaystyle$ A$}$가 유도하는$$ $p{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$가 모두 1과 동일한 거리$)$를 최소화하는 것과 같다$$.자연스러운 대안은 KL-다이버전스(KL-diversity)로, 다음과 같은 객관적 기능과 구배를 유도한다."(골드버거 2005)

${\displaystyle g(A)=\sum _{i}\log \left(\sum _{j\in C_}}p_{ij}\right)=\sum _{i}\log(p_{i}}}}}}}}}$

${\displaystyle {\frac {\partial g}{\partial A}=2A\sum _{i}\{ik}p_{ik}x_{ik}x_{ik}^{T}-{\frac {\in C_{j_{ij}x_{ij^}T}{{\sum _{j\in C_{i}p_{ij}}\오른쪽)}$

실제로 이 기능을 사용하여$$ $A{\displaystyle }$ ${\displaystyle A}$을(를) 최적화하는 경우 원본과 유사한 성능 결과를 제공하는 경향이 있다.

역사와 배경

이웃성분 분석은 2004년 토론토 대학 컴퓨터공학과의 제이콥 골드버거, 샘 로위스, 러슬란 살라쿠디노프, 제프 힌튼에 의해 개발되었다.

참고 항목

• 스펙트럼 클러스터링
• 큰 여유 가장 가까운 이웃

참조

• J. Goldberger, G. Hinton, S. Roweis, R. Salakutdinov. (2005) 인접 성분 분석.신경 정보 처리 시스템의 발전. 17, 513–520, 2005.

외부 링크

소프트웨어

• MLPACK 라이브러리에는 C++ 구현이 포함되어 있음
• nca(C++)
• Sklearn 구현(Python)