Álgebra Vetorial e Linear para Computação

Abrir o laboratório do projetoDoze matrizes e cinco estratégias simples, com pseudocódigo, para ver o erro de cada uma, comparar todas no torneio e tentar vencê-las preenchendo à mão.

A ideia

• Muitas tabelas de dados da computação têm entradas faltando: avaliações que ninguém deu, leituras de sensores perdidas, pixels corrompidos. No torneio, cada equipe recebe matrizes assim e escreve uma função que estima as entradas ocultas a partir das conhecidas.
• Preencher cada entrada oculta com a média da sua linha ou da sua coluna já dá uma primeira solução. Para errar menos, a equipe estuda a estrutura da matriz: posto, espaço das colunas, projeções e mínimos quadrados, assuntos desta disciplina, e a decomposição em valores singulares, que não faz parte do programa e fica para a pesquisa da equipe.

Como funciona

• Etapa 1, o código. A equipe escreve um arquivo .py com a função principal(observada, mascara), que recebe a matriz observada e a máscara das posições conhecidas e devolve a matriz completa, com as mesmas dimensões, como numpy.ndarray ou como lista de listas. Para testar e refinar o código, há um lote público de 10 matrizes; o funcionamento e os resultados que valem são os do programa avaliador da monitoria.
• Entrega, até 20/11, às 23:59. Um único arquivo .zip pelo Classroom, com o nome Grupo seguido do número da equipe (por exemplo, Grupo7.zip), contendo o código e um relatório curto que explique o algoritmo. Só um integrante entrega, e ele escreve os nomes da equipe num comentário particular na postagem da entrega.
• Classificação. Depois do prazo, a monitoria roda os códigos num lote privado de matrizes e mede o erro só nas posições ocultas, pelo RMSE normalizado (NRMSE): a raiz do erro quadrático médio dividida pelo desvio-padrão. Quanto menor o erro, melhor a posição. Passam à Etapa 2 as N primeiras equipes, com N calculado pelo número T de equipes inscritas, e outras equipes com entrega válida podem ser sorteadas. Em 29/11, a monitoria divulga no Classroom as classificadas, em ordem numérica; a classificação da Etapa 1 não é divulgada, porque o erro continua como critério central da classificação final.

N = max(3, min(6, ⌈0,4 T⌉))

• Etapa 2, a apresentação, em 03/12. Cada equipe classificada mostra aos monitores, em até 10 minutos, o algoritmo, o código funcionando, uma interpretação dos resultados e o que aprendeu no projeto. Depois, por cerca de 5 minutos, a monitoria pergunta a todos os integrantes sobre o algoritmo e a autoria do código. A ordem das equipes é sorteada no dia, antes da aula. A classificação final e o bônus de cada equipe saem no Classroom em 12/12.

Regras

• Tamanho máximo: 40 linhas e 40 colunas (40 × 40). Esse limite vale para cada dimensão, tanto no lote público quanto no privado. As matrizes podem ser quadradas ou retangulares. O código deve usar as dimensões recebidas em observada.shape.
• Participar é opcional. As equipes têm até três pessoas, de preferência trios, e se inscrevem na planilha da postagem do lançamento até 25/10, às 23:59; o número do campo na planilha é o número da equipe.
• Python, só com NumPy, SciPy, math e random. Bibliotecas de aprendizado de máquina ou de imputação automática, como scikit-learn e PyTorch, são proibidas.
• O avaliador roda o código num ambiente restrito (RestrictedPython): não se pode fixar a semente dos números aleatórios nem definir classes, e as funções auxiliares ficam dentro de principal. O limite é de 2 segundos por matriz e 25 segundos por lote.
• É desclassificada a equipe que não entregar no prazo ou cujo código final devolva uma matriz de dimensões erradas, com NaN ou com valores infinitos, ultrapasse o limite de tempo ou termine com erro.

Bônus na média final

• A equipe campeã ganha 2 pontos. Entre as N finalistas, a equipe na posição P ganha B(P) pontos, valor que cai em passos iguais de 2, na primeira posição, até 0,75, na última:

B(P) = 2,0 − (P − 1) · 1,25/(N − 1)

• Uma equipe que não chega à Etapa 2, mas entrega uma solução válida, ganha 0,5 ponto.

Um esboço do arquivo, na forma pedida pelo guia:

import numpy as np

def principal(observada, mascara):
    # mascara: True onde a entrada
    # de observada é conhecida
    saida = observada.copy()
    ...  # estime as ocultas
    return saida  # mesma forma