Projeto da disciplina · laboratório

Matriz oculta

No projeto, parte das entradas de uma matriz fica oculta, e o programa da equipe deve estimar essas entradas a partir das conhecidas. Este laboratório mostra cinco estratégias simples para isso. Escolha uma matriz e uma estratégia para ver as entradas ocultas sendo preenchidas e o erro das estimativas. Você também pode preencher as entradas ocultas à mão e comparar o seu erro com o das estratégias, ou rodar um torneio entre elas nas doze matrizes.

valor
oculta
estimada
erro

Erro nas entradas ocultas

Menor é melhor. Como o erro é medido

Estratégia

Você contra as estratégias

Preencha as entradas ocultas à mão, observando a estrutura da matriz, e compare o seu erro com o das cinco estratégias. Comece pelas matrizes menores.

Cinco estratégias

Como cada estratégia estima

Nesta seção, a entrada da linha i e da coluna j da matriz se escreve x_ij. A máscara marca cada entrada como conhecida, quando a estratégia pode usar o seu valor, ou como oculta. As entradas conhecidas passam sem mudança para a estimativa; em cada posição oculta (i, j), a estratégia calcula um valor, que se escreve x̂_ij (lê-se “x chapéu”). A média de todas as entradas conhecidas se chama média global e se escreve μ.

1. Média global

Todas as posições ocultas recebem a média global: x̂_ij = μ. A estimativa não depende da linha nem da coluna da entrada. Esta estratégia serve de referência: as outras só valem a pena quando erram menos do que ela.

função MÉDIA_GLOBAL(observada, máscara)
    μ ← média das entradas conhecidas
    para cada posição oculta (i, j)
        estimativa[i][j] ← μ
    devolva estimativa

2. Média da linha

A média das entradas conhecidas da linha i se escreve m_i; se a linha não tem entrada conhecida, m_i = μ. Cada posição oculta da linha i recebe essa média: x̂_ij = m_i.

A estimativa muda de uma linha para outra, mas, dentro de uma linha, é a mesma em todas as colunas. Por isso, ela acerta todas as entradas ocultas quando, em cada linha, todas as entradas são iguais e pelo menos uma é conhecida, como na matriz Listras.

função MÉDIA_DA_LINHA(observada, máscara)
    μ ← média das entradas conhecidas
    para cada linha i
        m_i ← média das conhecidas da linha i
        ▹ linha sem conhecidas: m_i ← μ
    para cada posição oculta (i, j)
        estimativa[i][j] ← m_i
    devolva estimativa

3. Média da coluna

É a estratégia anterior, com colunas no lugar das linhas. A média das entradas conhecidas da coluna j se escreve c_j; se a coluna não tem entrada conhecida, c_j = μ. Cada posição oculta da coluna j recebe essa média: x̂_ij = c_j.

A estimativa acerta todas as entradas ocultas quando, em cada coluna, todas as entradas são iguais e pelo menos uma é conhecida, como na matriz Colunas.

função MÉDIA_DA_COLUNA(observada, máscara)
    μ ← média das entradas conhecidas
    para cada coluna j
        c_j ← média das conhecidas da coluna j
        ▹ coluna sem conhecidas: c_j ← μ
    para cada posição oculta (i, j)
        estimativa[i][j] ← c_j
    devolva estimativa

4. Efeitos de linha e coluna

Esta estratégia supõe que cada entrada é a média global somada a dois números: um que só depende da linha, chamado de efeito da linha i e escrito α_i, e outro que só depende da coluna, chamado de efeito da coluna j e escrito β_j. A estimativa de cada posição oculta é

\hat{x}_{ij}=\mu+\alpha_i+\beta_j.

Parece natural tomar como efeito da linha i a diferença m_i − μ entre a média da linha e a média global, e fazer o mesmo com as colunas. Isso falha quando há entradas ocultas, porque a média de uma linha depende das colunas em que estão as suas entradas conhecidas. Um exemplo: a matriz tem duas linhas iguais a (1, 5), e só x₁₁ está oculta. A média da linha 1 é 5 e a da linha 2 é 3, embora as linhas sejam iguais, porque a única entrada conhecida da linha 1 está na coluna de valores maiores.

Por isso, os efeitos são calculados juntos: a estratégia procura os valores de α_i e β_j que tornam mínima a soma dos quadrados dos erros nas entradas conhecidas,

S=\sum_{(i,\,j)\ \text{conhecida}}\left(x_{ij}-\mu-\alpha_i-\beta_j\right)^{2}.

No exemplo, o menor valor possível é S = 0, com as duas linhas de mesmo efeito, e a estimativa de x₁₁ é 1, o valor verdadeiro.

A página procura esse mínimo em rodadas. Todos os efeitos começam iguais a zero, e cada rodada tem dois passos:

com os β_j fixos, cada α_i passa a ser a média dos números x_ij − μ − β_j nas entradas conhecidas da linha i;
com os novos α_i fixos, cada β_j passa a ser a média dos números x_ij − μ − α_i nas entradas conhecidas da coluna j.

Os dois passos se apoiam num fato simples: dados k números y₁, …, y_k, o valor de t que torna mínima a soma (y₁ − t)² + ⋯ + (y_k − t)² é a média deles (basta derivar em relação a t e igualar a zero). Assim, cada passo dá o menor S possível enquanto a outra família de efeitos fica fixa, e S nunca aumenta de uma rodada para a seguinte. A página faz 30 rodadas e usa os efeitos da última. Uma linha ou coluna sem entrada conhecida fica com efeito zero.

Na matriz Soma de efeitos, cada entrada é exatamente um número da linha somado a um número da coluna. Nela, o menor valor de S é zero, e a estratégia acerta todas as entradas ocultas do sorteio padrão.

função EFEITOS(observada, máscara, rodadas = 30)
    μ ← média das entradas conhecidas
    α_i ← 0 e β_j ← 0, para todo i e todo j
    repita rodadas vezes
        para cada linha i
            α_i ← média de (x_ij − μ − β_j) nas conhecidas da linha i
        para cada coluna j
            β_j ← média de (x_ij − μ − α_i) nas conhecidas da coluna j
        ▹ linha ou coluna sem conhecidas: o efeito fica 0
    para cada posição oculta (i, j)
        estimativa[i][j] ← μ + α_i + β_j
    devolva estimativa

5. Linhas vizinhas

Esta estratégia estima uma entrada oculta da linha i a partir das linhas mais parecidas com a linha i. Ela usa a média m_r das entradas conhecidas de cada linha r, como na estratégia 2, e o desvio de cada entrada conhecida em relação a essa média: o desvio de x_rj é a diferença x_rj − m_r.

Para comparar a linha i com outra linha r, a estratégia toma as colunas em que as entradas das duas linhas são conhecidas e forma dois vetores: u, com os desvios da linha i nessas colunas, e v, com os desvios da linha r. A semelhança entre as duas linhas é o cosseno do ângulo entre u e v:

s(i,r)=\frac{u^{\mathsf T}v}{\lVert u\rVert\,\lVert v\rVert}.

A semelhança vai de −1 a 1 e vale 1 quando u é um múltiplo positivo de v, isto é, quando os desvios das duas linhas nessas colunas são proporcionais, com constante positiva. Se as duas linhas têm menos de duas colunas conhecidas em comum, ou se u ou v é o vetor nulo, a semelhança é 0.

Para estimar x_ij, a estratégia considera as linhas r ≠ i em que x_rj é conhecida e s(i, r) > 0 e escolhe as 3 de maior semelhança, ou todas, se forem menos de 3. O conjunto das linhas escolhidas se escreve N. A estimativa é a média da linha i somada à média dos desvios dessas linhas na coluna j, ponderada pelas semelhanças:

\hat{x}_{ij}=m_i+\frac{\sum_{r\in N}s(i,r)\,(x_{rj}-m_r)}{\sum_{r\in N}s(i,r)}.

Se N é vazio, x̂_ij = m_i.

função VIZINHAS(observada, máscara, q = 3)
    μ ← média das entradas conhecidas
    para cada linha r
        m_r ← média das conhecidas da linha r
        ▹ linha sem conhecidas: m_r ← μ
    para cada posição oculta (i, j)
        V ← linhas r ≠ i com x_rj conhecida
        para cada r em V
            C ← colunas conhecidas nas linhas i e r
            u ← (x_ik − m_i) e v ← (x_rk − m_r), com k em C
            s(i, r) ← uᵀv / (‖u‖ ‖v‖)
            ▹ s(i, r) ← 0 se C tem menos de 2 colunas
            ▹ ou se u ou v é o vetor nulo
        N ← as q linhas de V de maior s(i, r), entre as de s(i, r) > 0
        se N é vazio então estimativa[i][j] ← m_i
        senão
            estimativa[i][j] ← m_i + Σ s(i, r)(x_rj − m_r) / Σ s(i, r)
            ▹ as duas somas percorrem as linhas r de N
    devolva estimativa

Para a sua equipe

Estas cinco estratégias usam só médias e produtos internos e servem de base de comparação. Nenhuma delas usa o posto da matriz, embora várias das doze matrizes tenham posto baixo: na Tabuada, por exemplo, todas as linhas são múltiplas de uma só. A pesquisa da equipe começa aí, com aproximações de posto baixo, a decomposição em valores singulares ou mínimos quadrados alternados, que aplicam a ideia das rodadas da estratégia 4 para aproximar a matriz pelo produto de uma matriz de poucas colunas por uma matriz de poucas linhas.

Um exercício: rode o torneio com 30% de entradas ocultas e explique por que a média da linha acerta todas as entradas ocultas da matriz Listras e erra no Xadrez, e por que a estratégia das linhas vizinhas erra pouco no Xadrez.

Na apresentação dos projetos (Etapa 2), a equipe explica o próprio algoritmo e responde a perguntas sobre o código.

Erro só nas posições ocultas

Como o erro é medido aqui

Como no torneio do projeto, as duas medidas comparam a estimativa com os valores verdadeiros só nas posições ocultas. Se algo aqui for diferente do guia de regras ou do avaliador da monitoria, liberados em 18/10, valem o guia e o avaliador.

Erro típico

Numa posição oculta (i, j), a estimativa é x̂_ij, e o valor verdadeiro, x_ij; o número de posições ocultas é h. O erro típico é a raiz quadrada da média dos quadrados das diferenças x̂_ij − x_ij:

\text{erro típico}=\sqrt{\frac{1}{h}\sum_{(i,\,j)\ \text{oculta}}\left(\hat{x}_{ij}-x_{ij}\right)^{2}}

Ele fica na unidade da própria matriz: nas notas de 1 a 5, um erro típico de 0,5 corresponde a erros da ordem de meio ponto. Em inglês, é o root mean square error (RMSE), o nome usado no guia de regras.

Erro relativo

O erro relativo é o erro típico dividido pelo desvio-padrão das entradas ocultas verdadeiras, que se escreve σ. Com x̄ para a média dessas entradas,

\text{erro relativo}=\frac{\text{erro típico}}{\sigma}

\sigma=\sqrt{\frac{1}{h}\sum_{(i,\,j)\ \text{oculta}}\left(x_{ij}-\bar{x}\right)^{2}}

Estimar todas as posições ocultas por x̄ dá erro relativo exatamente 1. Nenhuma estratégia pode fazer isso, porque x̄ depende das entradas ocultas, mas a comparação é útil: um erro relativo menor que 1 quer dizer que a estimativa errou menos do que esse valor constante. Como não depende da escala dos números, o erro relativo permite comparar matrizes diferentes, como no torneio. Se todas as entradas ocultas forem iguais, σ = 0, e a página divide o erro típico pela diferença entre o maior e o menor valor da matriz. No guia de regras, as equipes são classificadas pelo RMSE normalizado (NRMSE), o RMSE dividido pelo desvio-padrão: a mesma ideia do erro relativo.

A função do projeto

principal(observada, mascara) recebe a matriz observada e a máscara, que diz quais entradas são conhecidas, e devolve a matriz completa, com as mesmas dimensões. No torneio do projeto, valem a métrica e a normalização do guia de regras, liberado pela monitoria em 18/10.

As posições ocultas

Para cada matriz e cada porcentagem de entradas ocultas, o sorteio padrão é sempre o mesmo, porque o gerador de números aleatórios parte de uma semente fixa. Em todas as matrizes, menos na Coluna inteira oculta, cada linha e cada coluna ficam com pelo menos uma entrada conhecida. O botão “Outro sorteio” escolhe outras posições, e “Sorteio padrão” volta às do sorteio padrão.

As doze matrizes

São pequenas e geradas na própria página, para estudo. As matrizes do torneio do projeto são preparadas pela monitoria e pelo professor.