Phase 01 - Lesson 14

Normas e Distâncias

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Sua função de distância define o que "similar" significa. Escolha errado e tudo que vêm depois quebra.

Tipo: Construir Linguagem: Python Pré-requisitos: Fase 1, Lições 01 (Intuição de Álgebra Linear), 02 (Vetores, Matrizes e Operações) Tempo: ~90 minutos

Objetivos de Aprendizagem

• Implementar funções de distância L1, L2, cosseno, Mahalanobis, Jaccard e de edição do zero
• Selecionar a métrica de distância apropriada para uma dada tarefa de ML e explicar por que as alternativas falham
• Conectar as normas L1 e L2 a regularização LASSO e Ridge e suas regiões de restrição geométrica
• Demonstrar como o mesmo conjunto de dados produz vizinhos mais próximos diferentes sob métricas diferentes

O Problema

Você tem dois vetores. Talvez sejam embeddings de palavras. Talvez sejam perfis de usuário. Talvez sejam arrays de pixels. Você precisa saber: quao próximos eles estão?

A resposta depende inteiramente de qual função de distância você escolhe. Dois pontos de dados podem ser vizinhos mais próximos sob uma métrica e estar muito distantes sob outra. Seu classificador KNN, seu motor de recomendacao, seu banco de dados vetorial, seu algoritmo de clusterizacao, sua função de loss -- todos dependem dessa escolha. Erre e seu modelo otimiza para a coisa errada.

Não existe melhor distância universal. L2 funciona para dados espaciais. A similaridade de cosseno domina o PLN. Jaccard lida com conjuntos. A distância de edição lida com strings. Mahalanobis leva em conta correlações. Wasserstein move massa de probabilidade. Cada uma codifica uma suposição diferente sobre o que "similar" significa.

Está lição constrói toda função de distância importante do zero, mostra quando cada uma é a ferramenta certa e demonstra como os mesmos dados produzem vizinhos mais próximos completamente diferentes dependendo de qual métrica você usa.

O Conceito

Normas: medindo a magnitude de um vetor

Uma norma mede o "tamanho" de um vetor. Toda função de distância entre dois vetores pode ser escrita como a norma dá diferença deles: d(a, b) = ||a - b||. Então entender normas e entender distâncias.

Norma L1 (distância de Manhattan)

A norma L1 soma os valores absolutos de todos os componentes.

||x||_1 = |x_1| + |x_2| + ... + |x_n|

Ela é chamada de distância de Manhattan porque mede quanto você caminha em uma grade de cidade onde só é possível se mover ao longo dos eixos. Sem diagonais.

Point A = (1, 1)
Point B = (4, 5)

L1 distance = |4-1| + |5-1| = 3 + 4 = 7

On a grid, you walk 3 blocks east and 4 blocks north.

Quando usar L1:

• Dados esparsos de alta dimensão (features de texto, codificacoes one-hot)
• Quando você quer robustez a outliers (uma única diferença enorme não domina)
• Problemas de seleção de features (a regularização L1 promove esparsidade)

Conexao com a regularização L1 (Lasso): adicionar ||w||_1 a sua função de loss penaliza a soma dos valores absolutos dos pesos. Isso empurra pesos pequenos para exatamente zero, realizando seleção automatica de features. A penalidade L1 cria regiões de restrição em formato de diamante no espaço de pesos, e os cantos dos diamantes ficam nos eixos onde alguns pesos são zero.

Conexao com funções de loss: o Erro Absoluto Médio (MAE) é a distância L1 média entre predições e alvos. Ele penaliza todos os erros linearmente, tornando-o robusto a outliers comparado ao MSE.

Norma L2 (distância Euclidiana)

A norma L2 é a distância em linha reta. Raiz quadrada dá soma dos componentes ao quadrado.

||x||_2 = sqrt(x_1^2 + x_2^2 + ... + x_n^2)

Essa é a distância que você aprendeu na aula de geometria. Pitágoras em n dimensões.

Point A = (1, 1)
Point B = (4, 5)

L2 distance = sqrt((4-1)^2 + (5-1)^2) = sqrt(9 + 16) = sqrt(25) = 5.0

The straight line, cutting diagonally through the grid.

Quando usar L2:

• Dados contínuos de baixa a média dimensão
• Quando as escalas das features são comparaveis
• Distâncias fisicas (dados espaciais, leituras de sensores)
• Similaridade de imagens no nível de pixel

Conexao com a regularização L2 (Ridge): adicionar ||w||_2^2 a sua função de loss penaliza pesos grandes. Diferente dá L1, ela não empurra os pesos para zero. Ela encolhe todos os pesos em direção a zero proporcionalmente. A penalidade L2 cria regiões de restrição circulares, então não ha cantos nos eixos. Os pesos ficam pequenos mas raramente exatamente zero.

Conexao com funções de loss: o Erro Quadratico Médio (MSE) é a média das distâncias L2 ao quadrado. Elevar ao quadrado penaliza erros grandes muito mais do que os pequenos.

MAE (L1 loss):  |y - y_hat|         Linear penalty. Robust to outliers.
MSE (L2 loss):  (y - y_hat)^2       Quadratic penalty. Sensitive to outliers.

Normas Lp: a família geral

L1 e L2 são casos especiais dá norma Lp:

||x||_p = (|x_1|^p + |x_2|^p + ... + |x_n|^p)^(1/p)

Valores diferentes de p produzem "bolas unitárias" de formatos diferentes (o conjunto de todos os pontos a distância 1 dá origem):

p=1:    Diamond shape      (corners on axes)
p=2:    Circle/sphere      (the usual round ball)
p=3:    Superellipse       (rounded square)
p=inf:  Square/hypercube   (flat sides along axes)

Norma L-infinito (distância de Chebyshev)

Conforme p se aproxima do infinito, a norma Lp converge para o componente absoluto máximo.

||x||_inf = max(|x_1|, |x_2|, ..., |x_n|)

A distância entre dois pontos e determinada pela única dimensão em que eles mais diferem. Todas as outras dimensões são ignoradas.

Point A = (1, 1)
Point B = (4, 5)

L-inf distance = max(|4-1|, |5-1|) = max(3, 4) = 4

Quando usar L-infinito:

• Quando o desvio de pior caso em qualquer dimensão isolada importa
• Tabuleiros de jogo (um rei no xadrez se move em L-infinito: um passo em qualquer direção custa 1)
• Tolerancias de fabricacao (toda dimensão precisa estar dentro dá especificacao)

Similaridade de Cosseno e Distância de Cosseno

A similaridade de cosseno mede o ângulo entre dois vetores, ignorando suas magnitudes.

cos_sim(a, b) = (a . b) / (||a||_2 * ||b||_2)

Ela varia de -1 (direções opostas) a +1 (mesma direção). Vetores perpendiculares tem similaridade de cosseno 0.

A distância de cosseno a converte em uma distância: cosine_distance = 1 - cosine_similarity. Ela varia de 0 (direção idêntica) a 2 (direção oposta).

a = (1, 0)    b = (1, 1)

cos_sim = (1*1 + 0*1) / (1 * sqrt(2)) = 1/sqrt(2) = 0.707
cos_dist = 1 - 0.707 = 0.293

Por que o cosseno domina o PLN e os embeddings: em texto, o comprimento do documento não deveria afetar a similaridade. Um documento sobre gatos que tem o dobro do comprimento de outro documento sobre gatos ainda deveria ser "similar". A similaridade de cosseno ignora a magnitude (comprimento) e se importa apenas com a direção. Dois documentos com a mesma distribuição de palavras mas comprimentos diferentes apontam na mesma direção e tem similaridade de cosseno 1.0.

Quando usar a similaridade de cosseno:

• Similaridade de texto (vetores TF-IDF, embeddings de palavras, embeddings de sentencas)
• Qualquer dominio onde a magnitude e ruido é a direção e sinal
• Sistemas de recomendacao (vetores de preferência de usuário)
• Busca por embeddings (bancos de dados vetoriais quase sempre usam cosseno ou produto escalar)

Similaridade por Produto Escalar vs Similaridade de Cosseno

O produto escalar de dois vetores e:

a . b = a_1*b_1 + a_2*b_2 + ... + a_n*b_n
      = ||a|| * ||b|| * cos(angle)

A similaridade de cosseno é o produto escalar normalizado por ambas as magnitudes. Quando os dois vetores já estão normalizados a unidade (magnitude = 1), o produto escalar é a similaridade de cosseno são idênticos.

If ||a|| = 1 and ||b|| = 1:
    a . b = cos(angle between a and b)

Quando eles diferem: o produto escalar inclui a informação de magnitude. Um vetor com magnitude maior recebe uma pontuacao de produto escalar mais alta. Isso importa em alguns sistemas de recuperação onde você quer que itens "populares" rankeiem mais alto. A magnitude age como um sinal implicito de qualidade ou importancia.

a = (3, 0)    b = (1, 0)    c = (0, 1)

dot(a, b) = 3     dot(a, c) = 0
cos(a, b) = 1.0   cos(a, c) = 0.0

Both agree on direction, but dot product also reflects magnitude.

Na prática:

• Use a similaridade de cosseno quando você quer pura similaridade direcional
• Use o produto escalar quando as magnitudes carregam informação significativa
• Muitos bancos de dados vetoriais (Pinecone, Weaviate, Qdrant) deixam você escolher entre eles
• Se seus embeddings estão normalizados em L2, a escolha não importa

Distância de Mahalanobis

A distância Euclidiana trata todas as dimensões igualmente. Mas se suas features são correlacionadas ou tem escalas diferentes, a L2 dá resultados enganosos.

A distância de Mahalanobis leva em conta a estrutura de covariância dos dados.

d_M(x, y) = sqrt((x - y)^T * S^(-1) * (x - y))

onde S é a matriz de covariância dos dados.

Intuitivamente: a distância de Mahalanobis primeiro descorrelaciona e normaliza os dados (branqueamento), depois calcula a distância L2 nesse espaço transformado. Se S é a matriz identidade (features descorrelacionadas, variância unitária), a distância de Mahalanobis se reduz a distância Euclidiana.

Example: height and weight are correlated.
Someone 6'2" and 180 lbs is not unusual.
Someone 5'0" and 180 lbs is unusual.

Euclidean distance might say they are equally far from the mean.
Mahalanobis distance correctly identifies the second as an outlier
because it accounts for the height-weight correlation.

Quando usar a distância de Mahalanobis:

• Detecção de outliers (pontos com grande distância de Mahalanobis dá média são outliers)
• Classificacao quando as features tem escalas e correlações diferentes
• Quando você tem dados suficientes para estimar uma matriz de covariância confiável
• Controle de qualidade na fabricacao (monitoramento multivariado de processos)

Similaridade de Jaccard (para conjuntos)

A similaridade de Jaccard mede a sobreposição entre dois conjuntos.

J(A, B) = |A intersect B| / |A union B|

Ela varia de 0 (nenhuma sobreposição) a 1 (conjuntos idênticos). Distância de Jaccard = 1 - similaridade de Jaccard.

A = {cat, dog, fish}
B = {cat, bird, fish, snake}

Intersection = {cat, fish}         size = 2
Union = {cat, dog, fish, bird, snake}  size = 5

Jaccard similarity = 2/5 = 0.4
Jaccard distance = 0.6

Quando usar Jaccard:

• Comparar conjuntos de tags, categorias ou features
• Similaridade de documentos baseada na presença de palavras (não na frequência)
• Detecção de quase-duplicatas (aproximação MinHash de Jaccard)
• Comparar vetores de features binárias (dados de presença/ausência)
• Avaliar modelos de segmentacao (Intersection over Union = Jaccard)

Distância de Edição (Distância de Levenshtein)

A distância de edição conta o número mínimo de operações de um único caractere necessarias para transformar uma string em outra. As operações são: inserir, deletar ou substituir.

"kitten" -> "sitting"

kitten -> sitten  (substitute k -> s)
sitten -> sittin  (substitute e -> i)
sittin -> sitting (insert g)

Edit distance = 3

Calculada usando programação dinamica. Preencha uma matriz onde a entrada (i, j) é a distância de edição entre os primeiros i caracteres dá string A e os primeiros j caracteres dá string B.

        ""  s  i  t  t  i  n  g
    ""   0  1  2  3  4  5  6  7
    k    1  1  2  3  4  5  6  7
    i    2  2  1  2  3  4  5  6
    t    3  3  2  1  2  3  4  5
    t    4  4  3  2  1  2  3  4
    e    5  5  4  3  2  2  3  4
    n    6  6  5  4  3  3  2  3

Quando usar a distância de edição:

• Verificação e correção ortografica
• Alinhamento de sequências de DNA (com operações ponderadas)
• Correspondencia difusa de strings (fuzzy matching)
• Deduplicação de dados de texto bagunçados

Divergência KL (não é uma distância, mas usada como uma)

A divergência KL mede o quanto uma distribuição de probabilidade difere de outra. Coberta na Lição 09, mas pertence a está discussão porque as pessoas a usam como uma "distância" apesar de ela não ser uma.

D_KL(P || Q) = sum(p(x) * log(p(x) / q(x)))

Propriedade crítica: a divergência KL NAO é simétrica.

D_KL(P || Q) != D_KL(Q || P)

Isso significa que ela falha no requisito básico de uma métrica de distância. Ela também não satisfaz a desigualdade triangular. É uma divergência, não uma distância.

A KL direta (D_KL(P || Q)) e "buscadora de média": Q tenta cobrir todos os modos de P. A KL reversa (D_KL(Q || P)) e "buscadora de modo": Q foca em um único modo de P.

Quando você vê a divergência KL:

• VAEs (o termo KL no ELBO empurra a distribuição latente em direção a um prior)
• Destilacao de conhecimento (o aluno tenta imitar a distribuição do professor)
• RLHF (a penalidade KL mantém o modelo ajustado próximo ao modelo base)
• Métodos de gradiente de politica (restringindo atualizações de politica)

Distância de Wasserstein (Distância do Movedor de Terra)

A distância de Wasserstein mede o "trabalho" mínimo necessario para transformar uma distribuição de probabilidade em outra. Pense nela como: se uma distribuição é um monte de terra é a outra é um buraco, quanta terra você tem que mover é a que distância?

W(P, Q) = inf over all transport plans gamma of E[d(x, y)]

Para distribuições 1D, ela se simplifica para a integral dá diferença absoluta das funções de distribuição acumulada:

W_1(P, Q) = integral |CDF_P(x) - CDF_Q(x)| dx

Por que Wasserstein importa:

• É uma métrica verdadeira (simétrica, satisfaz a desigualdade triangular)
• Fornece gradientes mesmo quando as distribuições não se sobrepoem (a divergência KL vai para o infinito)
• Essa propriedade a tornou central para as Wasserstein GANs (WGANs), que resolveram a instabilidade de treinamento das GANs originais

Distributions with no overlap:

P: [1, 0, 0, 0, 0]    Q: [0, 0, 0, 0, 1]

KL divergence: infinity (log of zero)
Wasserstein: 4 (move all mass 4 bins)

Wasserstein gives a meaningful gradient. KL does not.

Quando usar Wasserstein:

• Treinamento de GAN (WGAN, WGAN-GP)
• Comparar distribuições que podem não se sobrepor
• Problemas de transporte ótimo
• Recuperacao de imagens (comparar histogramas de cor)

Por que Tarefas Diferentes Precisam de Distâncias Diferentes

Conexao com Funções de Loss

Funções de loss são funções de distância aplicadas a predições vs alvos.

Loss function       Distance it uses       Behavior
MSE                 L2 squared             Penalizes large errors heavily
MAE                 L1                     Penalizes all errors equally
Huber loss          L1 for large errors,   Best of both: robust to outliers,
                    L2 for small errors    smooth gradient near zero
Cross-entropy       KL divergence          Measures distribution mismatch
Hinge loss          max(0, margin - d)     Only penalizes below margin
Triplet loss        L2 (typically)         Pulls positives close, pushes
                                           negatives away
Contrastive loss    L2                     Similar pairs close, dissimilar
                                           pairs beyond margin

Conexao com Regularização

A regularização adiciona uma penalidade de norma sobre os pesos a função de loss.

L1 regularization (Lasso):   loss + lambda * ||w||_1
  -> Sparse weights. Some weights become exactly zero.
  -> Automatic feature selection.
  -> Solution has corners (non-differentiable at zero).

L2 regularization (Ridge):   loss + lambda * ||w||_2^2
  -> Small weights. All weights shrink toward zero.
  -> No feature selection (nothing goes to exactly zero).
  -> Smooth solution everywhere.

Elastic Net:                  loss + lambda_1 * ||w||_1 + lambda_2 * ||w||_2^2
  -> Combines sparsity of L1 with stability of L2.
  -> Groups of correlated features are kept or dropped together.

Por que L1 produz esparsidade mas L2 não: imagine a região de restrição no espaço de pesos 2D. L1 é um diamante, L2 é um circulo. As curvas de nível dá função de loss (elipses) tem maior probabilidade de tocar o diamante em um canto, onde um peso é zero. Elas tocam o circulo em um ponto suave, onde ambos os pesos são não nulos.

Busca de Vizinhos Mais Proximos

Toda função de distância implica um problema de busca de vizinho mais próximo: dado um ponto de consulta, encontre os pontos mais próximos em um conjunto de dados.

A busca exata de vizinho mais próximo e O(n * d) por consulta em um conjunto de n pontos com d dimensões. Para conjuntos de dados grandes, isso é lento demais.

Algoritmos de Vizinho Mais Proximo Aproximado (ANN) trocam uma pequena quantidade de acurácia por ganhos massivos de velocidade:

Algorithm         Approach                      Used by
KD-trees          Axis-aligned space partition   scikit-learn (low-dim)
Ball trees        Nested hyperspheres            scikit-learn (medium-dim)
LSH               Random hash projections        Near-duplicate detection
HNSW              Hierarchical navigable         FAISS, Qdrant, Weaviate
                  small-world graph
IVF               Inverted file index with       FAISS (billion-scale)
                  cluster-based search
Product quant.    Compress vectors, search       FAISS (memory-constrained)
                  in compressed space

HNSW (Hierarchical Navigable Small World) é o algoritmo dominante nos bancos de dados vetoriais modernos. Ele constrói um grafo de múltiplas camadas onde cada no se conecta a seus vizinhos mais próximos aproximados. A busca comeca na camada do topo (esparsa, saltos longos) e desce até a camada de baixo (densa, saltos curtos).

Construa

Passo 1: Todas as funções de norma e distância

Veja code/distances.py para a implementação completa. Cada função é construída do zero usando apenas matemática básica do Python.

Passo 2: Mesmos dados, distâncias diferentes, vizinhos diferentes

A demo em distances.py cria um conjunto de dados, escolhe um ponto de consulta e mostra como o vizinho mais próximo muda dependendo dá métrica de distância. O ponto que e "o mais próximo" sob L1 pode não ser o mais próximo sob L2 ou cosseno.

Passo 3: Busca de similaridade por embedding

O código inclui uma busca simulada de similaridade por embedding que encontra os "documentos" mais similares a uma consulta usando similaridade de cosseno vs distância L2, mostrando que os rankings podem diferir.

Use

O uso prático mais comum: encontrar itens similares em um banco de dados vetorial.

import numpy as np

def cosine_similarity_matrix(X):
    norms = np.linalg.norm(X, axis=1, keepdims=True)
    norms = np.where(norms == 0, 1, norms)
    X_normalized = X / norms
    return X_normalized @ X_normalized.T

embeddings = np.random.randn(1000, 768)

sim_matrix = cosine_similarity_matrix(embeddings)

query_idx = 0
similarities = sim_matrix[query_idx]
top_k = np.argsort(similarities)[::-1][1:6]
print(f"Top 5 most similar to item 0: {top_k}")
print(f"Similarities: {similarities[top_k]}")

Quando você chama model.encode(text) e depois busca em um banco de dados vetorial, e isso que acontece por baixo dos panos. O modelo de embedding mapeia texto para vetores. O banco de dados vetorial calcula a similaridade de cosseno (ou produto escalar) entre seu vetor de consulta e cada vetor armazenado, usando algoritmos ANN para evitar verificar todos eles.

Exercícios

1. Calcule as distâncias L1, L2 e L-infinito entre (1, 2, 3) e (4, 0, 6). Verifique que L-inf <= L2 <= L1 sempre vale para qualquer par de pontos. Prove por que essa ordenacao e garantida.

2. Crie dois vetores onde a similaridade de cosseno e alta (> 0.9) mas a distância L2 é grande (> 10). Explique geometricamente o que está acontecendo. Depois crie dois vetores onde a similaridade de cosseno e baixa (< 0.3) mas a distância L2 e pequena (< 0.5).

3. Implemente uma função que recebe um conjunto de dados é um ponto de consulta e retorna o vizinho mais próximo sob distância L1, L2, cosseno e Mahalanobis. Encontre um conjunto de dados onde os quatro discordam sobre qual ponto é o mais próximo.

4. Calcule a distância de Wasserstein entre [0.5, 0.5, 0, 0] e [0, 0, 0.5, 0.5] na mao usando o método dá CDF. Depois calcule entre [0.25, 0.25, 0.25, 0.25] e [0, 0, 0.5, 0.5]. Qual é maior e por que?

5. Implemente MinHash para similaridade de Jaccard aproximada. Gere 100 conjuntos aleatórios, calcule o Jaccard exato para todos os pares e compare com a aproximação MinHash usando 50, 100 e 200 funções de hash. Plote o erro de aproximação.

Termos-Chave

Leitura Complementar

• FAISS: A Library for Efficient Similarity Search - a biblioteca dá Meta para busca ANN em escala de bilhões
• Wasserstein GAN (Arjovsky et al., 2017) - o paper que introduziu a distância do movedor de terra nas GANs
• Locality-Sensitive Hashing (Indyk & Motwani, 1998) - algoritmo ANN fundamental
• Efficient Estimation of Word Representations (Mikolov et al., 2013) - Word2Vec, onde a similaridade de cosseno se tornou o padrão para embeddings
• sklearn.neighbors documentation - guia prático de métricas de distância e algoritmos de vizinho no scikit-learn