Exercícios — Aula 2: Representações Matriciais, Sistemas Lineares e Independência

Álgebra Linear e Otimização para Aprendizado de Máquina

Autor

Prof. Marcos Medeiros Raimundo

Aula Soluções

Convenções usadas nesta lista

\(X\in\mathbb{R}^{N\times d}\) denota uma matriz de design: cada uma das \(N\) linhas é o vetor de atributos de uma observação, cada uma das \(d\) colunas é um atributo medido em todas as observações, e \(\mathbf{w}\in\mathbb{R}^d\) é um vetor de pesos, de modo que \(X\mathbf{w}\in\mathbb{R}^N\) é o vetor de previsões (um número por observação).
O produto \(X\mathbf{w}\) admite duas leituras equivalentes: por linha, cada entrada \(i\) de \(X\mathbf{w}\) é o produto interno \(\mathbf{x}_i^T\mathbf{w}\) entre a \(i\)-ésima observação e os pesos (a previsão daquela observação); por coluna, \(X\mathbf{w}=\sum_{j=1}^d w_j\,\mathbf{x}^{(j)}\) é uma combinação linear das colunas de \(X\) (cada \(\mathbf{x}^{(j)}\in\mathbb{R}^N\) sendo o atributo \(j\) medido em todas as observações), pesada pelas entradas de \(\mathbf{w}\).
Para um sistema \(A\mathbf{x}=\mathbf{b}\), \([A\,|\,\mathbf{b}]\) denota a matriz aumentada (a matriz \(A\) com a coluna \(\mathbf{b}\) acrescentada), e \(\text{rk}(\cdot)\) denota o posto (número de colunas — equivalentemente, de linhas — linearmente independentes) de uma matriz.
Alguns itens usam o California Housing Dataset (preço de imóveis por bairro na Califórnia) como exemplo concreto, com os atributos: MedInc (renda mediana do bairro, em dezenas de milhares de dólares), HouseAge (idade média dos imóveis, em anos), AveRooms (média de cômodos por domicílio) e AveBedrms (média de quartos por domicílio).

Questões discursivas

Explique, com suas próprias palavras, as duas leituras do produto matriz-vetor \(A\mathbf{x}\) (por linha e por coluna, ver convenções acima), e diga qual das duas é mais útil para entender por que uma coluna redundante na matriz de design de um modelo linear não altera as previsões desse modelo.
Sabe-se que o conjunto-solução de um sistema linear homogêneo \(A\mathbf{x}=\mathbf{0}\) é sempre um subespaço vetorial de \(\mathbb{R}^n\) (contém a origem e é fechado sob soma e sob multiplicação por escalar). Explique por que esse resultado não se generaliza para um sistema não homogêneo \(A\mathbf{x}=\mathbf{b}\) com \(\mathbf{b}\ne\mathbf{0}\) — ou seja, por que o conjunto-solução de um sistema não homogêneo, quando existe e não é único, não passa pela origem nem é fechado sob soma.
No California Housing Dataset (ver convenções acima), os atributos AveRooms e AveBedrms têm correlação empírica \(0{,}865\) — forte, mas diferente de \(1\). Explique a diferença entre multicolinearidade exata (uma coluna sendo combinação linear exata de outra, o que reduz o posto da matriz de design) e quase-multicolinearidade (colunas fortemente correlacionadas, mas não exatamente dependentes, o que não reduz o posto). Por que a segunda é mais comum em dados reais do que a primeira?

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).

Teste 1 — A matriz de design

□ Se a matriz de design fosse transposta (linhas = atributos, colunas = observações), o produto que calcula as previsões, \(X\mathbf{w}\), ainda faria sentido dimensional sem qualquer outra mudança na definição de \(\mathbf{w}\in\mathbb{R}^d\).
□ No caso degenerado em que o dataset tem uma única observação (\(N=1\)), a matriz de design \(X\) se reduz a um vetor-linha, e o produto \(X\mathbf{w}\) ainda é bem definido e produz um único número (a previsão daquela observação).
□ Somar a coluna “renda média” com a coluna “número de cômodos” de um dataset produziria um número sem interpretação física direta, ainda que a operação de soma de vetores esteja matematicamente bem definida.
□ Se dois atributos tiverem escalas numéricas muito distintas (ex.: renda em dólares e número de cômodos), isso impede, por si só, que a matriz de design seja usada corretamente num produto matriz-vetor \(X\mathbf{w}\).

Teste 2 — Definição formal de matriz e produto matricial

□ Se \(A\in\mathbb{R}^{m\times n}\) e \(B\in\mathbb{R}^{n\times k}\) com \(k=1\), o produto \(AB\) se reduz exatamente ao produto matriz-vetor \(A\mathbf{x}\), com \(\mathbf{x}=B\) visto como vetor-coluna.
□ Se a matriz de design \(X\) tivesse mais colunas do que linhas (\(d>N\)), o produto \(X\mathbf{w}\) com \(\mathbf{w}\in\mathbb{R}^d\) ainda estaria bem definido e produziria um vetor de previsões em \(\mathbb{R}^N\).
□ Trocar a ordem do produto matriz-vetor, calculando \(\mathbf{w}^T X^T\) em vez de \(X\mathbf{w}\), produz o mesmo conjunto de valores de previsão, ainda que como um vetor-linha em vez de vetor-coluna.
□ Como o produto \(AB\) só está definido quando o número de colunas de \(A\) é igual ao número de linhas de \(B\), isso significa que \(A\mathbf{x}\) e \(\mathbf{x}^TA\) nunca podem estar ambos definidos para a mesma matriz \(A\) e o mesmo vetor \(\mathbf{x}\).

Teste 3 — As duas leituras do produto matriz-vetor

□ Se a matriz \(A\) tivesse todas as suas colunas iguais entre si (idênticas), a leitura “por linha” de \(A\mathbf{x}\) deixaria de ser válida, mas a leitura “por coluna” continuaria válida.
□ No caso em que \(\mathbf{x}\) é o vetor da base canônica \(\mathbf{e}_j\) (uma única entrada igual a \(1\), as demais \(0\)), a leitura “por coluna” de \(A\mathbf{x}\) se reduz exatamente à \(j\)-ésima coluna de \(A\), isolada.
□ As duas leituras do produto matriz-vetor descrevem operações matematicamente diferentes, que apenas coincidem por coincidência numérica.
□ Se \(X\) é uma matriz de design e \(\mathbf{w}\) tem exatamente uma entrada não nula (só o peso de um único atributo), a leitura “por coluna” de \(X\mathbf{w}\) implica que o vetor de previsões é simplesmente um múltiplo escalar da coluna daquele atributo em \(X\).

Teste 4 — Regressão Linear Múltipla como sistema linear

Um modelo de Regressão Linear Múltipla, ajustado por \(N\) observações e \(d\) atributos, corresponde ao sistema linear \(X\mathbf{w}=\mathbf{y}\), em que \(X\in\mathbb{R}^{N\times d}\) é a matriz de design e \(\mathbf{y}\in\mathbb{R}^N\) é o vetor-alvo. Diz-se sobredeterminado quando \(N\gg d\) (muito mais observações do que parâmetros).

□ Se, em vez de \(N\gg d\), tivéssemos \(N=d\) exatamente e a matriz \(X\) tivesse posto completo, o sistema \(X\mathbf{w}=\mathbf{y}\) teria, genericamente, exatamente uma solução — nem sobredeterminado nem subdeterminado.
□ No limite em que \(d=1\) (um único atributo), o sistema \(X\mathbf{w}=\mathbf{y}\) sobredeterminado (\(N\gg 1\)) se reduz a encontrar um único escalar \(w\) que melhor “explica” \(N\) pontos \((x_i,y_i)\).
□ Um sistema sobredeterminado de reconhecimento facial, com muito mais pixels medidos (\(N\)) do que parâmetros de um modelo de regressão a estimar (\(d\)), enfrentaria, genericamente, o mesmo problema de “nenhuma solução exata” que um sistema sobredeterminado de preços de imóveis (muito mais bairros do que atributos).
□ Como um sistema sobredeterminado não tem, genericamente, solução exata, isso implica que a Regressão Linear Múltipla é uma técnica inútil nesse regime.

Teste 5 — As três formas de solução de um sistema linear

□ Existe algum sistema sobredeterminado (mais equações que incógnitas) que tenha, mesmo assim, uma solução exata — não é uma impossibilidade lógica, só um evento não genérico.
□ No caso-limite em que \(m=0\) (sistema sem nenhuma equação), qualquer \(\mathbf{x}\in\mathbb{R}^n\) é, trivialmente, uma “solução” — o sistema tem infinitas soluções por vacuidade.
□ O sistema \(x_1+x_2=4\) e \(2x_1+2x_2=8\) (a segunda equação é a primeira multiplicada por \(2\), logo descreve a mesma reta) tem infinitas soluções, e esse conjunto-solução tem uma propriedade que o distingue do caso homogêneo \(x_1+x_2=0\): ele não passa pela origem, já que \(0+0\ne4\).
□ Um sistema linear real que admitisse exatamente duas soluções distintas \(\mathbf{x}_1\ne\mathbf{x}_2\) teria, na verdade, que ter infinitas soluções — incluindo toda combinação \(\lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2\).

Teste 6 — Sistemas homogêneos vs. não homogêneos

□ Se um sistema homogêneo \(A\mathbf{x}=\mathbf{0}\) tem apenas a solução trivial, então o sistema não homogêneo correspondente \(A\mathbf{x}=\mathbf{b}\), quando tem solução, tem exatamente uma solução (nunca infinitas).
□ No caso em que \(A\) é a matriz nula (\(A=\mathbf{0}\)), o sistema homogêneo \(A\mathbf{x}=\mathbf{0}\) tem \(\mathbb{R}^n\) inteiro como conjunto-solução, e o sistema não homogêneo \(A\mathbf{x}=\mathbf{b}\) com \(\mathbf{b}\ne\mathbf{0}\) não tem solução alguma.
□ O conjunto-solução de um sistema não homogêneo \(A\mathbf{x}=\mathbf{b}\), com \(\mathbf{b}\ne\mathbf{0}\), também é sempre um subespaço vetorial.
□ Se \(\mathbf{x}_1,\mathbf{x}_2\) são duas soluções distintas de \(A\mathbf{x}=\mathbf{b}\) com \(\mathbf{b}\ne\mathbf{0}\), a soma \(\mathbf{x}_1+\mathbf{x}_2\) também é, em geral, solução do mesmo sistema.

Teste 7 — Combinações lineares e independência

□ Se um conjunto de vetores \(\{\mathbf{x}_1,\dots,\mathbf{x}_k\}\) é linearmente dependente, então necessariamente pelo menos um deles pode ser escrito como combinação linear dos demais.
□ Um conjunto formado por um único vetor não nulo, \(\{\mathbf{x}_1\}\) com \(\mathbf{x}_1\ne\mathbf{0}\), é sempre linearmente independente.
□ Se um dos atributos da matriz de design fosse literalmente o vetor nulo (uma coluna de zeros, ex.: um atributo binário que nunca é ativado em nenhuma amostra do dataset), essa coluna, junto com qualquer outra coluna não nula, formaria um conjunto linearmente dependente.
□ Como um conjunto de vetores linearmente independentes “não tem redundância”, isso significa que todo subconjunto de um conjunto linearmente dependente também deve ser linearmente dependente.

Teste 8 — Vetores em excesso e dependência forçada

Considere os vetores \(\mathbf{v}_1=(2,1)\), \(\mathbf{v}_2=(1,3)\) e \(\mathbf{v}_3=(4,9)\) em \(\mathbb{R}^2\), para os quais vale \(\mathbf{v}_3=0{,}6\,\mathbf{v}_1+2{,}8\,\mathbf{v}_2\) — uma combinação não trivial de \(\mathbf{v}_1,\mathbf{v}_2\) que reconstrói \(\mathbf{v}_3\) exatamente, logo os três vetores são linearmente dependentes.

□ Se \(\mathbf{v}_3\) tivesse sido escolhido de forma completamente aleatória (em vez do valor específico \((4,9)\) usado acima), o resultado — dependência linear entre os três vetores — ainda seria garantido.
□ \(d+1\) vetores quaisquer em \(\mathbb{R}^d\) são sempre linearmente dependentes.
□ É possível encontrar 5 vetores linearmente independentes em \(\mathbb{R}^3\).
□ Como o número máximo de vetores linearmente independentes em \(\mathbb{R}^d\) é \(d\), isso implica que qualquer conjunto de exatamente \(d\) vetores em \(\mathbb{R}^d\) é automaticamente linearmente independente.

Teste 9 — Multicolinearidade em atributos de um dataset

Duas colunas de um dataset são ditas exatamente multicolineares quando uma é múltiplo escalar exato da outra — por exemplo, a mesma grandeza física medida em duas unidades diferentes, como “área em m²” e “área em pés²” (relacionadas por um fator de conversão fixo, \(1\text{m}^2\approx10{,}76\text{ pés}^2\)).

□ Se, em vez de “área em m²” e “área em pés²”, tivéssemos “área em m²” e “área em m² mais um ruído de medição aleatório e independente”, essas duas colunas formariam um par exatamente multicolinear (dependência linear exata).
□ No caso em que duas colunas de atributos são idênticas (não só proporcionais, mas exatamente iguais, ex.: o mesmo atributo duplicado por erro de importação de dados), elas são um caso particular de multicolinearidade exata, com fator de proporcionalidade igual a \(1\).
□ Duas colunas de um dataset financeiro, “salário anual” e “salário mensal” (uma sendo exatamente 12 vezes a outra, sem nenhuma variação adicional), formariam um par de colunas multicolineares exatas, pela mesma lógica do exemplo de área em m²/pés².
□ Como medir o mesmo atributo em duas unidades diferentes tipicamente produz colunas multicolineares exatas, isso significa que toda dupla de atributos fisicamente relacionados entre si (não necessariamente a mesma grandeza em unidades diferentes) também deve ser exatamente multicolinear.

Teste 10 — Posto de uma matriz

□ Se uma matriz \(A\in\mathbb{R}^{m\times n}\) tivesse todas as suas \(n\) colunas idênticas entre si (e \(n>1\)), seu posto seria exatamente \(1\), independentemente de \(m\) e \(n\).
□ O posto de uma matriz \(A\in\mathbb{R}^{m\times n}\) nunca pode ser maior que \(\min(m,n)\).
□ Uma matriz de design \(X\in\mathbb{R}^{N\times d}\) com \(N\gg d\) (o regime típico de aprendizado supervisionado com muitas observações e poucos atributos) tem, no melhor caso (posto completo), \(\text{rk}(X)=d\) — nunca \(N\), mesmo com \(N\) muito maior que \(d\).
□ Uma matriz é dita deficiente em posto quando seu posto é maior do que \(\min(m,n)\).

Teste 11 — Posto e solvabilidade de sistemas lineares

□ Se \(\text{rk}(A)\ne\text{rk}([A|\mathbf{b}])\) para um sistema específico, isso implica necessariamente que \(\text{rk}([A|\mathbf{b}]) = \text{rk}(A)+1\), nunca uma diferença maior.
□ No caso em que \(\mathbf{b}=\mathbf{0}\) (sistema homogêneo), \(\text{rk}([A|\mathbf{0}]) = \text{rk}(A)\) sempre, e portanto o critério de solvabilidade é automaticamente satisfeito.
□ Um sistema \(A\mathbf{x}=\mathbf{b}\) em que \(A\) tem posto deficiente, mas \(\mathbf{b}\) está fora do espaço gerado pelas colunas de \(A\), não tem solução, mesmo que \(A\) tenha, tecnicamente, “várias direções redundantes” disponíveis.
□ Como posto deficiente pode indicar multicolinearidade exata, toda vez que um sistema \(A\mathbf{x}=\mathbf{b}\) não tem solução, a causa deve ser posto deficiente de \(A\).

Teste 12 — Multicolinearidade exata vs. quase-multicolinearidade

No California Housing Dataset (ver convenções acima), os atributos AveRooms e AveBedrms têm correlação empírica \(0{,}865\) e a matriz de design formada pelos 4 atributos usuais tem posto completo igual a \(4\).

□ Se a correlação entre AveRooms e AveBedrms fosse exatamente \(1{,}0\) (em vez de \(0{,}865\)), o posto da matriz de design cairia de \(4\) para \(3\).
□ No limite em que a correlação entre dois atributos tende a \(1\) mas nunca a alcança exatamente (ex.: \(0{,}999999\)), o posto da matriz permanece tecnicamente completo, mas o sistema fica numericamente cada vez mais instável.
□ Quase-multicolinearidade pode causar instabilidade numérica no ajuste de um modelo, mesmo sem reduzir tecnicamente o posto da matriz.
□ Dois atributos de um dataset médico, “peso em kg” e “índice de massa corporal (IMC)”, fortemente correlacionados mas não exatamente proporcionais (o IMC depende também da altura), ilustrariam o mesmo tipo de quase-multicolinearidade discutido para AveRooms/AveBedrms, não uma multicolinearidade exata.