Incorporação semidefinida - Semidefinite embedding

Maximum Variance Unfolding (MVU) , também conhecido como Semidefinite Embedding (SDE), é um algoritmo em ciência da computação que usa programação semidefinida para realizar a redução da dimensionalidade não linear de dados de entrada vetorial de alta dimensão .

É motivado pela observação de que a análise de componentes principais do kernel (kPCA) não reduz a dimensionalidade dos dados, pois aproveita o truque do kernel para mapear não linearmente os dados originais em um espaço interno do produto .

Algoritmo

MVU cria um mapeamento dos vetores de entrada de alta dimensão para algum espaço vetorial euclidiano de baixa dimensão nas seguintes etapas:

1. Um gráfico de vizinhança é criado. Cada entrada é conectada com seus vetores de entrada k-mais próximos (de acordo com a métrica de distância euclidiana) e todos os vizinhos k-mais próximos são conectados entre si. Se os dados são amostrados bem o suficiente, o gráfico resultante é uma aproximação discreta da variedade subjacente.
2. O gráfico de vizinhança é "desdobrado" com a ajuda da programação semidefinida. Em vez de aprender os vetores de saída diretamente, a programação semidefinida visa encontrar uma matriz de produto interna que maximize as distâncias aos pares entre quaisquer duas entradas que não estão conectadas no gráfico de vizinhança, preservando as distâncias dos vizinhos mais próximos.
3. A incorporação de baixa dimensão é finalmente obtida pela aplicação de escalonamento multidimensional na matriz de produto interna aprendida.

As etapas de aplicação de programação semidefinida seguidas de uma etapa de redução de dimensionalidade linear para recuperar uma incorporação de baixa dimensão em um espaço euclidiano foram propostas pela primeira vez por Linial , London e Rabinovich.

Formulação de otimização

Deixe ser a entrada original e a incorporação. Se forem dois vizinhos, a restrição de isometria local que precisa ser satisfeita é: ${\ displaystyle X \, \!}$${\ displaystyle Y \, \!}$${\ displaystyle i, j \, \!}$

${\ displaystyle | X_ {i} -X_ {j} | ^ {2} = | Y_ {i} -Y_ {j} | ^ {2} \, \!}$

Let Ser as matrizes Gram de e (ou seja:) . Podemos expressar a restrição acima para todos os pontos vizinhos em termos de : ${\ displaystyle G, K \, \!}$${\ displaystyle X \, \!}$${\ displaystyle Y \, \!}$${\ displaystyle G_ {ij} = X_ {i} \ cdot X_ {j}, K_ {ij} = Y_ {i} \ cdot Y_ {j} \, \!}$${\ displaystyle i, j \, \!}$${\ displaystyle G, K \, \!}$

${\ displaystyle G_ {ii} + G_ {jj} -G_ {ij} -G_ {ji} = K_ {ii} + K_ {jj} -K_ {ij} -K_ {ji} \, \!}$

Além disso, também queremos restringir a incorporação para centralizar na origem: ${\ displaystyle Y \, \!}$

${\ displaystyle 0 = | \ sum _ {i} Y_ {i} | ^ {2} \ Leftrightarrow (\ sum _ {i} Y_ {i}) \ cdot (\ sum _ {i} Y_ {i}) \ Leftrightarrow \ sum _ {i, j} Y_ {i} \ cdot Y_ {j} \ Leftrightarrow \ sum _ {i, j} K_ {ij}}$

Conforme descrito acima, exceto que as distâncias dos pontos vizinhos são preservadas, o algoritmo visa maximizar a distância entre pares de cada par de pontos. A função objetivo a ser maximizada é:

${\ displaystyle T (Y) = {\ dfrac {1} {2N}} \ sum _ {i, j} | Y_ {i} -Y_ {j} | ^ {2}}$

Intuitivamente, maximizar a função acima é equivalente a puxar os pontos o mais longe possível uns dos outros e, portanto, "desdobrar" a variedade. A restrição de isometria local

Deixe onde ${\ displaystyle \ tau = max \ {\ eta _ {ij} | Y_ {i} -Y_ {j} | ^ {2} \} \, \!}$${\ displaystyle \ eta _ {ij}: = {\ begin {cases} 1 & {\ mbox {if}} \ i {\ mbox {é um vizinho de}} j \\ 0 & {\ mbox {caso contrário}}. \ fim {casos}}}$

impede a função objetivo de divergir (indo para o infinito).

Como o gráfico tem N pontos, a distância entre dois pontos quaisquer . Podemos então limitar a função objetivo da seguinte maneira: ${\ displaystyle | Y_ {i} -Y_ {j} | ^ {2} \ leq N \ tau \, \!}$

${\ displaystyle T (Y) = {\ dfrac {1} {2N}} \ sum _ {i, j} | Y_ {i} -Y_ {j} | ^ {2} \ leq {\ dfrac {1} { 2N}} \ sum _ {i, j} (N \ tau) ^ {2} = {\ dfrac {N ^ {3} \ tau ^ {2}} {2}} \, \!}$

A função objetivo pode ser reescrita puramente na forma da matriz de Gram:

${\ displaystyle {\ begin {align} T (Y) & {} = {\ dfrac {1} {2N}} \ sum _ {i, j} | Y_ {i} -Y_ {j} | ^ {2} \\ & {} = {\ dfrac {1} {2N}} \ sum _ {i, j} (Y_ {i} ^ {2} + Y_ {j} ^ {2} -Y_ {i} \ cdot Y_ {j} -Y_ {j} \ cdot Y_ {i}) \\ & {} = {\ dfrac {1} {2N}} (\ sum _ {i, j} Y_ {i} ^ {2} + \ soma _ {i, j} Y_ {j} ^ {2} - \ sum _ {i, j} Y_ {i} \ cdot Y_ {j} - \ sum _ {i, j} Y_ {j} \ cdot Y_ {i}) \\ & {} = {\ dfrac {1} {2N}} (\ sum _ {i, j} Y_ {i} ^ {2} + \ sum _ {i, j} Y_ {j} ^ {2} -0-0) \\ & {} = {\ dfrac {1} {N}} (\ sum _ {i} Y_ {i} ^ {2}) = {\ dfrac {1} {N }} (Tr (K)) \\\ end {alinhado}} \, \!}$

Finalmente, a otimização pode ser formulada como:

${\ displaystyle {\ begin {align} & {\ text {Maximize}} && Tr (\ mathbf {K}) \\ & {\ text {subject to}} && \ mathbf {K} \ successq 0, \ sum _ { ij} \ mathbf {K} _ {ij} = 0 \\ & {\ text {and}} && G_ {ii} + G_ {jj} -G_ {ij} -G_ {ji} = K_ {ii} + K_ { jj} -K_ {ij} -K_ {ji}, \ forall i, j {\ mbox {onde}} \ eta _ {ij} = 1, \ end {alinhado}}}$

Depois que a matriz de Gram é aprendida por programação semidefinida, a saída pode ser obtida por meio da decomposição de Cholesky . ${\ displaystyle K \, \!}$${\ displaystyle Y \, \!}$

Em particular, a matriz de Gram pode ser escrita como onde está o i-ésimo elemento do autovetor do autovalor . ${\ displaystyle K_ {ij} = \ sum _ {\ alpha = 1} ^ {N} (\ lambda _ {\ alpha} V _ {\ alpha i} V _ {\ alpha j}) \, \!}$${\ displaystyle V _ {\ alpha i} \, \!}$${\ displaystyle V _ {\ alpha} \, \!}$${\ displaystyle \ lambda _ {\ alpha} \, \!}$

Segue-se que o -ésimo elemento da saída é . ${\ displaystyle \ alpha \, \!}$${\ displaystyle Y_ {i} \, \!}$${\ displaystyle {\ sqrt {\ lambda _ {\ alpha}}} V _ {\ alpha i} \, \!}$

Veja também

• Incorporação localmente linear
• Isometria (matemática)
• Alinhamento de espaço tangente local
• Variedade Riemanniana
• Minimização de energia

Notas

Referências

• Linial, London e Rabinovich, Nathan, Eran e Yuri (1995). “A geometria dos gráficos e algumas das suas aplicações algorítmicas” . Combinatorica . 15 (2): 215–245. doi : 10.1007 / BF01200757 . S2CID   5071936 .
• Weinberger, Sha e Saul, Kilian Q., Fei e Lawrence K. (4 de julho de 2004a). Aprendendo uma matriz kernel para redução de dimensionalidade não linear . Anais da Vigésima Primeira Conferência Internacional sobre Aprendizado de Máquina (ICML 2004). Banff, Alberta , Canadá.
• Weinberger e Saul, Kilian Q. e Lawrence K. (27 de junho de 2004b). Aprendizagem não supervisionada de variedades de imagens por programação semidefinida . 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2 .
• Weinberger e Saul, Kilian Q. e Lawrence K. (1 de maio de 2006). "Aprendizagem não supervisionada de variedades de imagens por programação semidefinida" (PDF) . International Journal of Computer Vision . 70 : 77–90. doi : 10.1007 / s11263-005-4939-z . S2CID   291166 .
• Lawrence, Neil D (2012). "Uma perspectiva probabilística unificadora para a redução da dimensionalidade espectral: percepções e novos modelos" . Journal of Machine Learning Research . 13 (maio): 1612. arXiv : 1010.4830 . Bibcode : 2010arXiv1010.4830L .

Material adicional

• Código MVU Matlab de Kilian Q. Weinberger