다지관 정규화

머신러닝에서, 다지관 정규화는 데이터 집합에서 배워야 할 기능을 제약하기 위해 데이터 집합의 형태를 사용하는 기술이다.많은 머신러닝 문제에서 학습해야 할 데이터가 입력 공간 전체를 커버하지 않는다.예를 들어 안면 인식 시스템은 가능한 이미지를 분류할 필요가 없고, 얼굴이 포함된 이미지의 부분 집합만 분류할 필요가 있을 수 있다.다지관 학습 기법은 데이터의 관련 부분집합이 유용한 특성을 가진 수학 구조인 다지관에서 온다고 가정한다.이 기법은 또한 학습해야 할 기능이 원활하다고 가정한다. 라벨이 서로 다른 데이터는 서로 근접하지 않을 가능성이 높기 때문에 데이터 포인트가 많을 가능성이 높은 영역에서 라벨링 기능이 빠르게 변경되지 않아야 한다.이러한 가정 때문에, 다지관 정규화 알고리즘은 티호노프 정규화 기법의 확장을 이용하여, 학습된 기능이 빠르게 변화할 수 있는 장소와 그렇지 않은 장소를 알려주기 위해 라벨이 부착되지 않은 데이터를 사용할 수 있다.다지관 정규화 알고리즘은 라벨이 부착되지 않은 데이터를 사용할 수 있는 준감독 학습 및 유도 학습 설정에서 감독된 학습 알고리즘을 확장할 수 있다.이 기법은 의료 영상, 지리적 영상, 물체 인식 등의 용도에 사용되어 왔다.

다지관 정규화기

동기

다지관 정규화는 규칙화의 한 종류로, 복잡한 해결책을 불이익을 주어 과잉 피팅을 줄이고 문제가 잘 해결되도록 하는 기법이다.특히 다지관 정규화는 RKHS(Replicating kernel Hilbert space)에 적용된 티호노프 정규화의 기법을 확장한다.RKHS에 대한 표준 Tikhonov 정규화 하에서는 학습 알고리즘이 함수 $H{\displaystyle \mathcal{}}$ ${\$의 가설 공간 중에서$$ 함수 $f{\displaystyle }$ ${\displaystyle f}$를 배우려고 시도한다$.$ 가설 공간은 RKHS로서 $커널{\displaystyle }$ K ${\displaysty K$와 연관되어 있다는 것을 의미하며, 모든 후보 func.tion $f{\displaystyle }$ ${\displaystyle f}$에는 가설 공간에서 후보 함수의 복잡성을 나타내는 표준 represents ${\displaystyle f_{}}$ ${\displaystyle {\Vert }_{}}$ $display$ K {\displaystyle\$\f\right\ _{K}}$가 있다$$$.$알고리즘이 후보 함수를 고려할 때, 복잡한 함수에 불이익을 주기 위해 그 규범을 고려한다.

Formally, given a set of labeled training data ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{\ell },y_{\ell })}$ with ${\displaystyle x_{i}\in X,y_{i}\in Y}$ and a loss function ${\displaystyle V}$, a learning algorithm using Tikhonov regularization will att그 표현을 풀려고 비우다.

${\displaystyle {\underset {f\in {\mathcal{H}}{\arg \!\min }{1}{1}\sum _{i=1}^{{i}}\ell }V(f(x_{i}), y_}+\gamma \lef\f\{K}^2}}:$

여기서 $\gamma {\displaystyle }$ ${\displaystyle \gamma}$은 알고리즘이 데이터에 더 잘 맞는 함수보다 얼마나 간단한 함수를 선호하는지를 제어하는 하이퍼 파라미터다.

다지관 정규화는 표준 티코노프 정규화에 사용되는 주변 정규화에 두 번째 정규화 용어인 내성 정규화 용어를 추가한다.시스템 학습의 다지관 가정 하에서, 문제의 데이터는 전체 입력 $공간{\displaystyle }$ X ${\displaystyle$ X$\}$에서 오는 것이 아니라 비선형 다지관 ${\displaystyle M}$ ${\displaystyle \subset }$ X ${\displaystyle M\subset$ X$}$에서 오는 $것$이다$.$이 다지관의 기하학, 내적 공간은 정규화 규범을 결정하는 데 사용된다.^[1]

라플라시안 규범

$\Vert {\displaystyle {}_{}}$ ${\displaystyle f_{}}$ ${\displaystyle {\Vert }_{}}$ ${\displaystyle {}_{}}$ ${\$에 대한 가능한 선택 사항이 많다. $.$ ${\displaystyle M_{}}$ ${\$다지관의 경사를 수반하는 자연적인 선택도 많이 있어 대상 함수의 평활도를 측정할 수 있다.부드러운 함수는 입력 데이터가 밀집한 곳에서 천천히 변경되어야 한다. 즉, 구배 gradient${\displaystyle {\mathrm{}}_{}}$ f${\displaystyle }$( $){\displaystyle \nabla _{M}f(x)}$는 한계 확률 ${\displaystyle {밀도}_{}}$ ${\displaystyle P}$ X${\displaystyle {}_{}}$( x$){\displaystyle {\mathcal{P}_{X$ 임의로 그려진 데이터 포인트의 확률 $밀도$가 x ${\di$에 나타나야 한다$$.$splaystyle x}$은$($는) 크다.이것은 내적 정규화기에 적절한 한 가지 선택권을 준다.

${\displaystyle \left\f\right\_{I}^{2}=\int_{x\in M}\left\\nabla_{M}f(x)\right\ ^{2}\d{\mathcal {P}_{X}}}}}}}}$

실제로 이 $표준$은 ${\displaystyle {한계}_{}}$ 분포 P X ${\displaystyle$ {\$mathcal{P}_{X}}$을(를) 알 수 없으므로 직접 계산할 수 없지만 제공된 데이터에서 추정할 수 있다.

라플라시안 표준의 그래프 기반 접근법

입력 지점 사이의 거리가 그래프로 해석되는 경우 그래프의 라플라크 행렬이 한계 분포를 추정하는 데 도움이 될 수 있다.입력 데이터에 $\ell {\displaystyle }$ ${\displaystyle \ell}$ 레이블이$$ 있는 예제($입력{\displaystyle }$ x ${\displaystyle$ $x$$}$ 및$$ 레이블 $y{\displaystyle }$ ${\displaystyle$ y$\})$와 $u{\displaystyle }$ ${\displaystyle u}$ 레이블이$$ 없는 예제(관련 레이블이 없는 입력)가 포함되어 있다고 가정합시다.$W{\displaystyle }$ ${\displaystyle W}$을(를) 그래프의 에지 가중치 행렬로 정의하십시오$$. 여기서 ${\displaystyle {\mathrm{Wi}}_{}}$ j ${\$$displaystyle$ $W_$${i}$은(는) 데이터 포인트 x ${\displaystyle i_{}}$ ${\$과$($${\displaystyle \underset{}{\overset{}{}}}$) {\$displaystystyle D}$을(${\displaystyle \underset{}{\overset{}{Di}}}$ =${\displaystyle \underset{}{\overset{}{}}}$∑)로 정의하십시오$$.${\displaystyle D_{ii}=\sum _{j=1}^{\ell +u}W_{ij}}$ and ${\displaystyle L}$ to be the Laplacian matrix ${\displaystyle D-W}$. Then, as the number of data points ${\displaystyle \ell +u}$ increases, ${\displaystyle L}$ converges to the Laplace–Beltrami operator ${\displaystyle \De$$lta _{M}}$, which is the divergence of the gradient ${\displaystyle \nabla _{M}}$.^[2][3] Then, if ${\displaystyle \mathbf {f} }$ is a vector of the values of ${\displaystyle f}$ at the data, ${\displaystyle \mathbf {f} =[f(x_{1}),\ldots ,f(x_{l+u})]$$^{\mathrm{T$ 본질적인 규범을 추정할 수 있다.

${\displaystyle \왼쪽\f\오른쪽\ _{I}^{2}={\frac {1}{{1}(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}}$

데이터 포인트 $\ell {\displaystyle }$+ ${\displaystyle u}$ ${\displaystyle \ell +u}$이(가)^[1] 증가함에$$ 따라 $\Vert {\displaystyle {}_{}^{}}$ ${\displaystyle f_{}^{}}$ ${\displaystyle {\Vert }_{}^{}}$ I ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$\ \$f\right\ _{I}^{$$X}}}$의 경험적 $정의$가 ${\displaystyle {PX}_{}}${\$displaystystyle {\{\mathcal$}}}}}}}}}}}}}}이 알려지면 정의로 수렴된다$.$

그래프 기반 접근 방식으로 정규화 문제 해결

주변 및 내인성 정규제 $\gamma {\displaystyle {}_{}}$$$$${\$displaystyle \gamma _{A}$ 및$$ $\gamma {\displaystyle {}_{}}$ ${\displaystyle I_{}}$ ${\$의 가중치를 사용하여 해결할 최종 표현은 다음과 같이 된다.

${\displaystyle {\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }V(f(x_{i}),y_{i})+\gamma _{A}\left\ f\right\ _{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}}$

다른 커널 방법과 마찬가지로 $H{\displaystyle \mathcal{}}$ ${\$도 무한 차원 공간일 수 있으므로$$ 정규화 식을 명시적으로 풀 수 없다면 공간 전체를 검색해 해결책을 찾을 수 없다.대신, 대표자 정리는 표준 $\Vert {\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\Vert }_{}}$ I ${\$의 선택에 관한 특정 조건 하에서 최적의 $용액{\displaystyle {}^{}}$ f${\displaystyle {}^{}}${$${\$displaystyle$ f$^{*}}}$는 각 입력 지점을 중심으로 한 커널의 선형 조합이어야 함을$$ 보여준다. 일부 ${\displaystyle {가중치}_{}}$α i {\$displaystylepha_{i$$}}$,

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\알파 _{i}K(x_{i}x)}}$

이 결과를 이용하여 ${\displaystyle {\alpha i}_{}}$ ${\$의 가능한 선택에 의해 정의된 유한차원 공간을 검색함으로써$$ 최적의 솔루션 $∗{\$를 검색할 수 있다$.$^[1]

라플라시안 표준의 기능적 접근법

그래프-라플라시안 이상의 아이디어는 이웃을 이용하여 라플라시안을 추정하는 것이다.이 방법은 고차원적 문제에서 저확장성이 낮은 것으로 알려진 국소 평균화 방법과 유사하다.실제로 그래프 라플라시안은 차원성의 저주에 시달리는 것으로 알려져 있다.^[2]운 좋게도, 더 진보된 기능 분석 덕분에 예상되는 기능의 부드러움을 추정하는데 활용할 수 있다.${\displaystyle {이\mathrm{}}_{}}$ 방법은 첫 번째 변수의 j번째 좌표에 따른 부분파생상품을 나타내는$$$$ 커널 판독값 $\partial {\displaystyle {\mathrm{}}_{1\mathrm{},}}$ ${\displaystyle K_{}}$${\displaystyle }$(${\displaystyle {}_{}}$ $){\$$displaystyle \partial _{1}K$$($^[4]x_{ni}x$)$의 파생상품 덕분에 라플라시안 연산자를 추정할 때 구성된다${\displaystyle {.}_{}}$라플라시안 표준의 이 두 번째 접근방식은 그물망 없는 방법, 즉 PDE의 유한 차이 방법과 대비를 이루는 것이다.

적용들

다지관 정규화는 적절한 손실 $함수{\displaystyle }$ V ${\displaystyle V}$과 가설 $공간{\displaystyle \mathcal{}}$ H ${\$을(를) 선택하여 티코노프 정규화를 사용하여 표현할 수 있는 다양한 알고리즘을 확장할 수 있다$.$ 일반적으로 사용되는 두 가지 예는 지원 벡터 머신 계열과 정규화된 최소 제곱 a이다.lgograms. (정규화된 최소 제곱은 능선 회귀 알고리즘을 포함한다. LASSO의 관련 알고리즘과 탄력적인 순 정규화는 지원 벡터 머신으로 표현될 수 있다.)^[5][6]이러한 알고리즘의 확장 버전은 각각 Laplacian 정규화된 최소 제곱(약칭 LapRLS)과 Laplacian Support Vector Machine(LapSVM)이라고 불린다.^[1]

라플라시안 정규화 최소 제곱(LapRLS)

정규화된 최소 제곱(RLS)은 회귀 알고리즘의 제품군: $예측{\displaystyle }$ 값이 데이터의 실제 라벨에 근접해야 한다는 목표로 입력 x ${\displaystyle y$$=f(x$$)}$에 대한$$ $y{\displaystyle }$= ${\displaystyle f(x}$) ${\displaystyle$ y=f(x$)\}$ 값을 예측하는 알고리즘이다.특히 RLS는 정규화에 따라 예측값과 참 라벨 사이의 평균 제곱 오차를 최소화하도록 설계되었다.리지 회귀 분석은 RLS의 한 형태로서, 일반적으로 RLS는 리지 회귀 분석과 커널 방법을 결합한 것과 동일하다.^{[citation needed]}Tikhonov 정규화에서$$ 손실 함수 $V{\displaystyle }$ ${\displaystyle V}$을(를) 평균 제곱 오차로 선택한 RLS 결과에 대한 문제 진술:

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma \left\ f\right\ _{K}^{2}}$

대표자 정리 덕분에, 솔루션은 데이터 포인트에서 평가된 커널의 가중치 합으로 작성할 수 있다.

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell }\알파 _{i}^{*}K(x_{i}x)}}$

$\alpha {\displaystyle {}^{}}$ $∗{\$\ \ $^{*}}$에 대한 해결 방법은$$ 다음과 같다.

${\displaystyle \alpha ^{*}=(K+\gamma \ell I)^{-1}Y}$

여기서 $K{\displaystyle }$ ${\displaystyle K}$은(는) 커널 매트릭스로 정의되며$$, ${\displaystyle {\mathrm{Ki}}_{}}$ j${\displaystyle {}_{}}$= ${\displaystyle K(x_{}}$ i${\displaystyle {}_{}}$, x ${\displaystyle j_{}}$) ${\displaystyle K_{i}=K(x_{i},x_{j}}),$Y ${\displaysty Y}$은 $데이터$ 레이블의 벡터다.

다지관 정규화를 위한 라플라시안 용어를 추가하면 라플라시안 RLS 문장이 다음과 같다.

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma _{A}\left\ f\right\ _{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}}$

다지관 정규화를 위한 대표자 정리는 다시 주어진다.

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\알파 _{i}^{*}K(x_{i}x)}}$

and this yields an expression for the vector ${\displaystyle \alpha ^{*}}$. Letting ${\displaystyle K}$ be the kernel matrix as above, ${\displaystyle Y}$ be the vector of data labels, and ${\displaystyle J}$ be the ${\displaystyle (\ell +u)\times (\ell +u)}$ block matrix ${\$$I_{\ell }&0\\0&0_{u}\end{bmatrix$ :

${\displaystyle \alpha ^{*}={\underset {\alpha \in \mathbf {R} ^{\ell +u}}{\arg \!\min }}{\frac {1}{\ell }}(Y-JK\alpha )^{\mathrm {T} }(Y-JK\alpha )+\gamma _{A}\alpha ^{\mathrm {T} }K\alpha +{\frac {\gamma _{I}}{(\ell +u)^{2}}}\알파 ^{\mathrm {T}}KLK\alpha }$

의 해결책으로

${\displaystyle \alpha ^{*}=\왼쪽(JK+\gamma _{A}\ell I+{A}\frac {\gamma _{I}\ell +u)^{2}}}{{K\오른쪽)^{-1}Y}$^[1]

LapRLS는 센서 네트워크,^[7] 의료 영상화,^[8][9] 물체 감지,^[10] 분광학,^[11] 문서 분류,^[12] 약물-단백질 상호작용,^[13] 영상 및 비디오 압축 등의 문제에 적용되었다.^[14]

Laplacian 지원 벡터 머신(LapSVM)

SVM(Support Vector Machine)은 데이터를 둘 이상의 그룹 또는 클래스로 분류하는 데 종종 사용되는 알고리즘 제품군이다.직관적으로 SVM은 경계와 가장 가까운 라벨이 부착된 예들이 가능한 멀리 떨어져 있도록 등급 간의 경계를 그린다.이는 선형 프로그램으로 직접 표현할 수 있지만, 힌지 손실 $함수$인 V${\displaystyle (f}$(${\displaystyle x}$) ,${\displaystyle y}$) =${\displaystyle 최대}$ ( ${\displaystyle 0,1}$ -${\displaystyle y}$ (${\displaystyle x}$) ${\displaystyle V($f$(x),y)=\max(0,1-yf(x)}}$:

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma \left\ f\right\ _{K}^{2}}$^[15][16]

이 표현식에 내재된 정규화 용어를 추가하면 다음과 같은 LapSVM 문제 진술이 나온다.

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma _{A}\left\ f\right\ _{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}}$

다시 말하지만, 대표자 정리는 데이터 지점에서 평가된 커널의 관점에서 솔루션을 표현할 수 있게 한다.

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\알파 _{i}^{*}K(x_{i}x)}}$

${\displaystyle \alpha }$ ${\displaystyle \alpha}$은(는) 문제를 선형 프로그램으로 작성하고 이중 문제를 풀면 찾을 수 있다$$.다시 $K{\displaystyle }$ ${\displaystyle K}$을(를) 커널 매트릭스, $J{\displaystyle }$ ${\displaystyle J}$을(를) 블록 매트릭스[ u ${\$로 설정$I_{{\ell$}&$0\\0&0_{u}\end{bmatrix$ 솔루션은 다음과 같이 보일 수 있다.

${\displaystyle \alpha =\left(2\gamma _{A}I+2{\frac {\gamma _{I}}}{{I}}}\ell +u)^{2}}}{{{{1}J^{\mathrm {T}}}Y\베타 ^{*}}}}$

여기서 $\beta {\displaystyle {}^{}}$ $∗{\$는 이중 문제의$$ 해결책이다.

${\displaystyle {\begin{aligned}&&\beta ^{*}=\max _{\beta \in \mathbf {R} ^{\ell }}&\sum _{i=1}^{\ell }\beta _{i}-{\frac {1}{2}}\beta ^{\mathrm {T} }Q\beta \\&{\text{subject to}}&&\sum _{i=1}^{\ell }\beta _{i}y_{i}=0\\&&&0\leq \beta _{i}\leq {\frac {1}{\ell }}\;i=1,\ldots ,\ell \end{aligned}}}$

$Q{\displaystyle }$ ${\displaystyle$ Q$}$은(는) 다음에 의해 정의됨$$

${\displaystyle Q=YJK\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{{{I}})(\ell +u)^{2}}}{{{{1}J^{\mathrm{T}}}Y}$^[1]

LapSVM은 지리적 이미징,^[17][18][19] 의료 이미지,^[20][21][22] 얼굴 인식,^[23] 기계 유지보수,^[24] 뇌-컴퓨터 인터페이스 등의 문제에 적용되었다.^[25]

제한 사항

• 다지관 정규화는 서로 다른 라벨을 가진 데이터가 서로 근접하지 않을 것으로 가정한다.이러한 가정은 기법이 라벨이 부착되지 않은 데이터로부터 정보를 끌어낼 수 있게 하는 것이지만, 그것은 일부 문제 영역에만 적용된다.데이터의 구조에 따라 다른 반감독 또는 유도 학습 알고리즘을 사용할 필요가 있을 수 있다.^[26]
• 일부 데이터 집합에서 함수 $\Vert {\displaystyle {}_{}}$ ${\displaystyle f_{}}$ ${\displaystyle {\Vert }_{}}$ ${\displaystyle {}_{}}$ ${\$$displaystyle \left$$\f\$$right\ _{I$의 내적 표준은 주변 ${\displaystyle {}_{}}$에 매우 근접할$$ 수 있다$.$ 예를 들어 데이터가 수직선에 있는 두 등급으로 구성된 경우 내적 표준은 주변 표준과 동일할 것이다.이 경우 분리기가 매끄러워야 한다는 알고리즘의 가정에 데이터가 적합하더라도 라벨이 부착되지 않은 데이터는 다지관 정규화에 의해 학습된 용액에 영향을 미치지 않는다.이러한 한계를 해결하기 위해 공동 훈련과 관련된 접근법이 제안되었다.^[27]
• 라벨이 부착되지 않은 예시가 매우 많으면 커널 매트릭스 $K{\displaystyle }$ ${\displaystyle K}$이(가$$) 매우 커지며, 다지관 정규화 알고리즘이 엄청나게 느리게 계산될 수 있다.이 경우 다지관의 온라인 알고리즘과 희박한 근사치가 도움이 될 수 있다.^[28]

소프트웨어

• 매니폴드러닝 라이브러리와 프라이멀 LapSVM 라이브러리는 MATLAB에서 LapRLS 및 LapSVM을 구현한다.
• C++용 Dlib 라이브러리에는 선형 다지관 정규화 기능이 포함되어 있다.

참고 항목

• 다지관 학습
• 다지관 가설
• 반감독학습
• 전도(기계 학습)
• 스펙트럼 그래프 이론
• 커널 힐버트 공간 재현
• 티호노프 정규화
• 미분 기하학

참조