Aula Soluções
- Um vetor de características (feature vector) de dimensão \(d\) é denotado \(\mathbf{x}\in\mathbb{R}^d\), vetor-coluna com componentes \(x_1,\dots,x_d\).
- O conjunto de treino de um problema supervisionado é \(\mathcal D=\{(\mathbf x_i,y_i)\}_{i=1}^N\), com \(\mathbf x_i\in\mathbb R^d\) e \(y_i\) o rótulo/alvo. O \(k\)-NN prevê o rótulo de uma consulta \(\mathbf x_{\text{novo}}\) por votação (classificação) ou média (regressão) dos \(k\) pontos de \(\mathcal D\) mais próximos de \(\mathbf x_{\text{novo}}\).
- Um subconjunto \(U\subseteq V\) de um espaço vetorial é um subespaço vetorial se e só se passa no teste de fechamento: (i) contém a origem \(\mathbf 0\); (ii) é fechado sob soma (\(\mathbf x,\mathbf y\in U\Rightarrow \mathbf x+\mathbf y\in U\)); (iii) é fechado sob multiplicação por escalar (\(\mathbf x\in U,\lambda\in\mathbb R\Rightarrow \lambda\mathbf x\in U\)).
- Uma norma \(\|\cdot\|:V\to\mathbb R\) satisfaz homogeneidade absoluta (\(\|\lambda x\|=|\lambda|\|x\|\)), desigualdade triangular (\(\|x+y\|\le\|x\|+\|y\|\)) e positividade definida (\(\|x\|\ge0\), com igualdade só em \(x=\mathbf 0\)). As normas \(L_1\), \(L_2\) e \(L_\infty\) desta aula são \(\|x\|_1=\sum_i|x_i|\), \(\|x\|_2=\sqrt{\sum_i x_i^2}\) e \(\|x\|_\infty=\max_i|x_i|\).
- Uma métrica \(d:X\times X\to\mathbb R\) satisfaz não-negatividade (\(d(x,y)\ge0\), com \(d(x,y)=0\iff x=y\)), simetria (\(d(x,y)=d(y,x)\)) e desigualdade triangular (\(d(x,z)\le d(x,y)+d(y,z)\)). Toda norma induz uma métrica por \(d(x,y)=\|x-y\|\).
- A Similaridade do Cosseno entre \(x,y\in\mathbb R^n\setminus\{\mathbf 0\}\) é \(\text{Sim}_{\cos}(x,y)=\frac{\langle x,y\rangle}{\|x\|_2\|y\|_2}=\cos\theta\), e a Distância do Cosseno é \(d_{\cos}(x,y)=1-\cos\theta\).
Questões discursivas
A Hipótese de Suavidade que fundamenta o \(k\)-NN afirma que pontos próximos no espaço de características \(\mathbb{R}^d\) tendem a ter rótulos semelhantes, e a distância usada para decidir “o que é próximo” é tipicamente a Euclidiana, \(d_2(\mathbf x,\mathbf y)=\|\mathbf x-\mathbf y\|_2\), que soma os quadrados das diferenças em cada coordenada. Considere um paciente descrito pelo vetor \(\mathbf x=[\text{idade em anos}, \text{glicose em mg/dL}]^T\), com idade tipicamente entre \(0\) e \(100\) e glicose tipicamente entre \(70\) e \(400\). Explique, usando a fórmula da distância Euclidiana, por que aplicar o \(k\)-NN diretamente sobre esse vetor (sem reescalonar as duas características para uma faixa comparável) pode fazer com que a “proximidade” calculada pelo algoritmo deixe de refletir corretamente a Hipótese de Suavidade — ou seja, por que dois pacientes considerados “vizinhos” pelo algoritmo podem não ser, de fato, semelhantes nos dois atributos.
Use o teste de fechamento apresentado nesta aula (conter a origem; ser fechado sob soma; ser fechado sob multiplicação por escalar) para determinar se o círculo unitário \(C=\{\mathbf x\in\mathbb R^2 : \|\mathbf x\|_2=1\}\) — um exemplo simples de variedade curva unidimensional embutida em \(\mathbb R^2\) — é um subespaço vetorial de \(\mathbb R^2\). Diga explicitamente qual (ou quais) das três condições falha, exibindo um contraexemplo numérico concreto (dois pontos de \(C\) cuja soma, ou algum múltiplo escalar, não pertence a \(C\)).
A prova apresentada nesta aula de que a Distância do Cosseno \(d_{\cos}(x,y)=1-\cos\theta\) viola a desigualdade triangular usa três vetores unitários em \(\mathbb R^2\) a \(0^\circ\), \(90^\circ\) e \(135^\circ\). Repita a verificação numérica com um trio diferente de ângulos de sua escolha (mantendo os vetores em \(\mathbb R^2\)) que também viole a desigualdade triangular, mostrando os três valores de \(d_{\cos}\) envolvidos. Em seguida, explique por que a distância cordal \(\sqrt{2\,d_{\cos}(x,y)} = \|\hat x-\hat y\|_2\) não sofre do mesmo problema, mesmo sendo definida a partir da mesma quantidade \(d_{\cos}\).
Questões de Verdadeiro/Falso
Cada bloco de 4 itens trata do mesmo tema. A questão só é considerada correta se todos os 4 itens forem julgados corretamente (deixar em branco tem penalidade de 20% da nota da questão).
- □ Considere um vetor de atualização em otimização \(\Delta\mathbf{w}=-\eta\nabla L(\mathbf w)\), onde \(\eta>0\) é a taxa de aprendizado e \(\nabla L(\mathbf w)\) é o vetor gradiente da função de perda. Se, por um erro de implementação, o sinal de \(\eta\) fosse trocado para negativo, o vetor de atualização passaria a apontar exatamente na mesma direção de \(\nabla L(\mathbf w)\).
- □ Multiplicar um vetor de características \(\mathbf x\in\mathbb R^d\) por um escalar \(\alpha=0\) produz o vetor nulo, que deixa de estar associado a qualquer direção específica no espaço de características — a operação de escalonamento, portanto, deixa de estar definida nesse caso extremo.
- □ Em um sistema de recomendação, o vetor de perfil de um usuário é atualizado a cada clique somando um vetor de “interesse” ao perfil atual, \(\mathbf p_{t+1}=\mathbf p_t+\mathbf c_t\). Essa soma acumula sinais ao longo do tempo exatamente da mesma forma que a soma \(\mathbf u+\mathbf v\) de dois vetores de características, mesmo que \(\mathbf p_t\) e \(\mathbf c_t\) vivam em um espaço de embeddings de alta dimensão em vez de \(\mathbb R^2\).
- □ Como a soma de vetores segue a regra do paralelogramo e produz um vetor “maior” que cada parcela, é sempre verdade que \(\|\mathbf u+\mathbf v\|_2>\|\mathbf u\|_2\) e \(\|\mathbf u+\mathbf v\|_2>\|\mathbf v\|_2\), para quaisquer vetores não nulos \(\mathbf u,\mathbf v\in\mathbb R^d\).
- □ Se o hiperparâmetro \(k\) do \(k\)-NN for definido como \(k=N\) (igual ao número total de amostras de \(\mathcal D\)), a predição \(\hat y_{\text{novo}}\) para regressão (média dos \(k\) vizinhos) deixa de depender da posição da consulta \(\mathbf x_{\text{novo}}\), tornando-se constante para qualquer consulta.
- □ Suponha que a Hipótese de Suavidade fosse completamente falsa para um determinado problema — isto é, pontos muito próximos em \(\mathbb R^d\) tivessem rótulos tão distintos entre si quanto pontos distantes. Nesse cenário, aumentar \(k\) (considerar mais vizinhos na votação/média) resolveria o problema, pois a agregação por votação/média sempre corrige rótulos ruidosos.
- □ No \(k\)-NN, a fase de “treino” consiste apenas em armazenar o conjunto \(\mathcal D\), sem nenhuma otimização de parâmetros. Esse mesmo padrão — toda a “aprendizagem” reduzida a memorizar os dados, sem fase de ajuste de parâmetros — também descreve corretamente um classificador de regressão logística.
- □ Como o \(k\)-NN é chamado de método “não paramétrico”, isso significa que ele não possui nenhum hiperparâmetro a ser escolhido, sendo aplicado sempre da mesma forma independentemente do conjunto de dados.
- □ O subconjunto \(U=\{\mathbf 0\}\), contendo apenas o vetor nulo de \(\mathbb R^d\), satisfaz as três condições de fechamento (conter a origem, ser fechado sob soma, ser fechado sob multiplicação por escalar) e portanto é, tecnicamente, um subespaço vetorial válido, ainda que trivial.
- □ Considere o conjunto-solução de um sistema não homogêneo \(A\mathbf x=\mathbf b\) com \(\mathbf b\ne\mathbf 0\) fixo e solúvel, isto é, \(U=\{\mathbf x\in\mathbb R^n : A\mathbf x=\mathbf b\}\). Esse conjunto deixa de conter a origem (pois \(A\mathbf 0=\mathbf 0\ne\mathbf b\)), mas ainda assim permanece fechado sob soma: dados \(\mathbf x_1,\mathbf x_2\in U\), a soma \(\mathbf x_1+\mathbf x_2\) também satisfaz \(A(\mathbf x_1+\mathbf x_2)=\mathbf b\).
- □ Considere o conjunto de todos os vetores de pesos \(\mathbf w\in\mathbb R^d\) de um classificador linear tais que o hiperplano de decisão \(\mathbf w^T\mathbf x=0\) passe exatamente por um ponto fixo \(\mathbf x_0\in\mathbb R^d\), \(\mathbf x_0\ne\mathbf 0\) — ou seja, \(U=\{\mathbf w\in\mathbb R^d : \mathbf w^T\mathbf x_0=0\}\). Esse conjunto \(U\) é um subespaço vetorial de \(\mathbb R^d\).
- □ Como subespaços vetoriais devem ser “fechados” segundo as três condições acima, e o conjunto de vetores de características associados a exemplos de uma única classe \(y=1\), em um problema de classificação binária, corresponde a uma região geometricamente “fechada” (limitada) do espaço, esse conjunto é necessariamente um subespaço vetorial de \(\mathbb R^d\).
- □ Considere dados que vivem exatamente sobre a superfície de uma esfera em \(\mathbb R^3\) (uma variedade curva). Se, hipoteticamente, essa esfera tivesse raio tendendo a infinito (curvatura tendendo a zero), a região da variedade visitada por um conjunto finito de dados se tornaria aproximadamente um subespaço afim (o plano tangente local).
- □ Como a Hipótese da Variedade afirma que dados de alta dimensão se concentram perto de uma variedade de dimensão intrínseca menor, isso implica que essa variedade é sempre um subespaço vetorial de dimensão reduzida, apenas embutido (mergulhado) em um espaço maior.
- □ Um autoencoder é treinado para comprimir imagens de dígitos manuscritos (como o MNIST, originalmente vetores em \(\mathbb R^{784}\) para imagens \(28\times28\)) em um vetor latente de dimensão \(2\), com reconstrução precisa a partir desse vetor latente. Isso é coerente com a Hipótese da Variedade: os dígitos manuscritos residem próximos a uma variedade de dimensão intrínseca muito menor do que \(784\).
- □ Suponha que uma variedade de dados seja perfeitamente plana (sem curvatura), mas não passe pela origem de \(\mathbb R^d\) — ou seja, seja um subespaço afim deslocado. Nesse caso, a soma de dois pontos quaisquer dessa variedade ainda permanece sobre a própria variedade, pois “ser plana” já garante, por si só, o fechamento sob adição exigido de um subespaço vetorial.
- □ Para um vetor \(\mathbf x=[3,4]^T\in\mathbb R^2\), se generalizarmos para normas \(L_p\), \(\|\mathbf x\|_p=\left(\sum_i|x_i|^p\right)^{1/p}\), o valor \(\|\mathbf x\|_p\) converge para \(\max_i|x_i|=4\) à medida que \(p\to\infty\) — exatamente a definição de \(\|\mathbf x\|_\infty\) dada nesta aula.
- □ As três propriedades que definem uma norma (homogeneidade absoluta, desigualdade triangular, positividade definida) foram enunciadas conjuntamente. Se uma função \(f:\mathbb R^d\to\mathbb R\) satisfizesse a desigualdade triangular e a positividade definida, mas violasse a homogeneidade absoluta (por exemplo, \(f(\lambda x)=\lambda^2\|x\|_2\) em vez de \(|\lambda|\|x\|_2\)), essa função ainda poderia ser chamada de norma, já que as duas propriedades restantes já garantem que ela mede corretamente o “tamanho” de um vetor.
- □ Em regularização de modelos lineares (ex.: Lasso), a penalidade aplicada ao vetor de pesos \(\mathbf w\in\mathbb R^d\) é \(\|\mathbf w\|_1=\sum_{i=1}^d|w_i|\). Substituir essa penalidade por \(\|\mathbf w\|_\infty=\max_i|w_i|\) ainda produziria uma função de penalidade válida do ponto de vista da definição formal de norma, já que \(\|\cdot\|_\infty\) também satisfaz as três propriedades exigidas.
- □ Como as normas \(L_1\) e \(L_2\) induzem bolas unitárias de formatos geometricamente diferentes (losango vs. círculo), um vetor \(\mathbf x\) com \(\|\mathbf x\|_1<\|\mathbf y\|_1\) necessariamente também satisfaz \(\|\mathbf x\|_2<\|\mathbf y\|_2\), para quaisquer \(\mathbf x,\mathbf y\in\mathbb R^d\), já que ambas as normas medem o mesmo conceito subjacente de “tamanho”.
- □ A definição de métrica exige não-negatividade (com \(d(x,y)=0\iff x=y\)), simetria e desigualdade triangular. Se uma função \(\rho:X\times X\to\mathbb R\) satisfizesse não-negatividade e desigualdade triangular, mas fosse assimétrica (\(\rho(x,y)\ne\rho(y,x)\) para alguns pares), ela ainda poderia ser usada para ordenar os vizinhos mais próximos de uma consulta fixa \(\mathbf x_{\text{novo}}\) no \(k\)-NN (fixando sempre o primeiro argumento como a consulta), mesmo não sendo tecnicamente uma métrica válida.
- □ Toda função \(d:X\times X\to\mathbb R\) que satisfaça \(d(x,y)\ge0\) para quaisquer \(x,y\) e \(d(x,x)=0\) já pode ser chamada de métrica, pois não-negatividade e anulação na diagonal são exatamente os dois requisitos que caracterizam completamente o primeiro axioma — os demais axiomas (simetria, desigualdade triangular) seriam apenas propriedades adicionais desejáveis, não obrigatórias.
- □ Em um sistema de busca de imagens, a “distância” entre dois embeddings \(\mathbf u,\mathbf v\in\mathbb R^{512}\) é definida como \(d(\mathbf u,\mathbf v)=\|\mathbf u-\mathbf v\|_2^2\) (a norma Euclidiana ao quadrado, sem a raiz). Essa função ainda satisfaz a desigualdade triangular \(d(u,z)\le d(u,y)+d(y,z)\) para quaisquer \(u,y,z\), herdando essa propriedade diretamente da norma \(L_2\), da mesma forma que \(d(x,y)=\|x-y\|_2\) satisfaz.
- □ A métrica induzida pela norma \(L_\infty\) desta aula, \(d_\infty(\mathbf x,\mathbf y)=\|\mathbf x-\mathbf y\|_\infty=\max_i|x_i-y_i|\), satisfaz automaticamente os três axiomas de métrica, pelo mesmo argumento geral de que toda métrica induzida por uma norma válida herda essas três propriedades da norma que a define.
- □ A “maldição da dimensionalidade” descrita para a distância Euclidiana implica que, em espaços de dimensão muito alta (\(d\gg1000\)), o algoritmo \(k\)-NN deixa de fazer qualquer sentido matemático, pois a distância entre quaisquer dois pontos passa a ser exatamente igual, tornando a operação de ordenação por distância mal definida.
- □ Suponha que, em vez da soma usual de \(d\) termos quadráticos, a norma \(L_2\) fosse recalculada usando apenas duas coordenadas fixas de um vetor de altíssima dimensão (\(d=10\,000\)), ignorando as demais \(9\,998\) coordenadas. Nesse caso reduzido, o fenômeno de perda de contraste descrito para altíssima dimensão deixaria de se manifestar da mesma forma, pois o “colapso” de distâncias é, estruturalmente, um efeito do número de coordenadas somadas na norma, não do rótulo nominal da dimensão do espaço ambiente.
- □ No dataset Breast Cancer Wisconsin (classificação de diagnóstico de tumores a partir de atributos contínuos), os atributos têm escalas bem diferentes — por exemplo,
area_mean na casa das centenas e smoothness_mean na casa dos centésimos. Se o \(k\)-NN for aplicado sobre esses atributos sem nenhum reescalonamento (feature scaling), a distância Euclidiana entre dois pacientes será dominada pelos atributos de maior escala numérica, mesmo que atributos de escala menor sejam igualmente ou mais informativos para o diagnóstico.
- □ No caso particular em que o espaço de características tem dimensão \(d=1\) (uma única variável numérica), a distância Euclidiana \(d_2(x,y)=\|x-y\|_2\) se reduz a \(|x-y|\), e o fenômeno de “colapso de distâncias” descrito para dimensões muito altas não se aplica, pois não há múltiplas coordenadas cujas contribuições possam se diluir estatisticamente.
- □ Suponha, hipoteticamente, que a Desigualdade de Cauchy-Schwarz não fosse válida em \(\mathbb R^n\). Nesse cenário, a prova de não-negatividade de \(d_{\cos}(x,y)=1-\cos\theta\) — que depende de \(|\langle x,y\rangle|\le\|x\|_2\|y\|_2\) para limitar \(\cos\theta\) ao intervalo \([-1,1]\) — deixaria de ser válida como está, exigindo uma justificativa alternativa para garantir \(d_{\cos}(x,y)\ge0\).
- □ Como \(d_{\cos}(x,y)=1-\cos\theta\) satisfaz não-negatividade e simetria (dois dos três axiomas de métrica), e essas duas propriedades já capturam a “essência” do que significa medir distância, \(d_{\cos}\) pode ser tratada como uma métrica válida para todos os efeitos práticos e teóricos, inclusive em provas formais que dependam da desigualdade triangular.
- □ Em um algoritmo de agrupamento hierárquico aglomerativo aplicado a embeddings de texto, um passo do algoritmo depende de uma desigualdade do tipo “distância\((A,C)\le\) distância\((A,B)+\)distância\((B,C)\)” para garantir certas propriedades da árvore de fusões. Se \(d_{\cos}\) for usada diretamente como métrica de distância nesse algoritmo, contando com essa desigualdade, o resultado herda o mesmo risco identificado nesta aula: a garantia pode falhar exatamente pela mesma razão que \(d_{\cos}\) falha o axioma da desigualdade triangular.
- □ No caso extremo em que dois vetores não nulos \(x,y\in\mathbb R^n\setminus\{\mathbf 0\}\) são exatamente paralelos e de mesmo sentido (\(x=cy\) para algum \(c>0\)), a distância do cosseno atinge seu valor mínimo possível, \(d_{\cos}(x,y)=0\) — consistente com o primeiro axioma de métrica, mesmo sendo \(d_{\cos}\), no geral, uma quase-métrica por falhar a desigualdade triangular.