Caderno de estudo · 23 de novembro de 2026

Inteligência Artificial

Se você faltou às aulas, comece pelo exercício abaixo. Nas primeiras sessões você vai precisar de frações e leitura de tabelas. Os módulos apresentam os outros símbolos conforme entram nas contas.

Primeiros cinco minutos

De 40 alunos que fizeram a lista, 30 passaram. Entre os 20 que não fizeram, 5 passaram. Em P(passar | fez a lista), qual é o grupo depois da barra? Escreva primeiro o denominador, depois a fração.

Conferir a primeira conta

O grupo é quem fez a lista: 40 alunos, não a turma inteira. Desses 40, 30 passaram. A resposta é 30/40 = 3/4.

Agora abra a base de probabilidade. Em cada módulo, refaça o exemplo no papel, tente a pergunta curta sem abrir a resposta e passe ao treino. Deixe as questões longas e os simulados para quando conseguir começar sem olhar a receita.

  • Quarta, 18/11 · Base, Bayes e eliminação: escreva uma conjunta e resolva A-Q1; confira seu posterior por enumeração.
  • Quinta, 19/11 · Amostragem, Naive Bayes e árvores: liste as amostras aceitas, classifique o exemplo de B-Q1 e monte a tabela de ganhos de B-Q4.
  • Sexta, 20/11 · MDP: compare os retornos e preencha duas rodadas de VI e PI.
  • Sábado, 21/11 · Perceptron, redes neurais e simulado 1: registre scores e atualizações; derive os gradientes e corrija o simulado.
  • Domingo, 22/11 · Simulado 2: cronometre e refaça cada erro sem olhar a solução.
  • Segunda, 23/11 · Folha de revisão: de memória, escreva um passo-chave e um erro a evitar por família.

O que cada questão pede

  • A-Q1: escreva uma tabela por variável, some as que não são pedidas nem observadas e obtenha a probabilidade.
  • A-Q2: compare os retornos de duas estratégias para Jim e preencha as tabelas de valor e de política.
  • A-Q3: descubra as dimensões dos pesos que encaixam na rede e calcule duas derivadas.
  • B-Q1: conte exemplos por classe e classifique um dado novo.
  • B-Q2: atualize os pesos do perceptron e decida se alguma reta separa os rótulos.
  • B-Q3: escreva a fórmula da probabilidade e estime-a com as amostras aceitas.
  • B-Q4: compare as divisões para escolher a primeira pergunta da árvore e encontre a pior entre as perguntas binárias.

Módulo 1

Base: probabilidade conjunta, marginal e condicional

Uma tabela permite responder a três perguntas diferentes: quantos casos têm A e B juntos, quantos têm A, e quantos têm A entre os que já têm B. Na terceira pergunta, escolha primeiro o grupo que entra no denominador.

Qual grupo entra no denominador?

Conjunta é a célula: a fração de casos em que duas coisas acontecem juntas. Marginal é a soma da linha ou da coluna: você esquece uma variável somando. Condicional é a célula dividida pela linha (ou coluna) que virou o novo universo — e é por isso que aparece um denominador. Normalizar é dividir um conjunto de massas pela soma delas para que virem probabilidades que somam 1.

Tabela de contingência de 100 alunos: estuda ou não, passa ou não, com marginais nas bordas aluno passa não passa total estudou 45 15 60 não estudou 10 30 40 total 55 45 100 área verde = universo de P(passa | estuda) P(passa) = 55/100 = 0,55 usa a coluna inteira, sem condição
Figura 1.1 — Os mesmos 100 casos respondem a três perguntas: célula (conjunta), linha/coluna (marginal) e célula dividida pela linha (condicional).

Leitura da figura. A célula 45 é a conjunta “estudou e passou”. A coluna 55 é a marginal : somei a coluna e joguei fora a informação “estudou”. A condicional usa só a linha de cima como universo, 45 de 60. Note que 45/60 e 45/55 são frações diferentes com o mesmo numerador: o denominador é a condição.

Símbolos antes das fórmulas

Notação usada em todo o material
SímboloLê-seSignificado operacional
P(A)probabilidade de Afração dos casos em que A acontece
P(A,B)probabilidade conjuntafração em que A e B acontecem juntos (uma célula)
P(A∣B)A dado Bcélula dividida pela linha/coluna de B escolhida como universo
αalfafator de normalização: divide pela soma para o resultado somar 1
Σ, ∏soma, produtoΣ soma os termos indicados (2 + 3 = 5); ∏ multiplica os termos indicados (2 × 3 = 6).
P̂, ≈estimativa, aproximadamenteP̂ é calculada a partir de amostras; 1/3 ≈ 0,333 indica um arredondamento.
√, argmaxraiz quadrada, opção de maior valor√9 = 3. Se A vale 2 e B vale 5, o argmax é B; o máximo é 5.
P(A∣B)=P(A,B)P(B)=P(B∣A)P(A)P(B)

A segunda igualdade é o teorema de Bayes: ela só troca a condicional de lado multiplicando a verossimilhança pelo prior . O denominador é a soma de todas as formas de B acontecer; quando você só precisa comparar hipóteses, ele é o mesmo dos dois lados e pode ser trocado por .

Receita: responder qualquer pergunta de probabilidade em cinco passos

  1. Nomeie as variáveis e os valores ( e para binárias). Sem isso, o denominador é escolhido por acidente.
  2. Decida o que é universo: se a pergunta tem “dado” ou “sabendo que”, o denominador é a massa da condição; se não tem, é a soma de tudo.
  3. Escreva a conjunta como produto de condicionais, da causa para o efeito (regra do produto). Cada termo tem que ser uma entrada de tabela.
  4. Some o que você não quer (marginalize). Somar uma variável é apagá-la da tabela.
  5. Divida pela soma das massas que sobraram para obter probabilidades que somam 1. Confira: frações exatas e soma final igual a 1.

Exemplo resolvido com os mesmos 100 alunos

Perguntas: (i) qual a probabilidade de passar? (ii) e de passar dado que estudou? (iii) e de ter estudado dado que passou? (iv) e de passar dado que não estudou?

Contagens do exemplo (mesmas da figura)
Grupopassanão passatotal
estudou451560
não estudou103040
total5545100
  1. Conjunta (estudou e passou): 9/20 = 45/100.
  2. Marginal passar: 11/20 = (45+10)/100. Somei a coluna inteira; “estudou” desapareceu.
  3. Condicional passar dado que estudou: 3/4 = 45/60. Universo = linha “estudou”.
  4. Condicional invertida ter estudado dado que passou: 9/11 = 45/55. Universo = coluna “passa”. Note 3/4 ≠ 9/11: condicional não é simétrica.
  5. Entre quem não estudou, 10 dos 40 passaram: 10/40 = 1/4. Compare com os 3/4 entre quem estudou. A tabela mostra uma associação; sozinha, não prova a causa.
  6. Conferência das quatro células: 1, porque 45+15+10+30 = 100. Se a soma das células não der o total, a tabela está mal transcrita.

Por que a inversão funciona. Bayes diz = (3/4 · 3/5)/(11/20) = (9/20)/(11/20) = 9/11. A taxa base é o que impede a resposta de ser 3/4.

Erros que custam ponto

  • Trocar o denominador. divide por , não por . Escreva o denominador antes de calcular.
  • Somar condicionais de linhas diferentes como se fossem massas. Só some massas conjuntas; condicionais só somam 1 dentro do mesmo condicionante.
  • Esquecer a taxa base. Verossimilhança alta não significa posterior alta quando a hipótese é rara.
  • Deixar a resposta sem normalizar quando a pergunta pede probabilidade. Produto de fatores não é probabilidade até dividir pela soma.

Fonte: conceito padrão de probabilidade (regra da soma, regra do produto, Bayes); exemplo numérico autoral. Preparação para A-Q1, B-Q1 e B-Q3.

Na prova

A prova A pede em uma rede com cinco variáveis: a mesma pergunta “célula dividida pela condição”, só que a célula precisa ser montada por fatoração. A prova B pede simbolicamente e por amostragem. Comece sempre escrevendo a conjunta e o denominador: A-Q1 · B-Q3.

Antes de resolver: escolha o grupo

De 12 mensagens com link, 3 são spam. Em P(spam | tem link), qual número vai no denominador?

Conferir

12. A condição limita a conta às mensagens com link: 3/12 = 1/4.

Enumeração e fatoração, em três níveis: guiado · nível prova · acima da prova.

Módulo 2

Redes bayesianas: fatorar, ler o grafo e testar independência

Uma rede bayesiana é um desenho econômico de uma tabela gigante. Em vez de listar as 32 linhas de uma conjunta com cinco variáveis binárias, você guarda cinco tabelinhas locais e multiplica. O grafo diz quem entra na condicional de quem; a fatoração diz o que multiplicar.

Uma tabela para cada nó

Cada nó tem uma tabela . O produto dessas tabelas, um termo por nó, é a distribuição conjunta completa. Aresta significa influência direta, não necessariamente causalidade. Independência condicional é uma propriedade do grafo (d-separação) e vale para qualquer parametrização; caminho ativo, porém, só impede garantir independência pela estrutura — parâmetros particulares ainda podem dar independência.

Grafo da prova A: A e C influenciam S, C influencia D, S e D influenciam T; consulta C, evidência T, ocultas A, S e D A C S D T ocultas: A, S, D evidência: T = −t consulta: C
Figura 2.1 — Grafo da prova A (A→S, C→S, C→D, S→T, D→T) com papéis marcados: consulta em amarelo, evidência em azul, ocultas em cinza.

Leitura da figura. O nó amarelo é o que a pergunta quer; o azul é o que se observa; os demais são ocultas e vão ser somadas. Repare que tem dois filhos (S e D) e que tem dois pais (S e D): é exatamente isso que a fatoração precisa registrar.

Com os pais indicados pelo desenho, a conjunta é o produto de cinco termos — não de trinta e um números livres:

P(A,C,S,D,T)=P(A)P(C)P(S∣A,C)P(D∣C)P(T∣S,D)

Contagem de números livres. Binárias: e custam 1 número cada; tem 4 linhas de pais, logo 4 números; custa 2; custa 4. Total 12, contra 31 da conjunta completa. Essa economia é a razão de existir a rede.

Símbolos antes das fórmulas

Vocabulário mínimo de rede bayesiana
TermoDefiniçãoComo aparece na conta
CPTtabela de probabilidade condicional de um nó dados os paisuma linha por combinação de pais; a linha soma 1
raiznó sem paisentra como prior
fatortabela sobre um conjunto de variáveisproduto e soma operam sobre fatores
caminho ativocaminho que transporta dependência dada a evidênciase todos os caminhos estão bloqueados, há d-separação

Receita: atacar qualquer questão de rede

  1. Transcreva as arestas a partir das CPTs (quem é pai de quem). Sem isso, a fatoração sai errada e todo o resto também.
  2. Escreva a fatoração como produto de um termo por nó. É a etapa que a correção procura primeiro.
  3. Marque consulta, evidência e ocultas no grafo. Ocultas são as que serão somadas.
  4. Instancie a evidência nas tabelas: a linha da evidência vira número fixo, não variável.
  5. Escolha o método: enumeração (poucas ocultas), eliminação (muitas), amostragem (rede grande ou pergunta sobre estimativa).
  6. Normalize no fim sobre os valores da consulta.

Exemplo pequeno: duas variáveis, conta completa

Rede de brinquedo: (alarme tocou) e (vizinho saiu de casa), com . Dados: , , . Pergunta: .

  1. Fatoração: .
  2. Marginalizar A para obter o denominador: = 29/40.
  3. Numerador: .
  4. Posterior: = 27/29, isto é, o alarme sobe de para .

Como conferir. Cada CPT soma 1 linha a linha (para cada combinação de pais); a soma de todos os termos da conjunta dá 1; a posterior fica entre 0 e 1 e, em geral, entre o prior e 1. Se a conta não fecha, o erro costuma ser um fator esquecido — em especial o prior de uma raiz.

Independência: cadeia, causa comum e colisor

Três desenhos, três respostas diferentes. A regra de d-separação: um caminho é ativo se não tem colisor observado e nenhum não-colisor observado. Bloqueado em qualquer ponto, o caminho não transporta dependência.

Três estruturas de três nós: cadeia, causa comum e colisor, com o efeito da observação do nó do meio X Y Z X Y Z X Y Z cadeiaobservar Y bloqueia X–Z causa comumobservar Y bloqueia X–Z colisorobservar Y abre X–Z sem Y: dependentes sem Y: dependentes sem Y: independentes Y é o nó do meio: observar (ou não) muda a resposta
Figura 2.2. Observar o nó do meio bloqueia a cadeia e a causa comum, mas abre o caminho pelo colisor.

Na cadeia X → Y → Z e na causa comum X ← Y → Z, observar Y bloqueia o caminho. No colisor X → Y ← Z ocorre o contrário: observar Y, ou um descendente dele, abre o caminho. Pense em duas causas para o mesmo alarme: depois de ouvir o alarme, descobrir uma causa pode diminuir a necessidade de supor a outra.

  • Colisor bloqueia quando nem ele nem descendentes estão observados. Basta um descendente observado para reabrir.
  • Na Prova A, sem evidência, todos os caminhos entre A e C estão bloqueados. Observar S abre A → S ← C. Observar apenas T também abre esse caminho, pois T descende de S, e ainda abre A → S → T ← D ← C. Um caminho aberto não garante dependência.
  • Quando todos os caminhos estão bloqueados, a estrutura garante independência nas condições observadas, para quaisquer parâmetros compatíveis com a rede.
Grafo da prova B: B e D apontam para A, A aponta para C, C e B apontam para E A B D C E evidência na letra (b) pais: A ← {B, D}; C ← {A}; E ← {B, C}
Figura 2.3 — Grafo da prova B (B→A, D→A, A→C, C→E, B→E). Com B e E na consulta, as ocultas são A, C e D.

Erros que custam ponto

  • Fatorar com os filhos no lugar dos pais. O termo é , nunca .
  • Chamar todo caminho de dependência. Verifique colisor e descendentes observados antes de concluir.
  • Esquecer o termo da raiz. É o erro mais comum na prova: a conjunta some com um e o resultado muda.
  • Somar a variável de consulta. Some apenas as ocultas; a consulta sobrevive para a normalização.

Referência: CS188, aulas 13 e 14. Os grafos são das provas A-Q1 e B-Q3.

Na prova

A primeira linha da resposta de qualquer questão de rede deve ser a fatoração. Em A-Q1 ela tem cinco termos; em B-Q3, também cinco, mas com outra topologia. O enunciado de B-Q3(a) pede a equação de enumeração: é fatoração + somas sobre as ocultas.

Antes de calcular: escreva os fatores

Na rede A → B ← C, escreva a conjunta usando um fator por nó.

Conferir

P(A,B,C) = P(A)P(C)P(B|A,C). A e C não têm pais; B tem os dois.

Comece pela fatoração antes de calcular: guiado · nível prova · acima da prova.

Módulo 3

Eliminação de variáveis

Enumeração soma todas as ocultas de uma vez: para ocultas binárias, são produtos por valor da consulta. Eliminação faz a mesma conta uma variável por vez, guardando tabelas intermediárias. O resultado é idêntico; o custo cai porque você reaproveita somas parciais.

A ideia em três frases

Some a variável que aparece em menos fatores primeiro, multiplicando antes só as tabelas que a contêm. Cada soma produz um fator novo, menor. No fim sobra uma tabela sobre a consulta; normalizar sobre ela dá a resposta.

Fluxo da eliminação: fatores iniciais, restrição pela evidência, multiplicação, soma da variável e normalização, com células destacadas fatoresP(C), P(R|C) evidênciaP(+w|R) multiplicah(C,R) soma Rf(C) normaliza f(C)/soma h(C,R) = P(R|C) · P(+w|R) C+r−r +c18/251/50 −c9/502/25 célula somada = 18/25 + 1/50 = 37/50
Figura 3.1 — Eliminação em quatro operações: restringir a evidência, multiplicar as tabelas que compartilham a variável, somar a variável e normalizar. O retângulo verde é a soma que produz uma entrada do fator novo.

Para preencher a célula (+c,+r), procure P(+r|+c) = 4/5 no primeiro fator e P(+w|+r) = 9/10 no segundo. Multiplique: 18/25. Repita para as outras combinações de C e R. Para eliminar R, some as células +r e −r separadamente em cada linha de C.

Símbolos antes das fórmulas

Vocabulário de fatores
TermoDefiniçãoExemplo do módulo
fatortabela indexada por um conjunto de variáveis
produtopara cada combinação de valores, multiplique as entradas compatíveis dos fatoresh(C,R) = P(R|C)·g(R)
somaelimina uma variável somando todas as suas entradas
maior fatorfator intermediário com mais entradas — mede o custoaqui, 4 entradas

Receita: eliminação em cinco passos

  1. Liste os fatores iniciais (um por CPT) e restrinja cada um à evidência: linhas incompatíveis viram zero e podem sair.
  2. Escolha a ordem começando pela variável oculta que aparece em menos fatores. A ordem não muda o resultado, só o custo.
  3. Multiplique os fatores que contêm a variável. Em cada célula, use o mesmo valor de qualquer variável compartilhada. O produto ainda é um fator, não necessariamente uma distribuição que soma 1.
  4. Some a variável do fator resultante. Por que somar: você quer a massa independente do valor dela — é a definição de marginalização.
  5. Repita até sobrar a consulta; normalize dividindo pela soma. Confira com enumeração quando o número de ocultas for pequeno.
As seis etapas desta eliminação, uma por uma (abre também sem JavaScript)
  1. Etapa 1 — fatorar. Rede (chuva, rua molhada, grama molhada): . Consulta ; oculta .
  2. Etapa 2 — restringir a evidência. vira o fator , . A coluna não interessa mais.
  3. Etapa 3 — multiplicar. ; ; ; .
  4. Etapa 4 — somar R. ; .
  5. Etapa 5 — multiplicar o prior de C. ; .
  6. Etapa 6 — normalizar. Soma , logo .

Exemplo resolvido: dois passos, todas as contas

Dados do exemplo (chuva, rua molhada, grama molhada)
Distribuiçãovalores
2/5 e 3/5
4/5 e 1/5
1/5 e 4/5
9/10 e 1/10

Contas, na ordem da figura: = 18/25; = 1/50; = 37/50; = 13/50. Aplicando os priors: = 37/125 e = 39/250. Normalizando: = 74/113, cerca de 0,655. A evidência “grama molhada” subiu a chuva de 0,4 para 0,655.

Confira por enumeração. Some sobre diretamente: . O mesmo número da tabela — sinal de que a ordem e as tabelas intermediárias estão corretas.

Erros que custam ponto

  • Somar antes de multiplicar fatores que compartilham a variável. Você perderia a interação entre eles.
  • Somar a consulta por engano. A variável da pergunta nunca é eliminada.
  • Esquecer o prior de uma raiz que não foi multiplicada em nenhum fator.
  • Dizer que a ordem muda a resposta. Muda o custo (tamanho do maior fator), não o valor.

Referência: CS188, aula 15. O exemplo da chuva é autoral; A-Q1 traz os dados da prova.

Na prova

Em A-Q1, fixe T = −t e use a ordem D, S, A. Ao multiplicar os fatores que contêm D, a tabela sobre C, S e D pode ter 8 entradas. Depois de somar D, sobram 4, indexadas por C e S. A próxima multiplicação volta a 8 entradas sobre A, C e S, antes de somar S.

Antes de somar: encontre as tabelas certas

Em A-Q1, depois de fixar T = −t, quais fatores você precisa combinar antes de somar D?

Conferir

P(D|C) e P(−t|S,D). Os demais não contêm D; deixe-os separados nessa etapa.

guiado · nível prova · acima da prova.

Módulo 4

Amostragem: rejeição e peso de verossimilhança

Amostrar é gerar casos seguindo a rede e contar o que aconteceu. Em vez de somar todas as ocultas, você sorteia valores na ordem topológica (pais antes dos filhos) e usa a frequência como estimativa. Com muitas amostras o erro cai; com poucas, a estimativa pode ficar longe do valor exato — e a prova costuma dar poucas amostras de propósito.

Por que dividir só pelas amostras aceitas?

Para sortear uma amostra, siga as setas: sorteie os pais antes do filho, porque a tabela do filho depende dos valores deles. Na rejeição, descarte as amostras que não batem com a evidência. O denominador conta só as que sobraram. Se a evidência for rara, talvez seja preciso sortear milhares de amostras para obter cem aceitas.

Oito amostras da rede chuva, rua e grama com marcação de aceita ou rejeitada pela evidência grama molhada #amostra (C, R, W)evidência +w?conta?C = +c? 1(+c, +r, +w)sim 2(+c, −r, −w)não 3(−c, +r, +w)sim 4(+c, +r, −w)não 5(−c, −r, −w)não 6(+c, −r, +w)sim 7(−c, +r, +w)sim 8(+c, +r, +w)sim aceitaaceitaaceitaaceitaaceita rejeitarejeitarejeita simnãosimnãosim numerador: amostras aceitas com C = +c → 3 denominador: amostras aceitas → 5     estimativa = 3/5 = 0,6    exato = 74/113 ≈ 0,655
Figura 4.1 — Rejeição passo a passo com oito amostras. As três linhas vermelhas são descartadas porque a evidência é ; o resto forma o universo da estimativa.

Leitura da figura. A contagem de aceitas é o denominador — 5, não 8. Entre as aceitas, conte quantas têm : 3. A estimativa é 3/5 = 0,6, enquanto o valor exato é 0,655: o erro vem do número pequeno de amostras. Se a evidência fosse rara ( em 1 de cada 10 amostras), você precisaria de ~10 vezes mais sorteios para juntar o mesmo número de aceitas.

Símbolos antes das fórmulas

Os três estimadores que aparecem em prova
MétodoFórmulaQuando usar
rejeiçãoevidência comum, poucas variáveis
peso de verossimilhança, evidência rara; não descarta amostras
prior (sem evidência)pergunta marginal

Receita: rejeição em cinco passos

  1. Sorteie os pais antes dos filhos. Essa é uma ordem topológica: se X aponta para Y, sorteie X primeiro. Assim você sabe qual linha da tabela de Y usar.
  2. Sorteie cada nó pela sua CPT, condicionando nos valores já sorteados dos pais.
  3. Compare com a evidência: se algum valor sorteado discorda, descarte a amostra inteira. Por que descartar: você quer a distribuição condicionada à evidência, e essa amostra não pertence a esse universo.
  4. Conte as aceitas (denominador) e, entre elas, as que têm o valor da consulta (numerador).
  5. Divida e reporte que é estimativa. Se nenhuma amostra foi aceita, não existe estimativa — escreva isso, não invente 0.

Exemplo resolvido: as oito amostras da figura

Rede com os mesmos números do módulo de eliminação (, , ). Consulta , agora estimada por rejeição.

  1. Amostras aceitas (coluna ): 1, 3, 6, 7, 8 → 5.
  2. Entre as aceitas, com : 1, 6, 8 → 3.
  3. Estimativa: 3/5 = 0,6.
  4. Valor exato (eliminação): 74/113 ≈ 0,655. O erro absoluto é 0,055; com 5 aceitas isso é normal.

Por que a estimativa não é “errada”. Ela é uma variável aleatória: outra sequência de oito amostras daria outro número. O que se pode afirmar é que o erro esperado diminui com ; o valor exato continua sendo o da eliminação.

Aprofundamento: peso de verossimilhança e por que ele evita o desperdício

Na rejeição, evidência rara destrói quase todas as amostras. No peso de verossimilhança, você não sorteia as variáveis de evidência: fixa o valor observado e multiplica a amostra pelo peso . A estimativa é a média dos pesos, não a contagem simples.

Exemplo: rede , evidência , consulta . Sorteie só : amostras com pesos . Soma dos pesos ; peso das amostras com = ; estimativa ≈ 0,923. O valor exato é ≈ 0,727 — com quatro amostras, o peso ainda erra bastante, mas nenhuma amostra foi descartada.

Em prova, o que se cobra é a definição: pesos iguais à verossimilhança da evidência dados os pais, e divisão pela soma dos pesos. Não confunda com contagem de aceitas.

Erros que custam ponto

  • Dividir pelo total de amostras. O denominador é o número de aceitas.
  • Sortear a evidência e depois “corrigir”. Na rejeição a evidência é filtro; no peso de verossimilhança ela nem é sorteada.
  • Reportar estimativa como valor exato. Escreva “estimativa por amostragem”.
  • Ignorar amostras impossíveis que violam a CPT. Amostra com probabilidade zero não é “azar”: é erro de sorteio.

Referência: CS188, aula 16. Em B-Q3(b), a prova já fornece as amostras.

Na prova

B-Q3(b) dá a lista de amostras pronta: o trabalho é separar as que têm , contar e dividir. Não recalcule a probabilidade exata — a pergunta é sobre o estimador.

Antes de dividir: conte as aceitas

De seis amostras, quatro batem com a evidência. Só uma dessas quatro tem a resposta procurada. Qual fração você escreveria?

Conferir

1/4. As duas descartadas não entram no denominador.

guiado · nível prova · acima da prova.

Módulo 5

Naive Bayes

Naive Bayes classifica com duas ideias simples: a classe se explica pelo prior, e cada atributo contribui com sua própria verossimilhança, como se os atributos fossem independentes dentro da classe. “Naive” é o nome honesto dessa suposição — ela quase nunca é verdadeira, mas costuma classificar bem.

Conte dentro de cada classe

Treinar é contar: e . Classificar é comparar para cada classe. O produto é um escore; para virar probabilidade, divida pela soma dos escores. Se alguma contagem for zero, o produto inteiro zera e a suavização de Laplace entra em cena.

Fluxo do Naive Bayes: contagens por classe, produtos prior vezes verossimilhanças, escores e posterior normalizado contagensS: 2 exemplosN: 4 exemplos prior × verossimilhançasS: 1/3 · 1 · 1/2N: 2/3 · 1/4 · 1/2 escoresS: 1/6N: 1/12 posterior = escore / (soma dos escores) S = 2/3 N = 1/3 (1/6) / (1/6 + 1/12) = (4/24)/(6/24) = 2/3 atributos x1 = 1 e x2 = 0; classe prevista = S, a de maior escore
Figura 5.1 — Do exemplo bruto ao posterior: contar por classe, multiplicar prior e verossimilhanças, comparar escores e normalizar.

Leitura da figura. O escore não é probabilidade: 1/6 e 1/12 não somam 1. Somando-os (3/12) e dividindo cada um pela soma, chega-se a 2/3 e 1/3. Se a pergunta fosse apenas “qual classe?”, a comparação dos escores bastaria — normalizar só é necessário quando se pede a probabilidade.

Símbolos antes das fórmulas

Termos do classificador
SímboloSignificadoComo calcular
prior da classe#(y)/N
verossimilhança do atributo na classe#(x_i ∧ y)/#(y)
produto não normalizado
posteriorescore(y)/Σ escore
Laplacesuavização add-1
P(y∣x1,…,xn)=αP(y)∏i=1nP(xi∣y)

Receita: classificar em cinco passos

  1. Conte as classes (prior) e, dentro de cada classe, cada valor de cada atributo. Monte a tabela de contagens antes de qualquer conta.
  2. Calcule as verossimilhanças dividindo pela contagem da classe — nunca pelo total de exemplos. Por que: a pergunta é “dentro da classe y”.
  3. Multiplique prior e verossimilhanças do novo exemplo em cada classe. Por que multiplicar: é a hipótese de independência condicional aplicada ao produto.
  4. Compare os escores e escolha o maior; empate é empate (declare a convenção, por exemplo a classe de menor índice).
  5. Normalize só se pedirem probabilidade. Se aparecer zero, avise e aplique Laplace; recalcule a decisão, que pode mudar.

Exemplo resolvido: seis e-mails

Atributos: = contém “grátis” (1/0); = contém “reunião” (1/0). Classe: spam, normal. Novo e-mail: , .

Dados de treino (6 exemplos)
#GRclasse
111S
210S
301N
410N
500N
601N
  1. Priors: = 1/3 e = 2/3.
  2. Verossimilhanças na classe S (exemplos 1 e 2): = 1; = 1/2.
  3. Na classe N (exemplos 3 a 6): = 1/4; = 1/2.
  4. Escores: S = = 1/6; N = = 1/12.
  5. Posterior: = 2/3. Classificação: spam, com 2/3 de confiança.

Por que a classe com menos exemplos ganhou. O prior de N é o dobro, mas contra compensa com folga. É exatamente isso que a prova quer que você mostre: escore, não intuição.

Como conferir. Normalize os escores e veja se somam 1; a contagem total de cada classe tem de reproduzir o prior; a soma das contagens de cada atributo dentro da classe tem de dar a contagem da classe. Se um escore zerou, procure a contagem zero antes de concluir “impossível”.

Aprofundamento: zero count, Laplace e log (quando a conta degenera)

Se a classe N não tivesse nenhum exemplo com , então e o escore de N seria 0 — o modelo diria “impossível”, não “improvável”. A suavização de Laplace troca por e todos os denominadores sobem pelo número de valores do atributo.

Ao multiplicar muitas probabilidades positivas muito pequenas, o computador pode arredondar o produto para zero. Some os logaritmos para comparar os escores: log P(y) + Σ log P(xᵢ|y). O log preserva a ordem dos valores positivos, então a classe vencedora não muda. Trate escores exatamente iguais a zero à parte.

Escolhas que não resolvem zero count: reduzir os dados, normalizar as CPTs (elas já somam 1), usar máxima verossimilhança sem suavizar (é a causa do problema).

Erros que custam ponto

  • Dividir a verossimilhança pelo N total. O denominador é a contagem da classe.
  • Escrever o escore como probabilidade. Só depois de normalizar.
  • Ignorar zero count. Um zero anula o produto e a resposta vira 1 ou 0 sem discussão.
  • Esquecer o prior. Sem ele, o classificador deixa de penalizar classes raras.

Referência: CS188, aula 21. A tabela de oito exemplos da prova está em B-Q1.

Na prova

B-Q1 é o formato mínimo: tabela, nova instância, classificação. O enunciado não pede probabilidade, mas apresentar o posterior mostra domínio — e é o que separa “acertei” de “mostrei”.

Antes de multiplicar: escolha a classe

Das oito mensagens, cinco são spam. Três dessas cinco têm link. Escreva P(link | spam).

Conferir

3/5. O denominador é o total da classe spam, não o total de mensagens.

guiado · nível prova · acima da prova.

Módulo 6

MDP: decidir hoje pensando no que vem depois

A pergunta do dia a dia. Você está na fila do RU e vê que a fila do lado anda mais rápido. Trocar de fila agora custa o tempo da troca, mas pode render 10 minutos no futuro. Vale a pena? Um MDP é exatamente a ferramenta para responder isso de forma calculável: você lista os estados possíveis, as ações disponíveis, o que acontece (com qual probabilidade) quando você age, quanto ganha em cada passo e quanto o futuro "vale" para você.

A resposta que o MDP devolve não é um número solto: é uma política, isto é, uma ação recomendada para cada estado, escolhida para maximizar a soma de recompensas descontadas. Na iteração de valor, você atualiza os valores de todos os estados. Na iteração de política, você primeiro avalia uma política e depois decide onde trocar de ação.

Os símbolos, um por um

Antes de qualquer fórmula, fixe o vocabulário. A prova cobra que você declare a convenção usada.

Símbolos usados neste módulo
SímboloNomeLeitura em português
Sestadoso conjunto de situações em que o agente pode estar
A(s)açõeso que se pode fazer estando em s
T(s,a,s′) transiçãoprobabilidade de terminar em s′ depois de fazer a em s
R(s,a)recompensa o que se ganha naquele passo (não é o total)
γdescontoquanto vale hoje uma recompensa de amanhã; 0≤γ<1
πpolíticafunção que diz qual ação tomar em cada estado
Vπ(s)valor da política soma esperada de recompensas descontadas começando em s e seguindo π
Q(s,a)valor da ação o mesmo, mas forçando a primeira ação a ser a

Duas propriedades que a prova explora e que você deve citar:

  • Markov: o futuro só depende do estado atual, não de como você chegou ali — é por isso que T tem apenas três argumentos.
  • Normalização: para cada par (s,a), a soma das probabilidades de todos os destinos é 1. Confira isso na sua tabela antes de calcular valores.

O problema do Jim e da Pam, desenhado

Grade de cinco quadrados do problema de Jim e Pam com recompensas e transições Cinco quadrados numerados de 1 a 5. Jim começa no quadrado 1 e Pam fica no quadrado 5. Cada quadrado tem recompensa 4 elevado ao número do quadrado. A ação andar para a direita leva ao quadrado seguinte com probabilidade p e mantém no mesmo quadrado com probabilidade 1 menos p. A ação descansar mantém no mesmo quadrado com probabilidade 1. 1 2 3 4 5 Jim Pam R = 4 R = 16 R = 64 R = 256 R = 1024 (descansar em s: fica em s, recebe R(s) = 4 elevado a s) pppp 1−p 1−p p → fica em 5 Ação andar (tracejado = fracasso): com prob. p vai para s+1; com prob. 1−p fica em s. No quadrado 5 não há s+1. Horizonte infinito, sem estado terminal: o episódio não acaba, e é por isso que o desconto γ é obrigatório.
Leitura orientada. (1) Os cinco quadrados são os estados; a posição de Pam é fixa, então o estado é só o quadrado de Jim. (2) Cada quadrado tem uma recompensa, que só é recebida quando a ação é descansar. (3) Andar para a direita é uma ação arriscada: dá 0 no passo e pode não funcionar. (4) Quanto mais perto de Pam, maior a recompensa — mas chegar lá custa passos sem recompensa. (5) O desconto γ decide se esse custo compensa; é exatamente a conta que a prova pede.

Jim e Pam: se Jim está na casa s, faltam d = 5 − s passos até Pam. Descansar rende 4s imediatamente e mantém Jim na mesma casa. Mover rende 0, mesmo quando funciona.

Receita 1 — escrever o modelo formal

  1. Liste os estados e escreva o que cada um significa. Se a recompensa depende da distância d, converta: d=5−s implica R(s)=45−d=4s. Por quê: usar 4d diretamente inverte a escala e produz 256 no início.
  2. Liste as ações por estado. Se o enunciado não disser o que ocorre na borda, declare sua convenção. Em Jim e Pam, tratamos mover na casa 5 como permanecer nela com recompensa 0.
  3. Escreva a tabela de transição com as probabilidades somando 1 em cada linha. Por quê: é a checagem mais rápida de erro de transcrição.
  4. Declare a recompensa como R(s,a) ou R(s,a,s′), e diga em que instante ela é paga (no início do passo, com a ação, é a convenção mais comum). Por quê: a mesma política muda de valor se a recompensa for paga um passo depois.
  5. Declare o horizonte e o desconto (infinito? terminal? γ). Por quê: sem γ<1 e sem terminal, a soma pode divergir.
  6. Só então escreva Vπ ou V*.

Retorno é a soma das recompensas de um caminho, com desconto nas futuras. O símbolo 𝔼 indica média ponderada pelas probabilidades dos caminhos. Vπ(s) é essa média partindo de s e seguindo π; V*(s) é o melhor valor possível partindo de s.

Gt= ∑k=0∞ γkR(st+k, π(st+k)) Vπ(s)= 𝔼π[Gt∣ st=s]

Se Jim descansar na casa 1 e γ = 1/2, as parcelas são 4 agora, 2 no passo seguinte, 1 no outro, e assim por diante. Se S = 4 + 2 + 1 + …, então S/2 = 2 + 1 + …; subtraia para obter S/2 = 4, ou S = 8. A mesma subtração dá a fórmula geral:

∑k=0∞ cγk= c1−γ se |γ|<1

Se a primeira recompensa só é recebida no instante 1 (porque no instante 0 você agiu e ganhou 0), multiplique o resultado por γ. Esse é o erro número um de quem decora a fórmula sem pensar.

Receita 2 — iteração de valor (VI)

A ideia: comece achando que todo estado vale 0 e vá corrigindo. Cada rodada usa os valores da rodada anterior para recalcular cada estado, sempre escolhendo a melhor ação — daí o max.

Vk+1(s)= maxa∈A(s) ∑s′ T(s,a,s′) [R(s,a)+ γVk(s′)]
  1. Zere todos os estados: V0(s)=0. Estado terminal fica 0 para sempre e não entra no max.
  2. Para cada estado, calcule o valor de cada ação: recompensa imediata + γ vezes a média dos valores anteriores dos destinos, ponderada por T.
  3. Fique com o maior. Esse é o novo valor do estado. Use somente os valores da rodada anterior (atualização síncrona) — se misturar valores novos, a tabela deixa de corresponder a "iteração k".
  4. Repita até os valores pararem de mudar (ou pelo número de iterações pedido).
  5. No fim, extraia a política: π(s)=argmaxQ*(s,a).

Receita 3 — iteração de política (PI)

Em vez de varrer valores, PI aposta numa política e melhora. Dois passos alternados:

  1. Avaliar a política atual resolvendo as equações de esperança — sem max: V(s)=∑s′ T(s,π(s),s′) [R+γV(s′)].
  2. Melhorar: para cada estado, escolha a ação que maximiza R+γ∑s′TV(s′) com o V que você acabou de calcular.
  3. Se a política não mudou, pare: ela é ótima. Se mudou, volte ao passo 1.

A melhoria não reduz o valor da política. Se uma ação disponível for estritamente melhor, trocá-la melhora o valor em pelo menos um estado. Como há um número finito de políticas determinísticas, mantendo a ação atual nos empates o algoritmo para. No exemplo de Jim e Pam, há no máximo 2⁵ = 32 políticas.

A confusão que mais custa ponto. Avaliação de política não tem max; iteração de valor e melhoria de política têm. Se você colocar max na avaliação, está calculando outra coisa (o valor ótimo), e a conta não fecha com a política pedida.

Segunda confusão: o desconto multiplica o futuro, nunca a recompensa do passo atual. Em R+γVk+1(s′), o γ está só no segundo termo.

Exemplo pequeno, resolvido devagar

Vamos calcular as primeiras rodadas com dois estados: você pode estudar na mesa (M) ou descansar no sofá (S). Estudar na mesa rende 2 por passo e mantém você na mesa. Ir para o sofá descansando não rende nada no passo da mudança, mas descansar no sofá rende 3 por passo. Estudar no sofá (com o notebook no colo) rende 1 e leva de volta à mesa. Desconto γ=12.

Modelo do exemplo: duas ações, dois estados
EstadoAçãoDestino (prob.)Recompensa
M (mesa)estudarM (1,0)2
M (mesa)descansarS (1,0)0
S (sofá)estudarM (1,0)1
S (sofá)descansarS (1,0)3
Passo a passo da iteração de valor neste exemplo (5 etapas)
  1. Etapa 1 — ponto de partida. V0(M)=0 e V0(S)=0. Sem valores futuros, cada estado vale apenas a recompensa imediata da melhor ação.

    V1(M)=max{2+12⋅0,0+12⋅0}=2; V1(S)=max{1,3}=3.

  2. Etapa 2 — o futuro começa a contar. Agora usar V1 como "o que vem depois". Note que o destino depende da ação: descansar em M leva a S, cujo valor é 3.

    V2(M)=max {2+12⋅2, 0+12⋅3}=max{3;1,5}=3

    V2(S)=max {1+12⋅2, 3+12⋅3}=max{2;4,5}=4,5

  3. Etapa 3 — continue. V3(M)=max{2+1,5,0+2,25}=3,5; V3(S)=max{2,5;3+2,25}=5,25. Os valores sobem, mas cada vez menos: o desconto amortece.

  4. Etapa 4 — o limite é a solução exata. Se a política ótima é (estudar em M, descansar em S), as equações de esperança são V(M)=2+12V(M) e V(S)=3+12V(S). Resolvendo cada autorreferência: V(M)= 21−1/2=4 e V(S)= 31−1/2=6.

  5. Etapa 5 — conferir se essa política é mesmo ótima. Em M, descansar valeria 0+12⋅6=3<4. Em S, estudar valeria 1+12⋅4=3<6. Nenhuma troca melhora, então V*=(4;6) e π*=(estudar,descansar).

Iteração de valor no exemplo (síncrona, V0=0)
EstadoV0 V1V2 V3V*
M (mesa)0 2 33,5 4
S (sofá)0 3 9/25,25 6

A coluna V* não sai de "mais uma iteração": sai da solução exata do sistema da política ótima. VI chega perto; PI e a resolução do sistema chegam no valor exato.

Diagrama de retrocesso de Bellman com duas ações e seus sucessores O estado s aparece à esquerda. Duas ações saem dele: descansar, que leva a s com probabilidade 1 e recompensa 4 elevado a s, e andar, que leva a s mais 1 com probabilidade p e a s com probabilidade 1 menos p, com recompensa zero. O valor novo é o máximo entre os dois valores esperados. s descansar andar: p andar: 1−p fica em s R = 4 elevado a s vai para s+1 R = 0, próximo valor V(s+1) fica em s R = 0, próximo valor V(s) valor da ação descansar = 4^s + γ·V(s) valor da ação andar = p·γ·V(s+1) + (1−p)·γ·V(s) V novo (s) = maior dos dois (o max é isso: escolher a ação, não somar as duas)
Este é o desenho que explica a equação de Bellman: cada ação abre um leque de destinos com pesos T. A conta de uma ação é uma média ponderada; o valor do estado é o maior entre as médias das ações. Se você somar as duas ações em vez de tomar o máximo, o resultado perde o sentido (e não é o valor de nenhuma política).

O mesmo exemplo com iteração de política

Passo A — avaliar (sem max)

Política inicial: descansar sempre, π1=(descansar,descansar).

V(M)=0+12V(S)

V(S)=3+12V(S)

Logo V(S)=6 e V(M)=3.

Passo B — melhorar (com argmax)

Em M: estudar dá 2+12⋅3=3,5; descansar dá 0+12⋅6=3 ⇒ estudar.

Em S: estudar dá 1+12⋅3=2,5; descansar dá 3+12⋅6=6 ⇒ descansar.

Nova política π2=(estudar,descansar). Repetindo o passo A com ela, sai (4;6) e a melhoria não muda mais nada ⇒ parou.

As duas metades de PI, lado a lado. O painel A resolve um sistema linear (aqui, duas equações que se resolvem de cabeça); o painel B só compara números já calculados. Note que π1 tem valor 3 em M, mas a política melhorada tem 4: a melhoria é monótona, exatamente como o teorema garante.

Valores publicados neste exemplo, para conferência: Vπ1(M)=3 e Vπ1(S)=6. Na tabela, est significa estudar na mesa (M) e desc significa descansar no sofá (S).

Onde isso aparece na prova

A Questão 2 da Prova A é este mesmo problema com cinco quadrados, Pam no quadrado 5 e R(d)=45−d. O roteiro de resolução é o seguinte, e cada item usa uma receita diferente:

  • Item (a) — comparar duas políticas em s=1 com γ=0,5: use a soma geométrica em cada política e resolva a inequação em p. O critério final é p<13 (empate em 13).
  • Item (b) — mesma comparação com p=1, agora isolando γ: dá γ<14.
  • Item (c): faça duas rodadas de iteração de valor. Em cada rodada, leia apenas os valores da anterior.
  • Item (d) — duas rodadas de PI partindo de π1 (iteração de política): avalie, compare as ações e avalie a nova política.

No item (b), com movimento certo, descansar desde o começo rende 4/(1 − γ). Andar uma vez rende 0 agora e 16 a cada passo seguinte, então vale 16γ/(1 − γ). Para 0 ≤ γ < 1, compare 4 com 16γ: descansar ganha abaixo de 1/4, há empate em 1/4, e andar uma vez ganha acima de 1/4. Essa comparação vale para essas duas políticas.

Erros típicos e como conferir

ErroComo perceber sozinho
Usar 4d em vez de 4s no início (d=4) você obteria 256, mas o enunciado dá R(4)=4
Somar em vez de tomar max entre ações o valor do estado sairia maior que qualquer ação isolada; teste um estado com ação obviamente ruim
Colocar max na avaliação de política a política avaliada deixaria de importar — sinal de que a conta virou VI
Atualizar in-place sem avisar a tabela V1 não bate com nenhuma iteração síncrona
Comparar políticas em estados diferentes escreva "a partir de s=1" na resposta
Ignorar o empate declare o desempate ("mantenho a ação anterior"), senão PI pode ciclar entre políticas empatadas

Três conferências de 30 segundos. (1) Cada linha de T soma 1. (2) Todo V novo é maior ou igual ao anterior quando V0=0 e as recompensas são positivas — se caiu, há erro de sinal. (3) A política final, avaliada, satisfaz V(s)=maxaQ(s,a): trocar qualquer ação isolada não aumenta nada.

Treino em três níveis

Antes da tabela: Jim começa na casa 1, descansa sempre e γ = 1/2. Escreva as três primeiras parcelas do retorno.

Conferir

4 + 2 + 1. A recompensa recebida é 4 em todos os passos; o que muda é o peso de cada parcela.

Aprofundamento — por que VI converge e por que PI melhora

Contração. Defina o operador ℬ por (ℬV)(s)= maxa∑s′T(s,a,s′)[R+γV(s′)]. Para quaisquer dois vetores V e W, ‖ℬV−ℬW‖≤γ‖V−W‖, porque o max não aumenta distâncias e a média ponderada também não. Como γ<1, existe um único ponto fixo (teorema de Banach) e ‖Vk−V*‖≤ γk‖V0−V*‖. Sem γ<1 (ou sem terminal) o fator seria 1 e nada garante convergência.

Melhoria de política. Seja π′ gulosa em relação a Vπ. Então Q(s,π′(s))≥Q(s,π(s))=Vπ(s). Separando o primeiro passo e iterando, Vπ′(s)−Vπ(s)= ∑tγt𝔼π′[Q(st,π′(st))−Vπ(st)]≥0, pois todos os colchetes são não negativos. Se algum for estritamente positivo num estado alcançável, a melhoria é estrita. Com finitas políticas e desempate fixo, PI para.

VI versus PI. VI faz muitas iterações baratas (O(S2A) por iteração); PI faz poucas iterações caras (resolver um sistema |S|×|S|). Na prova, isso justifica a escolha: tabela pedida → VI; "avalie esta política" → sistema linear.

Referência de estudo: CS188 (Berkeley), aulas de MDP e de iteração de valor/política, edição de verão de 2025 — índice do curso. Material complementar, não a fonte da prova. As resoluções desta apostila são didáticas, não gabarito oficial.

Módulo 7

Perceptron: uma reta que aprende com o erro

A pergunta do dia a dia. Você quer aprovar ou reprovar alunos olhando duas notas. Se existir uma reta que deixe todos os aprovados de um lado e todos os reprovados do outro, o perceptron acha essa reta — e a única coisa que ele faz é empurrar a reta para o lado certo cada vez que erra.

O perceptron é o tijolo das redes neurais: um neurônio que calcula uma soma ponderada e compara com zero. Entender por que ele funciona (e quando não funciona) é o que a prova cobra.

Símbolos antes das contas

SímboloSignificadoDetalhe que vale ponto
x=(x1,x2,1) entrada com o termo de viéso 1 no fim é o que permite deslocar a reta
w=(w1,w2,w0) pesosw0 é o viés (bias), não a primeira característica
z=w⊤xescore quanto maior, mais "positivo" o ponto é
y^=sign(z) previsãodeclare o que acontece em z=0
ηtaxa de aprendizadono perceptron clássico costuma ser 1

O que uma atualização faz com a reta

Três painéis com os quatro pontos do exemplo e a reta de decisão antes e depois de cada atualização Painel 1: pesos iniciais menos um, dois, zero; a reta x1 igual a 2 x2. Painel 2: depois da primeira atualização, pesos um, dois, um; a reta passa longe, deixando todos os pontos do lado positivo. Painel 3: depois da segunda atualização, pesos um, menos um, zero; a reta x1 igual a x2 separa os positivos dos negativos. início: w = (−1, 2, 0) (2,0) + (2,1) + (0,3) − (1,3) − x1 = 2·x2; (2,0) fica do lado − ⇒ erro após a 1ª atualização (2,0) + (2,1) + (0,3) − (1,3) − w = (1, 2, 1): todos os z ficam > 0 após a 2ª (= final) (2,0) + (2,1) + (0,3) − (1,3) − w = (1, −1, 0): x1 = x2 separa Azul = rótulo +1; laranja = rótulo −1. Eixos em unidades de x1 (horizontal) e x2 (vertical).
Leitura orientada. No painel da esquerda, a reta inicial erra o ponto (2,0) positivo. A atualização soma yx aos pesos e gira a reta. No painel do meio, o modelo dá escore positivo aos quatro pontos, inclusive aos que têm rótulo negativo. O segundo erro leva à reta x1=x2, que separa os rótulos neste exemplo.

Receita — treinar um perceptron à mão

  1. Declare a convenção: rótulos em {+1,−1} (ou {0,1}), limiar em z>0 (ou ≥0) e o que acontece no empate. Por quê: duas pessoas com convenções diferentes chegam a pesos diferentes e ambas estão certas — desde que declarem.
  2. Monte a tabela com colunas x1, x2, 1, rótulo, e deixe espaço para z, y^, "erro?" e "pesos novos".
  3. Para cada exemplo, calcule z=w1x1+w2x2+w0.
  4. Se acertou, não mexa nos pesos. Se errou, atualize: w←w+ηyx (rótulos ±1) ou w←w+η(y−y^)x (rótulos {0,1}). Por quê: somar yx aumenta o escore do ponto quando ele é positivo e diminui quando é negativo; é o mínimo necessário para consertar aquele erro.
  5. Percorra uma "época" (todos os exemplos na ordem dada) e conte os erros. Se a época terminou com zero erros, os pesos atuais classificam tudo — acabou, e você provou separabilidade mostrando os pesos.
  6. Se ainda há erros, repita a época. Se os erros nunca zeram, isso é indício de não separabilidade — mas indício não é prova: a prova é o sistema de desigualdades impossível (próxima seção).

Exemplo pequeno, resolvido devagar

Quatro pontos, duas características e viés. Convenção declarada: y^=sign(z), empate (z=0) conta como −, η=1, e a atualização é w←w+yx. Pesos iniciais w0=(−1,2,0) (na ordem (w1,w2,w0)).

Uma época completa: quatro pontos, dois erros, duas atualizações
PassoPontoz y^y Erro?Pesos depois
0—————(−1,2,0)
1(2,0) -2−+sim (1,2,1)
2(2,1) 5++não (1,2,1)
3(0,3) 7+−sim (1,−1,0)
4(1,3) -2−−não (1,−1,0)

As contas, sem pular nada. Passo 1: z=−1⋅2+2⋅0+0=−2, previsão −, rótulo + ⇒ erro. Atualização: (−1,2,0)+1⋅(2,0,1)=(1,2,1). Passo 2: z=2+2+1=5 ⇒ acertou, pesos intactos. Passo 3: z=0+6+1=7 ⇒ previu +, era − ⇒ erro; (1,2,1)−1⋅(0,3,1)=(1,−1,0). Passo 4: z=1−3+0=−2 ⇒ acertou.

Fim da época: 2 erros. Nova época com w=(1,−1,0): escores 2, 1, −3, −1 ⇒ 0 erros. Os pesos finais são (1,-1,0) e as margens y⋅z são 2, 1, 3 e 2 — todas positivas, logo a separação é estrita (nenhum ponto em cima da reta).

O que uma época prova — e o que não prova.

  • Época terminou com zero erros ⇒ existe separador: está na sua mão, são os pesos atuais. Isso é prova construtiva de separabilidade.
  • Você rodou várias épocas e sempre houve erro ⇒ não prova nada sozinho. Pode ser só ordem ruim ou número insuficiente de épocas. A prova de não separabilidade é algébrica: suponha um separador e chegue a uma contradição.
  • Se os dados são separáveis e você treina com apresentação cíclica, o perceptron converge (teorema de Novikoff): no máximo (R/γm)2 erros, com R o maior comprimento de vetor de entrada e γm a margem do melhor separador. Se não são separáveis, nenhum η, nenhuma inicialização e nenhuma ordem fazem os erros zerarem.

Como provar que nenhuma reta serve

Pontos da questão de perceptron da prova B, com os positivos alinhados e os negativos dos dois lados Plano cartesiano de zero a cinco. Três pontos positivos alinhados sobre a reta x2 igual a x1 mais um: (1,2), (2,3) e (3,4). Quatro pontos negativos: (1,3) e (2,4) acima dessa reta, (3,1) e (4,1) abaixo. Qualquer reta que deixe os positivos de um lado deixa pelo menos um negativo do mesmo lado. 123 45 123 45 x1x2 x2 = x1 + 1 (1,2) + (2,3) + (3,4) + (1,3) − (2,4) − (3,1) − (4,1) − Os três positivos são colineares: formam um segmento. Os negativos ficam dos dois lados desse segmento. Para separar, a reta teria de deixar todos os + de um lado — mas os − cercam o segmento por cima e por baixo. Nenhuma reta consegue.
Leitura orientada. O desenho não é a prova, mas mostra onde ela nasce: os positivos estão sobre a reta x2=x1+1 e os negativos aparecem dos dois lados dela. Uma reta só divide o plano em duas metades — não consegue "abraçar" um segmento com negativos em cima e embaixo.

A prova formal usa as desigualdades que um separador w=(a,b,c) teria de satisfazer (com c o viés). Para os dados da prova: positivos (3,4),(2,3),(1,2) e negativos (1,3),(4,1),(2,4),(3,1):

  • 2a+3b+c>0 (ponto positivo) e a+3b+c≤0 (ponto negativo) — subtraindo, dá a>0.
  • 2a+3b+c>0 e 2a+4b+c≤0 — subtraindo, dá b<0.
  • 3a+b+c≤0 e a+2b+c>0 — subtraindo, dá 2a−b<0, e com b<0 isso força a<0.
  • Mas a primeira linha dá a>0: contradição. Logo não existe separador.

O passo a passo completo, com a tabela de treinamento real, está na resolução da Questão 2 da Prova B.

Onde isso aparece na prova

A Questão 2 da Prova B dá sete pontos, pesos iniciais e pede (a) uma iteração nos três primeiros exemplos e (b) a discussão sobre existência de pesos que classifiquem tudo. Use a receita acima: tabela de z, decisão, erro e pesos novos. Para o item (b), não basta dizer "testei e não converge": escreva o sistema de desigualdades e mostre a contradição. Esse é o mesmo raciocínio que mostra por que o XOR não é aprendível por um perceptron simples.

Erros típicos e como conferir

ErroComo perceber
Não declarar a convenção de rótulos, limiar ou empatea correção não consegue reproduzir seus pesos
Atualizar quando acertouo peso muda e o escore do ponto já correto fica pior
Trocar a ordem dos pesos(w1,w2,w0) com o viés no fim; escreva isso na folha
Concluir não separabilidade por uma épocarode mais épocas e, principalmente, prove por desigualdades
Dizer que "outro η resolveria"sem separabilidade, o conjunto de erros não zera para nenhum η
Confundir margem com escoremargem é y⋅z; a cota do teorema usa a margem geométrica (distância)

Conferência rápida: depois de treinar, calcule y⋅z para todos os pontos. Se todos forem positivos, você tem um separador válido e a conta está coerente. Se algum for zero, o ponto está na fronteira: a convenção de empate decide o destino dele — e isso precisa estar escrito na resposta.

Treino em três níveis

Antes de treinar, faça uma atualização isolada: w = (0,0,0), x = (2,1), rótulo +1, η = 1 e empate como negativo. Qual é o novo w?

Conferir

O escore é zero, portanto a previsão é negativa. Houve erro. Some (2,1,1), incluindo o 1 do viés: o novo w é (2,1,1).

Referência de estudo: CS188 (Berkeley), aula de perceptron, edição de verão de 2025 — índice do curso. Material complementar; resoluções didáticas, não gabarito oficial.

Módulo 8

Redes neurais: quem errou, e por quanto?

A pergunta do dia a dia. Uma rede neural é uma pilha de contas simples: multiplica por pesos, soma, aplica uma função e repete. O difícil não é a conta — é descobrir, depois de errar a previsão, quanto cada peso contribuiu para o erro. Isso é o gradiente, e o algoritmo que o calcula de trás para frente é o backpropagation.

Na prova, isso aparece em duas perguntas: (a) quais são as dimensões de cada matriz e (b) quais são as derivadas, sem deixar a derivada da ativação "escondida" na resposta. Ambas se resolvem com a mesma disciplina: escrever a cadeia de operações e seguir as dimensões.

Símbolos e a arquitetura da prova

A arquitetura é a da Questão 3 da Prova A: entrada x∈ℝd, uma camada escondida com ativação quadrática g(z)=z⊙z (quadrado componente a componente) e saída escalar. Sem funções de ativação "de biblioteca": aqui é só o quadrado.

z=W1x, y^=W2⊤g(z), ℒ=12(y−y^)2
Contabilidade de dimensões — o item (a) da prova é exatamente esta tabela
GrandezaFormaPor que
xd×1dado do problema: d características
W1n1×n2 para W1x existir, o número de colunas tem de ser d
zn1×1(n1×n2)(d×1) com n2=d
g(z)mesma de zativação elemento a elemento não muda a forma
W2k×1 W2⊤ é 1×k; para o produto dar escalar, g(z) precisa ter k entradas
y^,ℒescalaresa saída é um número real

Conclusão que a prova quer, em uma linha: n1=k (número de neurônios escondidos, igual ao número de pesos de saída) e n2=d (dimensão da entrada). Note que W1 é k×d, e não d×k: é a ordem que faz o produto existir.

Receita 1 — ida (forward)

Fluxo de ida da rede: entrada, produto por W1, quadrado componente a componente, produto por W2 e perda Caixas em sequência: x com duas componentes, z igual a W1 x com duas componentes, g de z com os quadrados, y chapéu como produto interno com W2 e perda como metade do quadrado da diferença. Cada seta mostra a dimensão do que passa. x (1, 2) d × 1 = 2 × 1 z = W1 x (3, 2) k × 1 = 2 × 1 g(z) = z ⊙ z (9, 4) mesma forma ŷ = W2ᵀ g(z) 1 escalar ℒ 2 escalar Valores do exemplo: W1 = [[1,1],[0,1]], W2 = (1, −2), x = (1,2), y = 3. Nenhuma etapa muda a forma, exceto a última: o produto interno transforma vetor em número. A ativação quadrática é aplicada componente a componente — não é produto interno.
Leitura orientada. Siga as formas da esquerda para a direita: a matriz W1 "achata" a entrada de d para k valores; a ativação quadrática só eleva cada um ao quadrado; e W2 combina esses k números em um único escore. A perda é a distância ao quadrado entre esse escore e o valor verdadeiro y.
  1. Verifique as formas antes de multiplicar. W1 é k×d, então W1x é k×1. Por quê: 90% dos erros de conta em prova vêm de multiplicar matrizes incompatíveis.
  2. Aplique a ativação componente a componente: g(z)=z⊙z eleva cada entrada ao quadrado. Por quê: a derivada dessa etapa será 2z, e é aí que a maioria deixa g′ na resposta.
  3. Calcule a saída como produto interno: y^=W2⊤g(z).
  4. Calcule a perda e, de brinde, o "erro assinado" δ=y^−y. Por quê: δ aparece em todos os gradientes; calculá-lo uma vez economiza contas e reduz erro de sinal.

Primeiro uma derivada escalar, depois a matricial

Rede minúscula: x=3, w1=2, z=w1x, g(z)=z2, y^=w2g(z) com w2=13, e y=20.

  1. Ida: z=2⋅3=6, g=36, y^=363=12, ℒ=12(20−12)2=32.
  2. Erro assinado: δ=y^−y=-8. Negativo porque a previsão ficou abaixo do alvo — e o gradiente vai empurrar os pesos para aumentar y^.
  3. Gradiente do peso de saída: ∂ℒ∂w2=δ⋅g(z)=−8⋅36=-288.
  4. Gradiente na entrada da ativação: ∂ℒ∂z=δ⋅w2⋅g′(z)=−8⋅13⋅12=-32. Aqui g′(z)=2z=12 já foi substituída: era isso que o enunciado proibia deixar simbólico.
  5. Gradiente do peso de entrada: ∂ℒ∂w1=∂ℒ∂z⋅∂z∂w1=−32⋅3=-96.
  6. Gradiente na entrada (para propagar a outra camada): ∂ℒ∂x=∂ℒ∂z⋅w1=−32⋅2=-64.

Conferência por diferenças finitas (o teste que você pode fazer na calculadora): aumentando w1 em 0,001 e diminuindo na mesma quantidade, a razão (ℒ(w1+ε)−ℒ(w1−ε))/(2ε) vale -96.0000, praticamente o gradiente exato −96. Se a sua conta de backprop discordar disso, a conta está errada.

Receita 2 — volta (backprop)

Fluxo reverso com os valores numéricos dos gradientes em cada etapa Da perda volta o erro assinado menos dois; o gradiente em W2 é menos dezoito e menos oito; o gradiente em z é menos doze e dezesseis; o gradiente em x é menos doze e quatro; e o gradiente em W1 é uma matriz dois por dois com menos doze, menos vinte e quatro, dezesseis e trinta e dois. ℒ = 2 δ = ŷ − y = −2 ∂ℒ/∂W2 (−18, −8) = δ · g(z) ∂ℒ/∂z (−12, 16) = 2δ · (W2 ⊙ z) ∂ℒ/∂x (−12, 4) = W1ᵀ · ∂ℒ/∂z ∂ℒ/∂W1 (−12, −24 ; 16, 32) = (∂ℒ/∂z) · xᵀ x = (1, 2) z = W1 x = (3, 2) g(z) = (9, 4) δ desce × g(z)
Leitura orientada. O gradiente da saída é o ponto de partida (δ) e cada seta aplica uma regra: multiplicar pela ativação para achar o gradiente de W2; multiplicar por 2z e por W2 para voltar a z; multiplicar por W1⊤ para chegar em x. Cada gradiente tem a forma da grandeza que ele afeta: vetor para x, matriz para W1. Se a forma não bate, a conta está errada.

As quatro regras, com o motivo de cada uma:

∂ℒ∂W2 =δ⋅g(z) ∂ℒ∂z= δ⊙(W2⊙g′(z))
∂ℒ∂x= W1⊤ ∂ℒ∂z ∂ℒ∂W1= ∂ℒ∂z x⊤
  1. δ=y^−y: derivada da perda em relação à previsão. Por quê: 12(y−y^)2 derivada em y^ dá y^−y (o ½ cancela o 2).
  2. W2 "vê" g(z): o gradiente é δg(z). Por quê: y^=∑jW2,jgj, então a derivada em W2,j é δgj.
  3. Volte por z: cada componente recebe δW2,jg′(zj). Para a ativação quadrática, g′(zj)=2zj — substitua, não deixe símbolo. Por quê: é a regra da cadeia, e o fator 2 vem do expoente 2 da ativação.
  4. Chegue em x com W1⊤ e em W1 com o produto externo (∂ℒ/∂z)x⊤. Por quê: W1 é k×d; o produto externo de um vetor k por um vetor d tem exatamente essa forma.

Exemplo vetorial resolvido

Mesma arquitetura, com d=k=2, W1=[[1,1],[0,1]], W2=(1,−2), x=(1,2), y=3. O enunciado não inclui viés. Em outra rede, se você representar o viés anexando 1 à entrada, a matriz da primeira camada teria d + 1 colunas. Nesta questão, a entrada continua com d componentes.

Ver todas as contas do exemplo vetorial
  1. Ida: z=(1⋅1+1⋅2,0⋅1+1⋅2)=(3,2); g(z)=(9,4); y^=1⋅9−2⋅4=1; ℒ=12(3−1)2=2.
  2. Erro: δ=1−3=-2.
  3. Saída: ∂ℒ/∂W2=δg(z)=(-18,-8).
  4. Camada escondida: ∂ℒ/∂z=2δ(W2⊙z)=−4⋅(1⋅3,−2⋅2)=(-12,16).
  5. Entrada: ∂ℒ/∂x=W1⊤(−12,16)=(-12,4).
  6. Pesos da primeira camada: ∂ℒ/∂W1=(∂ℒ/∂z)x⊤= [[-12,-24],[16,32]].
  7. Teste de descida: atualize só W₂, mantendo W₁ fixo, com η=0,01: W2←(1,−2)−0,01⋅(−18,−8)=(59/50,-48/25). Recalculando, y^=147/50 e ℒ=0.0018, menor que 2: a perda caiu.

A fórmula geral que a prova pede

Com g(z)=z⊙z, a derivada da ativação é g′(z)=2z. Substituindo nas quatro regras e escrevendo tudo com as grandezas que o enunciado permite:

∂ℒ∂W2= (y^−y)⊙g(z) =(y^−y)⊙(z⊙z)
∂ℒ∂x= 2(y^−y) W1⊤ (W2⊙z)

Em coordenadas, para quem preferir sem matrizes:

∂ℒ∂xi= 2(y^−y) ∑j=1k W2,jzj W1,ji com z=W1x

Note que nenhuma das duas expressões contém g′: a derivada 2z já foi absorvida. Era exatamente isso que o enunciado exigia — deixar g′(z) simbólico conta como resposta incompleta.

Onde isso aparece na prova

A Questão 3 da Prova A dá W1∈ℝn1×n2 e W2∈ℝk e pede: (a) n1 e n2 em termos de k e d; (b) ∂ℒ/∂W2 e ∂ℒ/∂x sem deixar a ativação. O roteiro: (1) escreva a cadeia de formas — isso resolve (a) sem conta; (2) derive de trás para frente, substituindo g′(z)=2z — isso resolve (b).

Erros típicos e como conferir

ErroComo detectar antes de entregar
Deixar g′ na respostao enunciado proíbe; substitua por 2z
Trocar W1⊤ por W1a forma de ∂ℒ/∂x precisa ser d×1
Esquecer o fator 2 da ativação quadráticadiferenças finitas denunciam imediatamente
Inverter o sinal de δδ=y^−y; com y^<y, δ<0
Dizer que n2=kteste com números: W1 é k×d, então n2=d
Usar η grande e concluir que "desceu" sem conferirrecalcule ℒ depois do passo; se subiu, o passo foi grande

Conferência em três linhas: (1) cada gradiente tem a forma da grandeza; (2) todas as derivadas compartilham o mesmo δ; (3) um passo pequeno na direção oposta ao gradiente reduz a perda.

Treino em três níveis

Antes de voltar pela rede: se a previsão é 2 e o alvo é 5, escreva o erro assinado δ usado na derivada da perda.

Conferir

δ = previsão − alvo = 2 − 5 = −3. Esse sinal precisa chegar aos gradientes.

Aprofundamento — o que essa arquitetura consegue representar

Como g(z)=z⊙z, cada unidade escondida contribui com W2,i(W1,i⋅x)2, isto é, uma forma quadrática em x. Somando, a saída é y^(x)=x⊤Mx com M=∑iW2,iW1,i⋅⊤W1,i⋅ (simétrica, de posto no máximo k). Consequências que valem ponto numa discussão:

  • Sem viés e sem termo linear, a rede não representa 2x1+1 nem uma constante diferente de zero (com x=0, a saída é sempre 0).
  • Representa bem funções quadráticas — inclusive 2x12.
  • Se W1=0, então z=0, g′(0)=0 e ∂ℒ/∂W1=0: o treinamento fica parado nesse ponto. É a versão "quadrática" do neurônio morto.

Referência de estudo: CS188 (Berkeley), aulas de perceptron e de redes neurais, edição de verão de 2025 — índice do curso. Material complementar; resoluções didáticas, não gabarito oficial.

Módulo 9

Árvores de decisão e ganho de informação

Uma árvore de decisão é uma sequência de perguntas sobre atributos. A pergunta da raiz deve ser a que mais reduz a mistura de classes. “Mistura” se mede por entropia, em bits; a redução é o ganho de informação. Escolher o atributo é comparar ganhos — não é opinião.

O que muda quando separam os exemplos?

Entropia mede incerteza: 0 quando a folha é pura, 1 bit quando há duas classes meio a meio. O ganho de informação é , com pesos pelas proporções dos ramos. O melhor atributo é o de maior ganho. Empate é empate: declare o critério de desempate em vez de escolher por gosto.

Comparação de dois atributos candidatos: antes cinco exemplos, três sim e dois não; depois das divisões por clima e por vento com entropias antes: 3 sim, 2 não sim 3/5 não 2/5 H = 0,970951 bit clima sol3 casos: 1 sim, 2 nãoH = 0,918 chuva2 casos: 2 simH = 0 resto = (3/5)(0,918) = 0,551 ganho = 0,420 vento fraco3 casos: 2 sim, 1 nãoH = 0,918 forte2 casos: 1 sim, 1 nãoH = 1,000 resto = 0,551 + (2/5)(1) = 0,951 ganho = 0,020 decisão clima separa 0,420 vento separa 0,020 raiz = clima
Figura 6.1 — Dois atributos candidatos avaliados no mesmo conjunto. O ganho é a entropia antes menos a média ponderada das entropias dos ramos.

Leitura da figura. A barra da esquerda é a mistura inicial. Cada atributo reparte os cinco exemplos em ramos; a entropia de cada ramo é ponderada pela fração de exemplos que caíram nele. Clima deixa um ramo puro (chuva) e o outro com 1 sim e 2 não, resultando em 0,420 bit de ganho; vento quase não muda nada (0,020). Por isso clima vai para a raiz.

Símbolos antes das fórmulas

Notação de árvores
SímboloSignificadoUnidade
entropia da distribuição de classesbits
entropia média depois de dividir por Abits
bits
peso do ramo vadimensional
H(S)=−∑c∈Cpclog2pc,Ganho(A)=H(S)−∑v∈valores(A)|Sv||S|H(Sv)

Receita: escolher a raiz em cinco passos

Em log₂(1/2) = −1, o logaritmo pergunta quanto vale o expoente de 2 para chegar a 1/2: 2−1 = 1/2. Com duas classes meio a meio, cada termo da entropia vale −(1/2)(−1) = 1/2; a soma vale 1 bit.

  1. Conte a coluna alvo e calcule . Sem esse número você não tem contra o que comparar.
  2. Para cada atributo, monte os ramos e conte sim/não dentro de cada ramo. Proporção, não contagem bruta, é o que entra na fórmula.
  3. Calcule a entropia de cada ramo (0 se puro, 1 se meio a meio) e faça a média ponderada pelo tamanho do ramo. Por que ponderar: um ramo com um exemplo não pode valer o mesmo que um com cinco.
  4. Subtraia de para obter o ganho de cada atributo candidato.
  5. Escolha o maior ganho e justifique com os números; se houver empate, diga que há empate e qual critério usa (ordem alfabética, menor número de valores, ganho de razão).

Exemplo resolvido: cinco dias, dois atributos

Dados de treino do exemplo
#climaventojogar
1solfracosim
2solfortenão
3chuvafracosim
4chuvafortesim
5solfraconão
  1. Antes: 3 sim, 2 não → = 0.970951.
  2. Clima: sol tem 3 casos (1 sim, 2 não) → 0,918296; chuva tem 2 casos (2 sim) → 0. Resto = (3/5)(0,918296) + (2/5)(0) = 0,550978. Ganho = 0,970951 − 0,550978 = 0.419973.
  3. Vento: fraco tem 3 casos (2 sim, 1 não) → 0,918296; forte tem 2 casos (1 sim, 1 não) → 1. Resto = (3/5)(0,918296) + (2/5)(1) = 0,950978. Ganho = 0.019973.
  4. Decisão: clima (0,420 contra 0,020). Vento é quase inútil: dividir por ele reproduz a mistura original.

Por que entropia mede mistura. Se todos os exemplos têm a mesma classe, não há pergunta a fazer: 0 bit. Se metade é sim e metade não, qualquer palpite acerta 50%: 1 bit para duas classes. A unidade é bit porque o logaritmo é base 2 — e a prova cobra a unidade.

Como conferir. O ganho nunca é negativo nem maior que ; a soma dos pesos dos ramos é 1; um atributo que não divide o conjunto tem ganho 0; e uma divisão perfeitamente pura dá ganho exatamente igual a .

Erros que custam ponto

  • Média simples das entropias dos ramos. Precisa ser ponderada pelo tamanho de cada ramo.
  • Comparar contagens em vez de ganhos. Um atributo com muitos valores parece melhor só por ter mais ramos: é o viés do ganho de informação.
  • Esquecer a unidade (bits) e o valor de .
  • Escolher no empate sem dizer o critério. A correção procura a justificativa.

Referência: CS188, aula 24. O exemplo de clima e vento é autoral.

Na prova

B-Q4 pede “qual atributo seria o melhor para a raiz” e “qual atributo binário seria a pior escolha”, ambos com justificativa detalhada. A resposta completa tem , o ganho de todos os atributos e a comparação explícita.

Para a segunda pergunta, marque os atributos de duas opções antes de comparar os ganhos. Se dois atributos binários deram 0,02 bit e um atributo de três opções deu 0,01 bit, os dois binários empatam como piores: o de três opções fica fora dessa comparação.

Antes de calcular a entropia

Um ramo tem dois exemplos, ambos da classe sim. Qual é sua entropia?

Conferir

0 bit. Dentro desse ramo, a classe já é conhecida.

guiado · nível prova · acima da prova.

Provas fornecidas

Enunciados originais transcritos. As soluções são didáticas, não oficiais.

Prova A

Prova A · Questão 1 · Documento sem título.pdf, página física 1

Rede de Bayes de Miles — por eliminação de variáveis

Enunciado transcrito. “Miles está curioso sobre a probabilidade de chegar à escola na hora certa. Os fatores que influenciam sua chegada à escola na hora certa podem ser representados pela seguinte rede (assuma valores binários).” Variáveis: = conjunto de alarmes; = dorme demais; = papai está atrasado; = combate ao crime na noite; = chega na hora. Arestas da figura: . Pedido: “Calcule P(C=+c / T=−t) usando eliminação de variáveis.”

P(S | A, C) — transcrita da prova
ACSP(S | A,C)
+a+c+s11/16
+a+c−s5/16
+a−c+s1/8
+a−c−s7/8
−a+c+s9/10
−a+c−s1/10
−a−c+s1/5
−a−c−s4/5
P(T | S, D) — transcrita da prova
TDSP(T | S,D)
+t+d+s1/20
+t+d−s2/5
+t−d+s1/5
+t−d−s1
−t+d+s19/20
−t+d−s3/5
−t−d+s4/5
−t−d−s0
P(D | C) — terceira tabela impressa na prova
CDP(D | C)
+c+d1/4
+c−d3/4
−c+d0
−c−d1
Priors impressos. Atenção: a primeira tabela vem rotulada “P(A)” na prova, mas os valores são de C (−c = 4/5, +c = 1/5); a segunda é P(A)
CP(C)AP(A)
−c4/5−a1/4
+c1/5+a3/4
Restringir a evidência T igual a menos t produz uma tabela sobre S e D; multiplicar por P(D dado mais c) e somar D produz um fator sobre S 1. evidência: P(−t | S, D) 2. multiplica P(D | +c) e soma D 3. fator f(S) S | D+d−d +s19/204/5 −s3/50 +s67/80 −s3/20 (19/20)(1/4)+(4/5)(3/4) = 67/80 (3/5)(1/4)+0 = 3/20 verde: a coluna de +d que entra na soma ponderada por P(+d | +c) = 1/4 depois disso só resta somar S com os pesos de P(S | A, +c), somar A com P(A) e normalizar
Figura A-Q1.1 — Primeira metade da eliminação com a ordem D, A, S: restringir a evidência, multiplicar P(D|C), somar D. O fator resultante tem só duas entradas.
Resolução didática — não gabarito oficial (versão estática completa)

Hipóteses declaradas. Todas as variáveis são binárias com os valores e ; a evidência é ; a consulta é . As quatro tabelas acima são as do enunciado, incluindo — a tabela do meio, que é indispensável e está impressa na prova; a resolução numérica abaixo usa e . Como esse é o único dado que não aparece nos dois primeiros quadros, a seção “forma simbólica” repete a conta em função de e , para o caso de a cópia da prova chegar ilegível.

Fórmula.

P(+c∣−t)=αP(+c)∑a∑s∑dP(a)P(s∣a,+c)P(d∣+c)P(−t∣s,d)

Fatoração: P(A,C,S,D,T) = P(A)P(C)P(S|A,C)P(D|C)P(T|S,D). As contas a seguir eliminam D, depois S, depois A. Para os dois valores de C juntos, os produtos sobre (C,S,D) e (A,C,S) têm 8 entradas; as somas sobre D e S deixam, respectivamente, os pares (C,S) e (A,C), com 4 entradas cada.

  1. Instancie a evidência. vira o fator com 19/20, 3/5, 4/5 e 0 (tabela da esquerda na figura).
  2. Multiplique por e some D. Para : = 67/80. Para : = 3/20. Esse é o fator ; D foi eliminado.
  3. Multiplique por e some S, mantendo A: para , = 797/1280. Para , = 123/160. S foi eliminado.
  4. Pese pelos priors de A e pelo prior de C: = 135/1024. A foi eliminado.
  5. Repita para . Agora e : = 4/5 e = 0. Com as CPTs de S para : = 1/10 e = 4/25. Ponderando: = 23/250.
  6. Normalize. = 28651/128000. Logo = 16875/28651 ≈ 0,5890 e = 11776/28651 ≈ 0,4110.

Leitura do resultado. O prior de é pequeno (1/5), mas a evidência de atraso favorece por dois caminhos: contra , e , alto quando o papai está atrasado. Ainda assim o atraso é mais provável com e , e nesse canto : a massa que sobra é pequena, o que explica o denominador 28651/128000 ≈ 0,224. O efeito final é contra o prior 0,2 — uma subida forte, mas longe de certeza.

Forma simbólica em e

Com e :

f6(+c,+s)=19u+16(1−u)20=16+3u20,f6(+c,−s)=3u5

Levando isso às somas sobre S e A e depois normalizando, obtém-se

P(+c∣−t)=3792+1707u6736+1707u+13704v

Conferências: com e (valores impressos) o numerador é e o denominador , reproduzindo 16875/28651. Com outro par, e , a mesma fórmula dá 9291/22031. A forma simbólica serve para mostrar que a estrutura da conta não depende dos números — e para detectar erro de transcrição da tabela.

Checklist do que escrever na prova
  • Fatoração completa da conjunta (cinco fatores, um por nó).
  • Declaração da consulta, da evidência e das ocultas .
  • Ordem de eliminação e justificativa (menor fator intermediário).
  • Tabelas intermediárias com as frações, não decimais.
  • Normalização explícita com a soma dos dois valores.
  • Resultado em fração exata e decimal, mais a leitura em uma frase.

Método e exemplo menor: módulo de eliminação de variáveis. Fatoração e leitura do grafo: módulo de redes bayesianas. Para treinar a mesma família: T-elim-1 e T-elim-2.

Prova A · Questão 2 · página 1–2 · MDP

Jim e Pam: duas políticas, duas iterações de valor e duas de política

Enunciado (transcrição). Jim e Pam estão em uma grade de 1 a 5, onde Jim começa no quadrado 1 e Pam está fixa no quadrado 5.

A cada passo de tempo, Jim escolhe entre mover-se para a direita ou parar. A escolha de mover-se tem sucesso com probabilidade p e falha com probabilidade 1−p; quando falha, Jim fica no mesmo lugar, e a ação tem recompensa 0. O descanso sempre funciona e proporciona R(d)=45−d, onde d é a distância entre Jim e Pam. Por exemplo, no início d=4; se Jim decide parar, recebe R(4)=4. Representamos isso como um MDP de horizonte infinito sem estado terminal.

a) Jim considera duas políticas. Política 1: descansar sempre no início. Política 2: tentar mover-se para a direita uma vez e, em seguida, independentemente do sucesso ou fracasso, descansar para sempre. Considerando que Jim começa no quadrado 1, para quais valores de p a Política 1 é superior à Política 2 quando o fator de desconto é igual a 0,5? (Dica: a soma de uma série geométrica infinita com valor inicial a e razão r é S=a1−r.)

b) Agora, suponha que p=1. Ainda assumindo que Jim começa no quadrado 1, para quais valores de desconto a Política 1 é superior à Política 2?

c) Assuma γ=0,5 e p=1. Faça 2 iterações de Iteração de Valor.

StatessJ=1 sJ=2 sJ=3 sJ=4 sJ=5
V000000
V1(a preencher)
V2(a preencher)

d) Assuma γ=0,5 e p=1. Realize duas iterações de iteração de política para os seguintes locais de Jim.

StatessJ=1 sJ=2 sJ=3 sJ=4 sJ=5
πirightrestrestrestrest
Vπi(a preencher)
πi+1(a preencher)
Vπi+1(a preencher)
πi+2(a preencher)
Abrir resolução didática — A-Q2 (não é gabarito oficial)

Hipóteses e convenções declaradas

  • Estados S={1,2,3,4,5}; a recompensa depende só do estado e da ação: R(s,rest)=4s (pois d=5−s) e R(s,right)=0.
  • Transições: T(s,rest,s)=1; T(s,right,s+1)=p, T(s,right,s)=1−p para s<5; em s=5 a ação right fica em 5 (não existe 6).
  • Horizonte infinito, sem terminal; recompensa paga no instante da ação; atualização de VI síncrona; no empate de VI mantenho a ação antiga (declarado, para a política extraída ficar estável).

(a) Para quais p a Política 1 supera a Política 2, com γ=0,5?

Contas, etapa por etapa
  1. Política 1 (descansar sempre). A recompensa é constante e começa em t=0: Vπ1(1)= ∑t=0∞ 0,5t⋅4= 41−0,5= 8.

  2. Política 2 (mover uma vez, depois descansar). No instante 0 a ação é mover, então a recompensa é 0. No instante 1 Jim está em 2 com probabilidade p e em 1 com probabilidade 1−p; a partir daí descansa para sempre. Por isso:

    Vπ2(1)= p⋅∑t=1∞ 0,5t⋅16+(1−p) ⋅∑t=1∞ 0,5t⋅4=16p+4(1−p). O fator 0,51−0,5=1 é o que transforma a soma a partir de t=1 em "o valor da recompensa vezes 1".

  3. Comparação: 8>4+12p ⇔4>12p ⇔p< 13.

    Resposta: a Política 1 é superior para p∈[0, 1/3); em p=13 as duas valem 8 (empate); para p>13 mover vale mais a pena.

  4. Interpretação. Mover troca 4 de recompensa certa (descansar agora) por uma chance p de valer 16 a partir do passo seguinte, além de abrir mão de 4. A comparação exata é 8>4+12p: os 8 do "descansar sempre" só ganham enquanto o acréscimo esperado 12p não supera os 4 de diferença, ou seja, enquanto p<1/3.

(b) Com p=1, para quais γ a Política 1 supera a 2?

Com p=1 o movimento é determinístico. A Política 1 vale 41−γ e a Política 2 vale 16γ1−γ (a recompensa 16 só começa no instante 1, daí o fator γ).

41−γ> 16γ1−γ ⇔4>16γ ⇔γ< 14.

Resposta: γ∈[0, 1/4); em γ=1/4 empatam. Vale escrever que com γ=1 e horizonte infinito as duas políticas têm valor infinito — a comparação só faz sentido com γ<1.

Se os dois parâmetros variarem: para p e γ com 0 ≤ p ≤ 1 e 0 ≤ γ < 1, Vπ2(1)= 4γ(1+3p)1−γ, logo π1≻π2 ⇔γ<11+3p. Conferindo: p=1/3 dá γ<1/2 (item a) e p=1 dá γ<1/4 (item b).

(c) Duas iterações de valor (γ=0,5, p=1)

Fórmula declarada, com V0(s)=0:

Vk+1(s)= max{4s+0,5 Vk(s), 0+0,5Vk(s+1)}
Cálculo da primeira e da segunda iteração
  1. Iteração 1 (V0=0): V1(s)=max{4s,0}=4s. É a recompensa imediata, sem futuro.

  2. Iteração 2, estado por estado. Note que em s=5 a ação right leva a 5 (não existe 6), por isso o valor de right é 0+0,5⋅V1(5).

    • V2(1)=max{4+0,5⋅4,0,5⋅16}=max{6,8}=8
    • V2(2)=max{16+8,0,5⋅64}=32
    • V2(3)=max{64+32,0,5⋅256}=128
    • V2(4)=max{256+128,0,5⋅1024}=512
    • V2(5)=max{1024+512,0+0,5⋅1024}=1536 Descansar vale 1536; mover vale 512. Escolha descansar, sem empate.
  3. Tabela final (o formato que a prova pede):

StatessJ=1 2345
V000000
V1 4 16 64 256 1024
V2 8 32 128 512 1536

Conferência que impressiona: para s∈{1,2,3,4}, V2(s)=2⋅4s: cada iteração dobra o valor, porque "andar" busca o vizinho e o fator 11−0,5=2 aparece. Em s=5 não há para onde andar e o valor vem de descansar (1024+512), por isso 1536≠2⋅1024.

(d) Duas iterações de política (γ=0,5, p=1)

Avaliação, melhoria, avaliação — com as equações
  1. Avaliação de πi=(right,rest,rest,rest,rest). Sem max, equações de esperança:

    V(1)=0+0,5V(2); V(2)=16+0,5V(2); V(3)=64+0,5V(3); V(4)=256+0,5V(4); V(5)=1024+0,5V(5).

    Cada autorreferência V=c+0,5V dá V=2c: então V(2)=32, V(3)=128, V(4)=512, V(5)=2048 e V(1)=0,5⋅32=16.

  2. Melhoria. Para cada estado, compare Q(s,a)=R+0,5∑s′TV(s′) com o V calculado. Em s=5, right fica em 5: Q(5,rest)=1024+0,5⋅2048=2048 e Q(5,right)=0+0,5⋅2048=1024 ⇒ rest.

  3. Conferir a nova política. Na tabela de melhoria abaixo, escolha a ação de maior Q em cada estado. A política muda para avançar nos estados 1 a 4 e descansar no estado 5.

πi e seu valor
States12345
πirightrestrestrestrest
Vπi 16 32 128 512 2048
Melhoria de política: Q de cada ação
EstadoQ(s,rest) Q(s,right)Nova ação
11216right
23264right
3128256right
45121024right
520481024rest

Logo πi+1=(right,right,right,right,rest) (a quinta coluna é rest).

Avaliação de πi+1 e segunda melhoria
  1. Avaliar πi+1 (andar até 4, descansar em 5):

    V(1)=0+0,5V(2), V(2)=0,5V(3), V(3)=0,5V(4), V(4)=0,5V(5), V(5)=1024+0,5V(5)=2048.

    Voltando: V(4)=1024, V(3)=512, V(2)=256, V(1)=128.

  2. Melhorar de novo. Em s=4: rest =256+0,5⋅1024=768 e right =0+0,5⋅2048=1024 ⇒ right continua. Em s=5: rest =2048 e right =1024 ⇒ rest. Nos estados 1 a 3 as comparações também mantêm right (Q(1,rest)=68 contra 128, por exemplo).

  3. Parada: πi+2= πi+1. Então V*=(128,256,512,1024,2048) e π*= "andar até o 5, depois descansar".

Resultado do item (d)
States12345
πirightrestrestrestrest
Vπi 1632 128512 2048
πi+1 rightright rightright rest
Vπi+1 128256 5121024 2048
πi+2 rightright rightright rest

Verificação de otimalidade (fecha a resposta): com V*, em s=4 descansar valeria 256+0,5⋅1024=768<1024 e em s=5 andar valeria 1024<2048. Nenhuma troca isolada melhora, logo a política é ótima.

O que escrever na prova (checklist)

  • O modelo: S, A, T, R, γ, horizonte infinito, sem terminal — e a conversão R(s)=4s.
  • Em (a) e (b): a soma geométrica escrita antes de substituir, e a comparação “a partir de s=1”.
  • Em (c): fórmula de VI com max, tabela V0,V1,V2 e a observação de que em s=5 right fica em 5.
  • Em (d): equações de avaliação sem max, tabela de Q na melhoria, e a frase “como a política não mudou, convergiu”.
  • Comparar as duas ações no estado 5: em V₂, descansar vale 1536 e mover vale 512.

Resolução didática produzida para este estudo; não é gabarito oficial. Receita correspondente: Receita 1 — modelo formal, Receita 2 — VI, Receita 3 — PI.

Prova A · Questão 3 · página 2–3 · Redes neurais

Ativação quadrática: dimensões e derivadas da perda

Enunciado (transcrição). Redes Neurais: Função de Ativação Quadrática. Considere a seguinte rede neural, onde a entrada é x∈ℝd e a saída é um número real y^∈ℝ. Temos 2 matrizes de pesos: W1∈ℝn1×n2 e W2∈ℝk, onde k,d são números conhecidos e você precisa determinar os valores de n1 e n2. Considere:

z=W1x; y^:=W2⊤g(z) com uma função quadrática de ativação g(z):=z⊙z (exemplo: g((1,2,3)⊤)=(1,4,9)⊤) e função de perda ℒ(W1,W2):=12(y−y^)2.

a) Quais os valores de n1 e n2? Você pode escrever os valores em termos de k e d.

b) Calcule a derivada da função de perda em relação às seguintes grandezas: W2 e X. Sua resposta NÃO deve incluir a função de ativação (ou seja, você precisa calcular explicitamente a derivada em vez de escrever g′). Mas pode incluir x,y, y^,W1,W2 e z.

Abrir resolução didática — A-Q3 (não é gabarito oficial)

(a) n1 e n2

A resposta formal é uma cadeia de dimensões, não um palpite:

  1. x é d×1. Para W1x existir, o número de colunas de W1 tem de ser d ⇒ n2=d.
  2. Então W1x tem n1 linhas, isto é, z∈ℝn1; a ativação é elemento a elemento, logo g(z) tem a mesma forma.
  3. y^=W2⊤g(z) é escalar e W2∈ℝk, então W2⊤ é 1×k e g(z) precisa ter k entradas ⇒ n1=k.

Resposta: n1=k (neurônios escondidos) e n2=d (dimensão da entrada), ou seja, W1∈ℝk×d.

(b) As derivadas, sem deixar g′

Derivação completa (regra da cadeia)
  1. Comece pela perda. Com δ:=y^−y:

    ∂ℒ∂y^ =y^−y=δ.

  2. Como y^=∑jW2,jzj2 (porque g(zj)=zj2):

    ∂ℒ∂W2,j= δgj(z)= δzj2 ⇒ ∂ℒ∂W2= δ⊙(z⊙z).

  3. Para a entrada, encadeie por z. Cada componente: ∂ℒ∂zj= δW2,jg′(zj) =2δW2,jzj (aqui a derivada da quadrática, 2z, já foi substituída).

    Em forma vetorial: ∂ℒ∂z= 2δ(W2⊙z).

  4. Como z=W1x, temos ∂z∂x=W1 e a regra da cadeia matricial dá W1⊤ multiplicando:

    ∂ℒ∂x= W1⊤∂ℒ∂z =2(y^−y) W1⊤(W2⊙z).

Respostas em destaque:

∂ℒ∂W2= (y^−y)⊙g(z) ∂ℒ∂x= 2(y^−y) W1⊤(W2⊙z)

Em coordenadas (caso a correção prefira sem matrizes): ∂ℒ∂xi= 2(y^−y) ∑jW2,jzjW1,ji.

Conferência numérica (para não entregar uma fórmula "no escuro")

Tome d=k=2, W1=I, W2=(1/2,−1), x=(1/2,1) e y=1. Então: z=(1/2,1), g(z)=(1/4,1), y^=12⋅14−1=-7/8 e ℒ=12(1+7/8)2=225/128.

Com δ=-15/8:

  • ∂ℒ/∂W2=δg(z)=(-15/32,-15/8).
  • ∂ℒ/∂z=2δ(W2⊙z)=(-15/16,15/4).
  • ∂ℒ/∂x=W1⊤∂ℒ/∂z=(-15/16,15/4) (igual porque W1=I).
  • Um passo com η=0,1: W2←(35/64, -13/16), nova previsão -173/256 e nova perda 1.4041<1,7578 — coerente com descida de gradiente.

O que escrever na prova (checklist)

  • (a) A cadeia de dimensões em três linhas, terminando em n1=k e n2=d; dizer por que (para os produtos existirem).
  • (b) Declarar δ=y^−y, escrever ∂ℒ/∂y^ e só então encadear.
  • Substituir g′(z)=2z — deixar g′ na resposta é erro explícito do enunciado.
  • Conferir formas: ∂ℒ/∂W2 é k×1 e ∂ℒ/∂x é d×1.
  • Se sobrar tempo, o bônus ∂ℒ/∂W1= 2(y^−y)(W2⊙z)x⊤.

Resolução didática; não é gabarito oficial. Receita correspondente: Receita 2 — backprop e a fórmula geral.

Prova B

Prova B · Questão 1 · prova2.pdf (“Prova 1 (2026)”), página física 1

Naive Bayes com dois atributos — classificação de

Enunciado transcrito. “Aprendizado de Máquina: Classificação. Considere o conjunto de treinamentos da tabela, com as características X1, X2, e classe Y. Assuma uma Naive Bayes para modelar os dados de treinamento. Qual seria a classificação para um novo dado com X1 = 1 e X2 = 0?”

Conjunto de treinamento transcrito (8 exemplos)
#X1X2Y
1001
2010
3100
4100
5101
6111
7111
8111
Resolução didática — não gabarito oficial

Hipóteses. binária com valores 1 e 0; atributos binários; sem suavização (nenhuma contagem necessária é zero, então Laplace não muda a decisão e não é exigida).

  1. Conte as classes. nos exemplos 1, 5, 6, 7, 8 → = 5/8. nos exemplos 2, 3, 4 → = 3/8.
  2. Verossimilhança de em cada classe. Entre os cinco de , quatro têm (5, 6, 7, 8) → 4/5. Entre os três de , dois têm (3, 4) → 2/3.
  3. Verossimilhança de em cada classe. Em : exemplos 1 e 5 → 2/5. Em : exemplos 3 e 4 → 2/3.
  4. Escore de cada classe (prior × verossimilhanças): = 1/5; = 1/6.
  5. Compare. , logo a classificação é Y = 1.
  6. Posterior (opcional, mas recomendado). = 6/11 ≈ 0,5455 e = 5/11. A decisão é apertada: 0,545 contra 0,455.

Por que não normalizar antes de decidir. O fator é comum às duas classes, então a comparação dos escores já dá a classificação. Só é preciso normalizar para responder “com que probabilidade”.

Se houvesse zero count. Basta uma contagem zero, por exemplo nenhum exemplo de com , para o escore de virar 0 e o modelo declarar a classe impossível. A resposta formal seria aplicar Laplace, por atributo, e refazer a comparação.

Checklist do que escrever na prova
  • Tabela de contagens por classe (prior e cada atributo).
  • Fórmula do escore com o produto explícito.
  • Os dois escores em fração e a comparação.
  • Classificação final e, se sobrar tempo, o posterior normalizado.
  • Declaração de que não houve zero count (ou aplicação de Laplace se houve).

Receita e exemplo de seis exemplos: módulo de Naive Bayes. Para treinar: T-nb-1 e T-nb-2.

Prova 1 · Questão 2 · página 1 · Perceptron

Uma iteração do perceptron e a existência de um separador

Enunciado (transcrição). Considere treinar um perceptron com 2 características (x1,x2) e o termo bias, no conjunto de treinamento mostrado na tabela. Os pesos iniciais são w=[−1,1,0], onde os pesos correspondem a x1, x2 e 1, respectivamente.

x1 x2Label
34+
13−
23+
41−
12+
24−
31−

a) Depois de executar uma iteração do algoritmo nos 3 primeiros dados da tabela, qual é o novo vetor de pesos w?

b) Discuta sobre a existência de um vetor de pesos que consiga classificar os dados perfeitamente.

Abrir resolução didática — B-Q2 (não é gabarito oficial)

Convenções declaradas

  • Rótulos y∈{+1,−1}; entrada x=(x1,x2,1); escore z=w⊤x; previsão y^=sign(z) com empate (z=0) contando como −; taxa η=1; atualização w←w+yx somente quando erra.

(a) Uma passada pelos três primeiros dados

#Dadoz y^y Erro?Pesos depois
0————— (−1,1,0)
1(3,4) 1++não (−1,1,0)
2(1,3) 2+−sim (−2,−2,−1)
3(2,3) -11−+sim (0,1,0)
As contas, sem pular nenhum passo
  1. Dado 1: (3,4), rótulo +. z=−1⋅3+1⋅4+0⋅1=1>0 ⇒ previsão +, igual ao rótulo ⇒ sem atualização.

  2. Dado 2: (1,3), rótulo −. z=−1+3+0=2>0 ⇒ previu +, era − ⇒ erro. Atualização: (−1,1,0)+(−1)(1,3,1)=(−2,−2,−1).

  3. Dado 3: (2,3), rótulo +. z=−2⋅2−2⋅3−1⋅1=−11<0 ⇒ previu −, era + ⇒ erro. Atualização: (−2,−2,−1)+(2,3,1)=(0,1,0).

Resposta: wnovo=(0,1,0), com 2 erros nos três dados. Robustez de convenção: com rótulos {0,1} e w←w+(y−y^)x, y^=1[z>0], os mesmos três passos levam ao mesmo (0,1,0) — bom argumento para escrever se a correção usar outra convenção.

(b) Existe vetor de pesos que classifique tudo?

Não. A prova é por contradição, com o sistema de desigualdades que um separador w=(a,b,c) teria de satisfazer (com c o viés):

Positivos: 3a+4b+c>0, 2a+3b+c>0, a+2b+c>0
Negativos: a+3b+c≤0, 2a+4b+c≤0, 3a+b+c≤0, 4a+b+c≤0
A cadeia de desigualdades (3 subtrações e a contradição)
  1. Do positivo (2,3) e do negativo (1,3): (2a+3b+c)−(a+3b+c)=a>0.

  2. Do positivo (2,3) e do negativo (2,4): (2a+3b+c)−(2a+4b+c)=−b>0 ⇒b<0.

  3. Do negativo (3,1) e do positivo (1,2): (3a+b+c)−(a+2b+c)=2a−b<0. Como b<0, isso força a<0.

  4. Contradição: a>0 e a<0. Logo não existe separador linear; os conjuntos não são linearmente separáveis.

Evidência empírica (para juntar, sem substituir a prova). Rodando épocas completas na mesma ordem, com η=1, os erros por época são 5, 4 e 6 — não caem para zero. Ao fim da primeira época os pesos são (−5,−2,−1). Isso é indício, não prova: a prova é a contradição acima.

Leitura geométrica. Os positivos (1,2), (2,3),(3,4) são colineares (sobre x2=x1+1); os negativos ficam dos dois lados dessa reta. Uma reta não consegue isolar um segmento "cercado" assim.

O que fazer se pedirem uma solução: enriquecer as características (termos x12,x22,x1x2) ou usar uma rede com camada escondida. Um perceptron de uma camada não resolve — assim como não resolve XOR.

O que escrever na prova (checklist)

  • Convenções: rótulos, limiar, empate, η, ordem dos pesos (viés no fim).
  • A tabela do item (a) com z, previsão, rótulo, "erro?" e pesos novos — e a resposta (0,1,0) destacada.
  • No item (b): o sistema de desigualdades, as três subtrações, a contradição e a conclusão “não é linearmente separável”.
  • Uma frase separando evidência (erros que não zeram) de prova (contradição).

Resolução didática; não é gabarito oficial. Receita correspondente: treinar um perceptron à mão e provar não separabilidade.

Prova B · Questão 3 · prova2.pdf, página física 1

Enumeração e amostragem por rejeição na rede de cinco nós

Enunciado transcrito. “Considere a rede de Bayes da figura. Cada variável aleatória é binária com 2 possíveis valores (T, F). a) Qual é a equação para calcular P(+b | +e), usando inferência por enumeração? b) Para a pergunta seguinte considere os seguintes exemplos: (+a, +b, −c, +d, −e) (+a, −b, +c, +d, +e) (−a, +b, +c, +d, −e) (+a, +b, +c, +d, +e) (+a, −b, −c, −d, +e) (−a, −b, +c, +d, +e). Usando ‘rejection sampling’, calcule P(+b | +e).”

Rede da prova B com arestas B para A, D para A, A para C, C para E e B para E A B D C E arestas: B→A, D→A, A→C, C→E, B→E evidência: +e
Figura B-Q3.1. B e D são pais de A. A é pai de C. B e C são pais de E.
Resolução didática — não gabarito oficial
(a) Equação de enumeração para

Passo 1 — fatoração. Um termo por nó, com os pais do desenho:

P(A,B,C,D,E)=P(B)P(D)P(A∣B,D)P(C∣A)P(E∣B,C)

Em notação compacta: P(B)P(D)P(A|B,D)P(C|A)P(E|B,C). São cinco fatores, dos quais dois são priors de raiz ( e ) e três são condicionais.

Passo 2 — consulta e ocultas. Consulta , evidência ; ocultas , e — três variáveis binárias, logo combinações por valor de (16 no total, se você escrever o denominador por extenso).

Passo 3 — equação. Com normalizando sobre :

P(+b∣+e)=αP(+b)∑dP(d)∑aP(a∣+b,d)∑cP(c∣a)P(+e∣+b,c)

e, explicitando o normalizador, calculado com a mesma soma trocando por . Termos contados: 8 produtos por valor de , com 5 fatores cada. Escrever a fatoração e a contagem de termos é o que a correção procura: a prova não fornece as CPTs, então a resposta é simbólica.

(b) por amostragem por rejeição

Hipótese. As seis amostras são a lista completa fornecida; amostras com são descartadas; a estimativa é a proporção de entre as aceitas.

As seis amostras da prova B, com aceitas e rejeitadas pela evidência mais e, numerador e denominador #amostraEsituaçãoBentra no numerador? 1(+a, +b, −c, +d, −e)−e 2(+a, −b, +c, +d, +e)+e 3(−a, +b, +c, +d, −e)−e 4(+a, +b, +c, +d, +e)+e 5(+a, −b, −c, −d, +e)+e 6(−a, −b, +c, +d, +e)+e rejeitarejeita aceitaaceitaaceitaaceita −b+b−b−b sim nãonãonão denominador: 4 amostras com +e numerador: 1 dessas tem +b estimativa = 1/4 = 0,25 duas rejeições porque a evidência era −e com seis amostras, 0,25 é estimativa grosseira
Figura B-Q3.2 — A lista da prova marcada: 4 aceitas, 2 rejeitadas, 1 acerto de entre as aceitas.
  1. Filtre pela evidência. Amostras com : 2, 4, 5 e 6 → 4 aceitas; as amostras 1 e 3 () são descartadas → 2 rejeições.
  2. Conte a consulta entre as aceitas. Apenas a amostra 4 tem → 1.
  3. Divida. = 1/4 = 0,25.
  4. Comente o estimador. Com quatro aceitas, o erro amostral é grande: o erro padrão é , então o valor não é “a” probabilidade, é uma estimativa compatível com uma faixa larga. A amostra 5 ( com ) é improvável mas válida: rejeição filtra só pela evidência, não questiona a verossimilhança da amostra.
Checklist do que escrever na prova
  • Fatoração completa e identificação das ocultas.
  • Equação com e as somas na ordem escolhida.
  • Contagem de termos (8 por valor de B) e justificativa.
  • Lista de aceitas com marcação explícita e o par numerador/denominador.
  • Resultado 1/4 e a frase de que é estimativa, não valor exato.

Método: módulo de amostragem (rejeição e peso de verossimilhança) e módulo de redes bayesianas (fatoração). Para treinar: T-rej-1 e T-rej-2.

Prova B · Questão 4 · prova2.pdf, página física 2

Árvore de decisão: melhor e pior atributo para a raiz

Enunciado transcrito. “Usando os dados da tabela para predição de Read (yes/no). Os atributos e seus valores são: Fiction: yes/no; Age: new/old/ancient; Award: yes/no; Rating: hi/med/low; Length: short/medium/long. a) Qual atributo seria o melhor para colocar na raiz da árvore? Justifique detalhadamente. b) Que atributo binário seria a pior escolha para a raiz da árvore? Justifique detalhadamente.”

Dados transcritos da prova (7 exemplos)
Ex.FictionAgeAwardRatingLengthRead
1nonewnohishortYes
2yesancientnomedlongNo
3yesoldyeshimediumYes
4yesoldnomedmediumNo
5yesancientyeslowshortNo
6nonewnolowshortNo
7yesnewnohishortYes
Resolução didática — não gabarito oficial

Hipóteses. Entropia em bits (log base 2), ganho de informação clássico (ID3), média ponderada pelo número de exemplos de cada ramo. Valores arredondados em 6 casas decimais; diferenças de nas somas vêm do arredondamento.

  1. Distribuição inicial. Read = Yes nos exemplos 1, 3, 7 (3 de 7) e No nos exemplos 2, 4, 5, 6 (4 de 7). = 0.985228. Esse é o teto de ganho: nenhum atributo pode passar disso.
  2. Rating. hi → exemplos 1, 3, 7, todos Yes (H = 0); med → 2, 4, ambos No (H = 0); low → 5, 6, ambos No (H = 0). Os três ramos são puros, então a entropia depois é 0 e o ganho é integral: 0.985228.
  3. Age. new → 1, 6, 7: 2 Yes e 1 No, H = 0.918296; old → 3, 4: 1 Yes e 1 No, H = 1; ancient → 2, 5: 0 Yes e 2 No, H = 0. Resto = (3/7)(0,918296) + (2/7)(1) + (2/7)(0) = 0,679269. Ganho = 0.305958.
  4. Fiction. yes → 2, 3, 4, 5, 7: 2 Yes e 3 No, H = 0.970951; no → 1, 6: 1 Yes e 1 No, H = 1. Resto = (5/7)(0,970951) + (2/7)(1) = 0,979251. Ganho = 0.005978.
  5. Award. yes → 3, 5: 1 Yes e 1 No, H = 1; no → 1, 2, 4, 6, 7: 2 Yes e 3 No, H = 0,970951. Resto = (2/7)(1) + (5/7)(0,970951) = 0,979251. Ganho = 0.005978.
  6. Length. short → 1, 5, 6, 7: 2 Yes e 2 No, H = 1.000000; medium → 3, 4: 1 Yes e 1 No, H = 1; long → 2: 1 No, H = 0. Resto = (4/7)(1) + (2/7)(1) + (1/7)(0) = 0,857143. Ganho = 0.128085.
  7. Compare. Rating 0,985228 > Age 0,305958 > Length 0,128085 > Fiction = Award 0,005978. O melhor atributo para a raiz é Rating; ele separa os sete exemplos em três folhas puras, o que encerra a árvore com profundidade 1 (figura abaixo).
  8. Pior atributo binário. Os atributos binários são Fiction e Award, e ambos têm o mesmo ganho, bit — um empate exato, não uma coincidência de arredondamento: cada um deixa um ramo 50/50 e o outro 2/3, produzindo a mesma entropia média. Por isso a resposta correta é “Fiction e Award empatam como pior escolha”, com a justificativa numérica; apontar só um deles sem mencionar o empate perde ponto. Se o enunciado exigisse um só, o critério de desempate (por exemplo ordem alfabética) teria de ser declarado.
Árvore final da prova B: raiz Rating, ramos hi, med e low, folhas Yes, No, No Rating? himedlow Yes (3) No (2) No (2) exemplos: hi = {1, 3, 7}; med = {2, 4}; low = {5, 6} entropia dos três ramos = 0 → ganho = H(S) = 0,985228 profundidade 1: nenhuma pergunta adicional é necessária
Figura B-Q4.1 — Árvore obtida com Rating na raiz: três ramos puros, portanto uma árvore de profundidade 1.

Por que o ganho mede “melhor”. Escolher a raiz é escolher a pergunta que mais reduz incerteza sobre Read. Rating reduz a incerteza a zero porque cada valor seu determina a classe neste conjunto. Age reduz menos porque o ramo “old” fica 50/50. Length quase não reduz porque o ramo “short” fica 50/50 com quatro exemplos. O ganho é a diferença entre a incerteza de antes e a média ponderada da incerteza depois — nada mais.

Cuidado com o viés. Atributos com muitos valores tendem a ganhar mais por construirem ramos pequenos, mesmo sem generalizar. Aqui Rating tem três valores e vence com folga (ramos puros), então a escolha é robusta; mas em outro conjunto um atributo de 6 valores poderia “ganhar” apenas por fragmentar. Se a pergunta pedisse um critério mais justo, a resposta seria ganho de razão (ganho dividido pela informação de divisão).

Checklist do que escrever na prova
  • com a conta e a unidade (bits).
  • Ganho de todos os cinco atributos (a prova pede justificativa detalhada).
  • Entropia de cada ramo, não só o resultado final.
  • Resposta (a): Rating, com o argumento de ramos puros.
  • Resposta (b): Fiction e Award empatados no pior ganho, com os números.

Receita e exemplo de cinco exemplos: módulo de árvores de decisão. Para treinar: T-arv-1 e T-arv-2.

Treino progressivo

Questões autorais. Em cada família, tente primeiro o nível guiado e termine pelo nível acima da prova.

Treino · Enumeração e fatoração · nível guiado

T-enum-1 — cadeia de três nós

Rede , binárias, com , , , e . Calcule por enumeração.

Roteiro orientador (complete as lacunas)

  1. Escreva a fatoração .
  2. Marginalize X para obter para e .
  3. Monte nas duas linhas.
  4. Some as duas linhas para obter o denominador .
  5. Divida a linha pelo denominador.
Solução completa
  1. Fatoração: .
  2. ; .
  3. Linha : = 2/5. Linha : .
  4. Denominador: = 9/20.
  5. = 8/9 ≈ 0,889.

Comentário. O sinal de Z é forte: separa as duas hipóteses com folga. Note que era 1/2 e a evidência levou a 8/9.

Treino · Enumeração e fatoração · nível prova

T-enum-2 — chuva, sprinkler e grama molhada

Rede: , , (chuva, sprinkler ligado, grama molhada). Dados: ; , ; , , , . Calcule .

Solução completa

Fatoração. . Consulta , evidência , oculta .

  1. Restrinja a evidência: vira número em cada uma das quatro combinações de .
  2. Some para cada valor de C: = 41/100.
  3. Para : .
  4. Denominador: .
  5. = 82/127 ≈ 0,6457.

Comentário. A combinação tem probabilidade zero de grama molhada, mas não zera a classe: o produto com zero é uma parcela descartada, não o total. Confundir “uma parcela é zero” com “a classe é impossível” é o erro mais comum aqui.

Treino · Enumeração e fatoração · acima da prova

T-enum-3 — enumeração completa na topologia da prova B

Rede com , , , , . CPTs: , ; , , , ; , ; , , , . Calcule , informe quantos termos a enumeração tem por valor da consulta e justifique a fatoração.

Solução completa

Fatoração. . Consulta , evidência ; ocultas → 8 termos por valor de .

  1. Interna em C: com . Para : vale para e para . Para : e .
  2. Some D com . Para : ; . Para : e .
  3. Combine B: . Como a CPT de A já está condicionada em B, não existe prior para multiplicar — A não é raiz.
  4. Para : .
  5. Denominador: = 577/1000.
  6. = 2186/2885 ≈ 0,7577.

Comentário. Este treino cobra a diferença entre nó raiz e nó com pais: multiplicar — que não existe na rede — mudaria o resultado. Também cobra a ordem: eliminar C antes de D funciona porque C só depende de A.

Treino · Eliminação · nível guiado

T-elim-1 — elimine Y na cadeia

Com os dados do T-enum-1, calcule usando eliminação com ordem . Mostre o fator intermediário.

Roteiro orientador

  1. Quais fatores contêm Y? e .
  2. Fixe a evidência em .
  3. Multiplique e some Y, mantendo X → fator de duas entradas.
  4. Multiplique pelo prior de X e normalize.
Solução completa
  1. Evidência: e .
  2. Some Y para : = 59/100.
  3. Para : = 6/25.
  4. Aplicando os priors: e .
  5. Soma , que é — coerente com o T-enum-1.
  6. = 59/75 ≈ 0,7867.

Treino · Eliminação · nível prova

T-elim-2 — quatro variáveis, evidência no nó folha

Rede: , , , . Dados: ; , ; , ; , , , . Calcule por eliminação, na ordem , e informe o maior fator intermediário.

Solução completa
  1. Fatoração: . Restrinja a evidência: , com 9/10, 6/10, 5/10 e 1/10.
  2. Multiplique e some B para cada A. Para : .
  3. Para : .
  4. Priors: = 173/625; .
  5. Denominador: = 2689/5000.
  6. = 1384/2689 ≈ 0,5147. A evidência quase não move o prior 0,4: sobe só para 0,515.
  7. Maior fator intermediário: ao multiplicar aparece um fator sobre com 8 entradas — esse é o custo do caminho escolhido.

Treino · Eliminação · acima da prova

T-elim-3 — consulta no nó do meio e comparação de ordens

Com a mesma rede e os mesmos dados do T-elim-2, calcule na ordem , diga o tamanho do maior fator e explique o que muda se você eliminar antes de .

Solução completa
  1. Restrinja como no T-elim-2. Fixe e elimine C primeiro (ele só depende de A): vale para e para .
  2. Some A com : = 1923/5000.
  3. Para , o mesmo caminho dá .
  4. conferido: — igual ao T-elim-2, como tem de ser.
  5. = 1923/2689 ≈ 0,7151.
  6. Maior fator: sobre → 8 entradas. Eliminar C antes de A não reduz esse fator porque os dois caminhos tocam as mesmas três variáveis; o resultado é idêntico e o custo também. Só uma topologia com variável “de passagem” mudaria o custo entre ordens.

Treino · Amostragem por rejeição · nível guiado

T-rej-1 — seis amostras, evidência comum

Rede . Amostras de : 1 (+a,+b); 2 (+a,−b); 3 (−a,+b); 4 (+a,+b); 5 (−a,−b); 6 (−a,+b). Estime por rejeição.

Roteiro orientador

  1. Marque quais amostras têm .
  2. Conte as aceitas (denominador).
  3. Conte quantas aceitas têm (numerador).
  4. Divida e escreva “estimativa”.
Solução completa
  1. Aceitas (): 1, 3, 4, 6 → 4; rejeitadas: 2 e 5.
  2. Com entre as aceitas: 1 e 4 → 2.
  3. Estimativa: = 1/2.

Comentário. Duas amostras com foram aceitas: a evidência não filtra a consulta, apenas a condição. Se você tivesse descartado as , teria calculado outra coisa.

Treino · Amostragem por rejeição · nível prova

T-rej-2 — dez amostras com duas variáveis observáveis

Rede , (chuva, rua molhada, guarda-chuva). Amostras de : 1 (+r,+w,+u); 2 (+r,+w,−u); 3 (−r,+w,+u); 4 (−r,−w,−u); 5 (+r,+w,+u); 6 (−r,+w,−u); 7 (+r,−w,−u); 8 (−r,−w,+u); 9 (+r,+w,−u); 10 (−r,+w,+u). Estime por rejeição e diga quantas amostras foram descartadas.

Solução completa
  1. Aceitas pela evidência : 1, 2, 3, 5, 6, 9, 10 → 7; descartadas: 4, 7 e 8 (3 amostras).
  2. Com entre as aceitas: 1, 2, 5, 9 → 4.
  3. Estimativa: = 4/7 ≈ 0,571.

Comentário. A amostra 3 ( com ) é possível: a rua pode estar molhada sem chuva. Rejeição não julga plausibilidade, só evidência.

Treino · Amostragem por rejeição · acima da prova

T-rej-3 — evidência rara e custo do descarte

Rede (doença, teste positivo). Doze amostras de : 1 (+d,+t); 2 (−d,−t); 3 (−d,−t); 4 (+d,−t); 5 (−d,−t); 6 (−d,+t); 7 (−d,−t); 8 (−d,−t); 9 (+d,−t); 10 (−d,−t); 11 (−d,−t); 12 (−d,−t). (a) Estime por rejeição. (b) Qual é a taxa de aceitação observada? (c) Quantas amostras seriam esperadas para juntar 100 aceitas? (d) Por que peso de verossimilhança seria preferível aqui?

Solução completa
  1. (a) Aceitas (): 1 e 6 → 2. Com : apenas 1 → 1. Estimativa = 1/2.
  2. (b) Taxa de aceitação = 1/6 ≈ 0,167.
  3. (c) Para 100 aceitas: amostras = 600 (valor esperado).
  4. (d) Com evidência rara, ~5 de cada 6 amostras são jogadas fora. O peso de verossimilhança fixa , sorteia só e pondera cada amostra por : nenhuma amostra é descartada e a variância cai para o mesmo número de sorteios.

Comentário. Com duas aceitas, 1/2 é praticamente ruído: o erro padrão é grande. A resposta correta em prova inclui essa ressalva — e não trata a estimativa como valor exato.

Treino · Naive Bayes · nível guiado

T-nb-1 — seis exemplos, dois atributos

Treino: (1,1,A), (1,1,A), (1,0,B), (0,1,B), (0,0,B), (1,0,A). Classifique o novo exemplo com Naive Bayes, sem suavização.

Roteiro orientador

  1. Conte A e B (priors).
  2. Conte e dentro de cada classe.
  3. Monte os dois escores (prior × duas verossimilhanças).
  4. Compare; normalize se quiser o posterior.
Solução completa
  1. Priors: A tem 3 exemplos (1, 2, 6) e B tem 3 (3, 4, 5) → .
  2. Classe A: ; (só o exemplo 6).
  3. Classe B: (exemplo 3); (exemplos 3 e 5).
  4. Escores: A = 1/6; B = 1/9.
  5. Como , a classe é A; posterior = 3/5.

Treino · Naive Bayes · nível prova

T-nb-2 — oito exemplos, três atributos

Classifique o novo exemplo . Tabela de treino:

Treino do T-nb-2 (8 exemplos)
#a1a2a3classe
1110S
2101S
3011S
4111N
5001N
6100N
7010S
8000N
Solução completa
  1. Priors: S nos exemplos 1, 2, 3, 7 → 4 de 8; N nos exemplos 4, 5, 6, 8 → 4 de 8. Ambos 1/2.
  2. Classe S: (1, 2, 7); (1, 3); (2, 3).
  3. Classe N: (4, 6); (4); (4, 5).
  4. Escores: S = 3/32; N = 1/32.
  5. Posterior S = 3/4. Classificação: S, com 75% de confiança.

Comentário. Nenhuma contagem é zero: a suavização não é necessária e não mudaria a decisão. Se não aparecesse em N, o escore de N viraria 0 e a resposta precisaria de Laplace.

Treino · Naive Bayes · acima da prova

T-nb-3 — zero count: o que muda com Laplace e o que não muda

Treino , 10 exemplos. Classe S (6 exemplos): (1,1,0), (1,1,0), (1,0,0), (0,1,0), (1,1,0), (0,1,0). Classe N (4 exemplos): (1,0,1), (0,0,1), (0,1,1), (1,0,1). Classifique (a) por máxima verossimilhança e (b) com suavização de Laplace em atributos e prior, calculando o posterior. (c) A decisão muda?

Solução completa

(a) Sem suavização.

  1. Priors: , .
  2. Classe S: ; ; . Escore S = 0.
  3. Classe N: ; ; . Escore N = 1/20.
  4. Posterior de N = 1 (o denominador é 0 + 1/20). Decisão: N, com “certeza” artificial — o zero é artefato de amostragem, não impossibilidade lógica.

(b) Com Laplace. Cada atributo é binário: denominador ; priors com e .

  1. Classe S: ; ; . Escore = 35/1024.
  2. Classe N: ; ; . Escore = 25/432.
  3. Posterior de S = 189/509 ≈ 0,371.

(c) A decisão não muda — N continua vencendo (0,629 contra 0,371) — mas a justificativa muda: sem suavização a resposta era “S é impossível”, o que é falso. Depois de Laplace as duas classes têm probabilidade positiva e comparável. Moral: suavização não é para “ganhar a classificação”, é para não afirmar impossibilidade a partir de uma amostra pequena.

Treino · Árvores de decisão · nível guiado

T-arv-1 — quatro exemplos, um atributo perfeito

Treino : (1,1,sim), (1,0,sim), (0,1,não), (0,0,não). Calcule , o ganho de A e o ganho de B, e diga qual vai para a raiz.

Roteiro orientador

  1. Conte sim e não → entropia inicial.
  2. Divida por A: entropia de cada ramo e média ponderada.
  3. Repita para B.
  4. Subtraia de em cada caso.
Solução completa
  1. 2 sim e 2 não → bit = 1.
  2. Atributo A: tem 2 exemplos, ambos sim → H = 0; tem 2, ambos não → H = 0. Resto 0, ganho = 1.
  3. Atributo B: tem um sim e um não → H = 1; também → H = 1. Resto , ganho = 0.
  4. Raiz: A, que separa perfeitamente. B não informa nada: qualquer valor seu deixa a mesma mistura.

Treino · Árvores de decisão · nível prova

T-arv-2 — seis exemplos, três atributos

Calcule e o ganho dos três atributos; indique a raiz.

Treino do T-arv-2 (6 exemplos)
#climaventoumidadejogar
1solfracoaltanão
2solfortealtanão
3chuvafraconormalsim
4chuvafraconormalsim
5solfraconormalsim
6chuvafortenormalsim
Solução completa
  1. 4 sim e 2 não → = 0.918296.
  2. Clima: sol → 3 exemplos (1 sim, 2 não) H = 0,918296; chuva → 3 exemplos (3 sim) H = 0. Resto ; ganho = 0.459148.
  3. Vento: fraco → 4 exemplos (3 sim, 1 não) H = 0,811278; forte → 2 (1 sim, 1 não) H = 1. Resto ; ganho = 0.044110.
  4. Umidade: alta → 2 exemplos (2 não) H = 0; normal → 4 (4 sim) H = 0. Resto 0; ganho = 0.918296.
  5. Raiz: umidade, que separa perfeitamente (ganho igual a ). Clima é o segundo candidato; vento é quase inútil.

Comentário. Um atributo com dois valores pode separar perfeitamente; outro com dois valores pode não separar nada. O número de valores não decide — o ganho decide.

Treino · Árvores de decisão · acima da prova

T-arv-3 — empate entre atributos binários e viés do ganho

Treino com 8 exemplos: (1,1,a,sim), (1,1,a,não), (1,0,b,sim), (1,0,b,não), (0,1,b,sim), (0,1,b,não), (0,0,c,não), (0,0,c,não). Calcule e os ganhos de X, Y e Z. Explique o empate e discuta se Z é realmente “melhor”.

Solução completa
  1. Classes: 3 sim (exemplos 1, 3, 5) e 5 não → = 0.954434.
  2. X: → exemplos 1 a 4, com 2 sim e 2 não (H = 1); → 5 a 8, com 1 sim e 3 não (H = 0,811278). Resto ; ganho = 0.048795.
  3. Y: → exemplos 1, 2, 5, 6 (2 sim, 2 não, H = 1); → 3, 4, 7, 8 (1 sim, 3 não, H = 0,811278). Ganho = 0.048795.
  4. Z: a → 1 sim e 1 não (H = 1, peso 2/8); b → 2 sim e 2 não (H = 1, peso 4/8); c → 0 sim e 2 não (H = 0, peso 2/8). Resto ; ganho = 0.204434.
  5. Empate exato entre X e Y: as duas divisões produzem a mesma tabela de contingência (2/2 e 1/3), logo o mesmo ganho. A resposta correta é “X e Y empatam”, não “X é melhor por ser a primeira coluna”.
  6. Z tem ganho maior, mas com três valores ele fatia os dados em ramos menores. Parte do ganho é consequência da fragmentação, não de informação útil: é o viés do ganho de informação a favor de atributos com mais valores. Um critério mais justo divide o ganho pela informação de divisão (ganho de razão).

Treino — MDP, perceptron e redes neurais

Nove questões autorais, três por família e três níveis por família. O nível guiado traz roteiro; o nível prova não traz ajuda; o acima da prova muda convenção ou estrutura e exige justificativa. Resolva no papel antes de abrir a resolução.

Treino · MDP · nível guiado

Dois corredores, duas ações

Um robô de entregas se move entre dois corredores, A e B. Em cada passo ele escolhe ficar ou ir (ir alterna o corredor). Recompensas: ficar em A rende 1; ficar em B rende 4; ir rende 0. Desconto γ=12. Horizonte infinito, sem estado terminal.

(a) Monte a tabela de transição e calcule V1, V2 e V3 por iteração de valor, com V0=0.

(b) Mostre que a política "ir em A, ficar em B" satisfaz a equação de Bellman de otimalidade com V*=(4,8).

Roteiro: em (a), calcule primeiro o valor de cada ação com os valores da rodada anterior; só então tome o máximo. Em (b), verifique as duas ações em cada estado, não só a escolhida.

Abrir resolução — T-mdp-1

Modelo. T(A,ficar,A)=1, T(A,ir,B)=1, T(B,ficar,B)=1, T(B,ir,A)=1; recompensas 1, 0, 4, 0 respectivamente.

(a) Iteração de valor.

  1. V1(A)=max{1+0,0+0}=1; V1(B)=max{4,0}=4.
  2. V2(A)=max{1+0,5⋅1,0,5⋅4}=max{1,5,2}=2; V2(B)=max{4+0,5⋅4,0,5⋅1}=6. Note que já na segunda rodada "ir" passa a ser melhor em A.
  3. V3(A)=max{1+1,0,5⋅6}=3; V3(B)=max{4+3,0,5⋅2}=7.

(b) Verificação de otimalidade. Com V(A)=4 e V(B)=8:

  • Em A: ir =0+0,5⋅8=4 e ficar =1+0,5⋅4=3 ⇒ ir, valor 4 ✔.
  • Em B: ficar =4+0,5⋅8=8 e ir =0+0,5⋅4=2 ⇒ ficar, valor 8 ✔.

As duas equações de Bellman se confirmam, então π*=(ir,ficar) (A → ir; B → ficar) é ótima. Observe a assimetria que explica tudo: B rende 4 por passo, o dobro do valor de A, então vale pagar um passo sem recompensa para chegar em B.

Conferência: V3≤V* componente a componente (3 ≤ 4 e 7 ≤ 8) e a sequência é monótona crescente, como esperado com V0=0 e recompensas positivas.

Treino · MDP · nível prova

Três estados e um estado final

Um agente pode estar em E1, em E2 ou no estado final F (terminal, V=0). Desconto γ=12. Em E1, a ação avançar leva a E1 com probabilidade 1/2 e a E2 com 1/2, com recompensa 1; a ação parar leva a F com recompensa 2. Em E2, avançar leva a F com recompensa 6 e parar fica em E2 com recompensa 4.

(a) Faça três iterações de valor a partir de V0=0.

(b) Determine V* e π* resolvendo as equações da política candidata e verificando a otimalidade.

(c) Explique por que "parar" em E2 é ótima mesmo com "avançar" pagando 6 imediatamente.

Abrir resolução — T-mdp-2

(a) Com V(F)=0 sempre:

  • V1(E1)=max{1+0,2+0}=2; V1(E2)=max{6,4}=6.
  • V2(E1)=max{1+0,5(0,5⋅2+0,5⋅6),2}=max{3,2}=3; V2(E2)=max{6,4+0,5⋅6}=7.
  • V3(E1)=max{1+0,5(1,5+3,5),2}=7/2; V3(E2)=max{6,4+1,5}=15/2.

(b) Candidata π*=(avançar,parar). Avaliando (sem max): V(E2)=4+0,5V(E2)⇒V(E2)=8; V(E1)=1+0,5(0,5V(E1)+0,5⋅8) ⇒ 0,75V(E1)=3 ⇒ V(E1)=4. Verificação:

  • E1: avançar =4, parar =2 ⇒ avançar ✔.
  • E2: parar =8, avançar =6 ⇒ parar ✔.

(c) Porque 6 é recompensa imediata, enquanto "parar" rende 4 para sempre: 4+0,5⋅8=8>6. Com γ=0,5, uma recompensa recorrente de 4 vale 41−0,5=8; seria diferente com γ pequeno (aí o imediato venceria).

Armadilha evitada: colocar max na avaliação. Se a política é dada, você resolve o sistema; o max só entra na iteração de valor ou na melhoria.

Treino · MDP · acima da prova

Iteração de política partindo de uma política ruim — e o que quebra com γ = 1

Use o MDP da questão anterior (E1, E2, F; γ=12). Comece com π1=(parar em E1, avançar em E2).

(a) Execute iteração de política até convergir, mostrando avaliação e melhoria em cada rodada.

(b) Enuncie o teorema de melhoria de política e diga em que condição a melhoria é estrita neste exemplo.

(c) Explique o que deixaria de valer se γ=1.

Abrir resolução — T-mdp-3

(a) Rodada 1 — avaliar π1. Como E1 "parar" vai direto para F: V(E1)=2. Em E2 "avançar" vai para F com 6: V(E2)=6.

Melhoria. Em E1: avançar =1+0,5(0,5⋅2+0,5⋅6)=3 contra parar =2 ⇒ avançar. Em E2: parar =4+0,5⋅6=7 contra avançar =6 ⇒ parar. Então π2=(avançar,parar).

Rodada 2 — avaliar π2: V(E2)=8 e V(E1)=4 (mesma conta da T-mdp-2). O ganho na primeira melhoria foi 2 em E1.

Melhoria: em E1 avançar =4 e parar =2; em E2 parar =8 e avançar =6. Nada muda: π3=π2, convergiu. Valores iniciais: Vπ1=(2,6).

(b) Se π′ é gulosa em relação a Vπ, então Vπ′(s)≥Vπ(s) para todo s. A melhoria é estrita em s se a desigualdade for estrita em algum estado alcançável a partir de s com probabilidade positiva. Aqui ela é estrita em E1 (2 → 4) e em E2 (6 → 8); logo a política nova é estritamente melhor nos dois estados.

(c) Com γ=1 e horizonte infinito, os valores podem divergir: "parar" em E2 vale 4+4+4+⋯, que não converge, e nenhuma das contas acima tem solução finita. O operador de Bellman deixa de ser contração (fator 1), o teorema de Banach não se aplica e a comparação de políticas perde sentido — 4+γV=V não tem solução para γ=1.

Conferência: a sequência de valores é monótona (2 → 4 em E1; 6 → 8 em E2), coerente com o teorema — melhoria nunca piora.

Treino · Perceptron · nível guiado

Quatro pontos, três erros e convergência

Dados (1,0) e (2,0) com rótulo +1; (1,2) e (2,3) com rótulo −1. Pesos iniciais (0,0,0) (ordem w1,w2,w0), η=1, y^=sign(z) e empate contando como −.

(a) Percorra os quatro pontos na ordem dada, época por época, até zero erros.

(b) Calcule as margens y⋅z no fim e diga se a separação é estrita.

Roteiro: monte uma tabela com z, previsão, rótulo, "erro?" e pesos novos. Cuidado: no empate z=0 a previsão é −, então um ponto positivo empatado conta erro.

Abrir resolução — T-perc-1

(a) Ordem: +, +, −, −.

  • Época 1. (1,0): z=0 ⇒ previsão −, era + ⇒ erro ⇒ w=(1,0,1). (2,0): z=3 ⇒ acertou. (1,2): z=1+1=2 ⇒ previu +, era − ⇒ erro ⇒ w=(1,0,1)−(1,2,1)=(0,−2,0). (2,3): z=−6 ⇒ acertou. Erros: 2.
  • Época 2. (1,0) com w=(0,−2,0): z=0 ⇒ empate ⇒ previsão −, era + ⇒ erro ⇒ w=(1,−2,1). (2,0): z=3 ✔; (1,2): z=1−4+1=−2 ✔; (2,3): z=2−6+1=−3 ✔. Erros: 1.
  • Época 3. Escores 2, 3, −2, −3 com w=(1,-2,1): todos corretos ⇒ erros 0. Convergiu.

(b) Margens: (1,0): 2; (2,0): 3; (1,2): 2; (2,3): 3. A menor é 2 > 0, então a separação é estrita e os pesos atuais são um certificado de separabilidade: a reta é x1−2x2+1=0.

Conferência: se todos os y⋅z são positivos, você acabou de provar (construtivamente) que o conjunto é separável — não é preciso invocar o teorema de convergência.

Treino · Perceptron · nível prova

XOR: uma época e a prova de que nenhuma reta separa

Dados: (0,1) e (1,0) com rótulo +1; (0,0) e (1,1) com rótulo −1. Pesos iniciais (1,1,0), η=1, empate como −.

(a) Execute duas épocas e mostre os erros por época.

(b) Prove que não existe (a,b,c) que classifique os quatro pontos perfeitamente.

(c) Explique por que a oscilação observada em (a) não é prova de nada — e o que seria prova.

Abrir resolução — T-perc-2

(a) Época 1, w=(1,1,0):

  • (0,1) +: z=1 ✔ (erro 0 até aqui).
  • (1,0) +: z=1 ✔.
  • (0,0) −: z=0 ⇒ empate ⇒ previsão −, que é o rótulo ⇒ ✔.
  • (1,1) −: z=2 ⇒ previu +, era − ⇒ erro ⇒ w=(1,1,0)−(1,1,1)=(0,0,−1).

Erros na época 1: 1. Época 2, com w=(0,0,−1) (escore sempre −1, tudo previsto como −): (0,1) + erra ⇒ w=(0,1,0); (1,0) + erra ⇒ w=(1,1,1); (0,0) −: z=1 erra ⇒ w=(1,1,0); (1,1) −: z=2 erra ⇒ w=(0,0,−1). Erros: 4. Terceira época volta a 4 e o ciclo se repete.

(b) Suponha que exista (a,b,c) com sign correto em todos. Então:

  • (0,0) −: c≤0.
  • (1,1) −: a+b+c≤0.
  • (0,1) +: b+c>0.
  • (1,0) +: a+c>0.

Somando as duas últimas: a+b+2c>0. Como a+b+c≤0, isso obriga c>0 (porque a+b+2c=(a+b+c)+c>0 exige c>0). Contradiz c≤0. Logo não existe separador.

(c) Algumas épocas com erro mostram apenas que aquela sequência não achou solução: pode ser ordem ruim ou poucas épocas. A prova é o sistema de desigualdades impossível de (b). A assimetria que vale lembrar: zero erros numa época é prova positiva (os pesos atuais classificam tudo); erros persistentes não são prova negativa.

Treino · Perceptron · acima da prova

Rótulos {0,1}, equivalência de regras e a cota do teorema

Considere (2,1) e (1,2) com classe 1; (0,0) e (1,0) com classe 0. Pesos iniciais (0,0,0), η=1, y^=1[z>0] e atualização w←w+(y−y^)x.

(a) Treine até zerar os erros e diga quantos erros ocorreram por época.

(b) Repita com rótulos ±1 e a regra w←w+yx. O resultado é o mesmo? Justifique.

(c) Calcule a cota (R/γm)2 para o separador x1+x2=1,5 e compare com os erros observados.

Abrir resolução — T-perc-3

(a) Ordem: 1, 1, 0, 0.

  • (2,1), z=0 ⇒ y^=0 (empate não passa de 0), mas y=1 ⇒ erro ⇒ w=(2,1,1).
  • (1,2): z=2+2+1=5 ⇒ y^=1 ✔.
  • (0,0): z=1 ⇒ y^=1, era 0 ⇒ erro ⇒ w=(2,1,1)−(0,0,1)=(2,1,0).
  • (1,0): z=2 ⇒ y^=1, era 0 ⇒ erro ⇒ w=(1,1,−1).

Segunda época: (2,1): 2+1−1=2 ✔; (1,2): 1+2−1=2 ✔; (0,0): −1 ✔; (1,0): 1−1=0 ⇒ y^=0 ✔ (empate do lado 0). Erros: 3 e 0.

(b) Com rótulos ±1, a regra é w←w+yx quando y⋅z≤0. A regra {0,1} é w←w+(y−y^)x, com (y−y^)∈{−1,0,1}. Se y=1 e y^=0, o incremento é +1⋅x, igual a yx com y=+1; se y=0 e y^=1, o incremento é −1⋅x, igual a yx com y=−1. Nos acertos nada muda em nenhuma das duas. Logo as sequências coincidem: w=(1,1,-1) nas duas convenções — e a versão ±1 confirma: (1,1,-1).

(c) R=maxx‖x‖=5 (o ponto (2,1)). O separador unitário é (1,1)/2; as distâncias dos pontos à reta x1+x2=1,5 são 1,5/√2 (positivos) e, para (1,0), 0,5/2 — então γm=0,5/2, γm2=0.125 e R2=5.0.

Cota: (R/γm)2=R2/γm2=5/0,125=40.0 erros. Observamos 3. A cota é garantia de pior caso, não previsão: o perceptron pode convergir muito antes. Escrever isso na prova mostra que você entendeu o teorema em vez de decorá-lo.

Conferência: o ponto (1,0) fica exatamente na fronteira x1+x2=1 com os pesos finais? Não: com w=(1,1,−1) seu escore é 0. Por isso a convenção z>0 importa: ele é classificado como 0 e conta acerto. Se você usar z≥0, ele vira erro e o treino continua — declare a convenção.

Treino · Redes neurais · nível guiado

Rede escalar: todas as derivadas, uma por uma

Rede com uma entrada e um neurônio: x=2, z=w1x+b1 com w1=3 e b1=0; g(z)=z2; y^=w2g(z)+b2 com w2=12 e b2=0; alvo y=10; perda ℒ=12(y−y^)2.

(a) Faça a ida e calcule ℒ.

(b) Calcule ∂ℒ/∂w2, ∂ℒ/∂z, ∂ℒ/∂w1 e ∂ℒ/∂x.

(c) Calcule também ∂ℒ/∂b1 e ∂ℒ/∂b2.

Roteiro: calcule δ=y^−y uma vez e use em tudo. Não esqueça que g′(z)=2z deve ser substituído por número.

Abrir resolução — T-redes-1

(a) Ida. z=3⋅2+0=6; g(z)=36; y^=12⋅36=18; ℒ=12(10−18)2=32.

(b) δ=y^−y=8.

  • ∂ℒ/∂w2=δg(z)=8⋅36=288.
  • ∂ℒ/∂z=δw2g′(z)=8⋅12⋅12=48.
  • ∂ℒ/∂w1=(∂ℒ/∂z)⋅x=48⋅2=96.
  • ∂ℒ/∂x=(∂ℒ/∂z)⋅w1=48⋅3=144.

(c) O viés b2 soma direto em y^: ∂ℒ/∂b2=δ=8. O viés b1 entra em z, então ∂ℒ/∂b1=∂ℒ/∂z=48.

Conferência por diferenças finitas: aumentando w1 em 0,001, z vira 6,002, y^ vira 18,012 e ℒ sobe aproximadamente 0,096; dividindo por 0,001 dá ≈ 96 — igual ao gradiente.

Treino · Redes neurais · nível prova

Duas entradas, dois neurônios escondidos, viés explícito

Rede com d=2, k=2: W1=[[1,0],[0,−1]], b1=(1,−1), W2=(1,1), b2=1; x=(1,2), y=3, g(z)=z⊙z, ℒ=12(y−y^)2.

(a) Calcule z, y^ e ℒ.

(b) Calcule ∂ℒ/∂W2, ∂ℒ/∂b2, ∂ℒ/∂z, ∂ℒ/∂x, ∂ℒ/∂W1 e ∂ℒ/∂b1.

(c) Verifique a forma de cada gradiente contra a da grandeza correspondente.

Abrir resolução — T-redes-2

(a) z=W1x+b1=(1⋅1+1,−1⋅2−1)=(2,-3). Ativação: g(z)=(4,9). Saída: y^=1⋅4+1⋅9+1=14. Perda: ℒ=12(3−14)2=121/2.

(b) δ=y^−y=11.

  • ∂ℒ/∂W2=δ⊙g(z)=(44,99);
  • ∂ℒ/∂b2=δ=11;
  • ∂ℒ/∂z=2δ(W2⊙z)=22⋅(1⋅2,1⋅(−3))=22⋅(2,−3)=(44,−66);
  • ∂ℒ/∂x=W1⊤(44,−66)=(44,66) (porque W1⊤=[[1,0],[0,−1]]);
  • ∂ℒ/∂W1=(∂ℒ/∂z)x⊤=[[44,88],[-66,-132]];
  • ∂ℒ/∂b1=∂ℒ/∂z=(44,−66).

(c) Formas: W2 é 2×1 e seu gradiente também; W1 é 2×2 e o gradiente é 2×2; x e z são vetores 2×1, e os gradientes também. Esse teste pega o erro clássico de esquecer a transposta.

Conferência: todos os gradientes compartilham o fator δ=11; se um deles não tiver esse fator, há erro de conta.

Treino · Redes neurais · acima da prova

O neurônio que não aprende: gradiente nulo e o que a rede pode representar

Rede com k=2: W1=[[1,1],[0,0]], b1=(0,0), W2=(2,5), b2=−1, x=(1,2), y=4, g(z)=z⊙z.

(a) Calcule a ida, ℒ e todos os gradientes.

(b) Explique por que a segunda unidade escondida nunca sai de z=0 se os pesos dela começam todos nulos (e o viés também).

(c) Sem viés de saída e com W1=0, que funções a rede representa? E com b2 livre?

Abrir resolução — T-redes-3

(a) z=(1⋅1+1⋅2,0)=(3,0); g(z)=(9,0); y^=2⋅9+5⋅0−1=17; ℒ=12(4−17)2=169/2; δ=13.

  • ∂ℒ/∂W2=δg(z)=(117,0); ∂ℒ/∂b2=13.
  • ∂ℒ/∂z=2δ(W2⊙z)=26⋅(2⋅3,5⋅0)=(156,0).
  • ∂ℒ/∂W1=(156,0)(1,2)⊤=[[156,312],[0,0]].
  • ∂ℒ/∂x=W1⊤(156,0)=(156,156).

(b) Com W1,2⋅=0 e b1,2=0, temos z2=0 para qualquer entrada. Seu gradiente é 2δW2,2z2=0: a linha 2 de W1 e o viés b1,2 não recebem atualização (é o que aparece como linha de zeros em ∂ℒ/∂W1). Como os pesos dessa unidade não mudam, z₂ continua zero para a mesma entrada. O gradiente de W₂,₂ também é zero: δ multiplica a ativação g(z₂) = 0.

(c) Cada unidade contribui com W2,i(W1,i⋅x)2, uma forma quadrática homogênea. Com W1=0, z=0 e y^=b2: a rede representa apenas a constante b2 — e, como o gradiente de W1 é zero, ela fica presa nesse ponto. Sem b2, a saída é 0 em toda parte. Ou seja: sem viés, essa arquitetura não representa constante não nula nem função linear (2x1+1 é impossível), só formas quadráticas puras.

Simulados autorais

100 pontos e 120 minutos sugeridos por simulado. Pontuação e tempo didáticos, não oficiais.

Simulado 1

Simulado 1 · bloco 1 · Bayes exato · 20 pontos

Entrega de comida: chuva, trânsito, motoboy e atraso

Rede: , , (chuva, trânsito, motoboy sai tarde, atraso). Todas binárias. Dados:

CPTs do bloco (valores em frações de denominador 10)
Distribuiçãovalores
3/10 e 7/10
8/10 e 3/10
4/10 e 6/10
9/10 e 6/10
5/10 e 2/10
  1. (4 pts) Escreva a fatoração da conjunta e identifique consulta, evidência e ocultas para a pergunta .
  2. (10 pts) Calcule e depois , mostrando as massas intermediárias.
  3. (3 pts) Escolha uma ordem de eliminação para e informe o número de entradas do maior fator intermediário.
  4. (3 pts) e são independentes? E condicionadas a ? Justifique com d-separação.
Resolução didática — pontuação por subitem
  1. (4 pts) Um fator por nó: . Consulta ; evidência ; ocultas e (2 pontos pela fatoração, 1 pela consulta/evidência, 1 pelas ocultas).
  2. (10 pts) Primeiro marginalize : , logo . Depois dado : ; . Então = 1/2 (4 pts). Agora a massa conjunta: = 24/125 (4 pts). Posterior: = 48/125 ≈ 0,384 (2 pts). O prior 0,3 sobe para 0,384: a evidência de atraso é fraca porque o motoboy atrasado também explica o atraso. Para fechar a coerência, a mesma conta para M: = 34/125 e = 68/125.
  3. (3 pts) Ordem : eliminar C primeiro produz um fator sobre T com 2 entradas; em seguida é um fator sobre com 4 entradas. Alternativa igualmente válida: eliminar M primeiro (2 entradas) e depois C. Qualquer ordem correta vale os 3 pontos, desde que o maior fator declarado corresponda à ordem escrita.
  4. (3 pts) e são raízes ligadas por um único caminho , que tem um colisor em . Sem observar (nem descendentes dele, e não há), o caminho está bloqueado: são independentes — 1,5 ponto. Observando , o colisor abre o caminho e elas passam a ser dependentes (explicação mútua: trânsito e motoboy competem como causas do atraso) — 1,5 ponto.

Checklist. Fatoração com quatro fatores; antes de tudo; massas conjuntas em fração; normalização explícita; justificativa de d-separação citando o colisor e o que está observado.

Simulado 1 · bloco 2 · Amostragem · 10 pontos

Rejeição na mesma rede da entrega

Dez amostras de , na ordem topológica:

Amostras fornecidas (na ordem em que foram sorteadas)
#CTMA
1+c+t+m+a
2+c+t−m+a
3−c−t−m−a
4−c+t+m+a
5+c−t+m−a
6−c+t−m+a
7+c+t+m+a
8+c−t−m+a
9−c−t+m+a
10−c+t+m−a
  1. (4 pts) Marque as amostras aceitas e as rejeitadas para a evidência e escreva numerador e denominador.
  2. (3 pts) Estime .
  3. (3 pts) Compare com o valor exato do bloco 1 (48/125) e explique a diferença em no máximo três linhas.
Resolução didática — pontuação por subitem
  1. (4 pts) Aceitas: 1, 2, 4, 6, 7, 8, 9 → 7. Rejeitadas: 3, 5 (evidência ), 10 (idem). Com entre as aceitas: 1, 2, 7, 8 → 4.
  2. (3 pts) = 4/7 ≈ 0,571.
  3. (3 pts) Exato: 48/125 ≈ 0,384. A estimativa superestima em ~0,19 porque só sete amostras foram aceitas e o sorteio não é equilibrado; erro de amostragem cai com e não indica que a conta exata esteja errada. Três linhas bastam: valor, diferença, causa.

Checklist. Lista de aceitas explícita; denominador 7 (não 10); numerador 4; frase final dizendo “estimativa”.

Simulado 1 · bloco 3 · Naive Bayes · 10 pontos

Classificação de um novo exemplo

Treino (8 exemplos)
#a1a2classe
111S
211S
310S
401S
501N
600N
700N
811N

Classifique . (a) (4 pts) priors e verossimilhanças; (b) (4 pts) escores; (c) (2 pts) classe e posterior.

Resolução didática — pontuação por subitem
  1. (4 pts) S nos exemplos 1 a 4 (4 de 8) e N nos exemplos 5 a 8 (4 de 8) → priors 1/2 e 1/2. (1, 2, 3); (3); (8); (6, 7).
  2. (4 pts) S: = 3/32. N: = 1/16.
  3. (2 pts) e , então S vence; posterior = 3/5. Não há zero count, logo Laplace não é necessário — dizê-lo vale a justificativa.

Checklist. Contagens por classe na tabela; escores com prior explícito; comparação em frações de mesmo denominador; posterior normalizado.

Simulado 1 · Bloco 4 · MDP · 20 pontos · ~25 min

Jim e Pam com desconto maior

Mesma grade de 1 a 5 do problema clássico: Jim começa no quadrado 1, Pam fica no 5, e descansar rende R(d)=45−d (com d a distância até Pam). Andar para a direita funciona com probabilidade p e rende 0. Horizonte infinito, sem terminal. Agora use γ=0,75 e p=1 em todos os itens.

(a) [6 pontos] Com γ=0,75, para quais valores de p a Política 1 (descansar sempre) é superior à Política 2 (mover uma vez e depois descansar para sempre)? Comece em s=1.

(b) [8 pontos] Com p=1, faça duas iterações de iteração de valor a partir de V0=0 e preencha a tabela (declare a fórmula usada).

(c) [6 pontos] Determine V* e π* para γ=0,75 e p=1, verificando a otimalidade com a equação de Bellman.

States12345
V000000
V1(a preencher)
V2(a preencher)
Abrir resolução — Simulado 1, bloco MDP

Convenções. R(s)=4s (pois d=5−s): 4, 16, 64, 256, 1024. Em s=5, andar fica em 5. Atualização síncrona; desempate mantendo a ação anterior.

(a) [6] Política 1: Vπ1(1)= 41−0,75= 40,25=16.

Política 2: no instante 0 a recompensa é 0 (andar); a partir do instante 1, Jim está em 2 e descansa: Vπ2(1)= p0,75⋅160,25+ (1−p)0,75⋅40,25 =48p+12(1−p) =12+36p.

Comparando: 16>12+36p ⇔4>36p⇔p< 1/9. Resposta: p∈[0,1/9); em p=1/9 empatam; acima, mover compensa. Intuição: com γ grande o futuro pesa muito, então andar (que quadruplica a recompensa) vale a pena para quase todo p.

(b) [8] Fórmula: Vk+1(s)= max{4s+0,75 Vk(s), 0,75Vk(s+1)} (com s+1=5 quando s=5).

  • Iteração 1: como V0=0, sai V1(s)=4s.
  • Iteração 2, estado por estado: V2(1)=max{4+3,0,75⋅16}=12; V2(2)=max{16+12,0,75⋅64}=48; V2(3)=192; V2(4)=768; V2(5)=max{1024+768,0,75⋅1024}=1792.
States12345
V000000
V1 416 64256 1024
V2 1248 192768 1792

(c) [6] Candidata π*=(andar ×4, descansar em 5). Avaliando: V(5)=1024+0,75V(5) ⇒V(5)=4096; depois V(4)=0,75⋅4096=3072, V(3)=2304, V(2)=1728, V(1)=1296.

Verificação: em s=1, descansar vale 4+0,75⋅1296=976<1296 (andar); em s=4, descansar vale 2560<3072; em s=5, andar vale 3072<4096 (descansar). Nenhuma troca melhora ⇒ ótima. Política: (right,right,right,right,rest).

Distribuição dos pontos e checklist

  • (a) 6 pontos: 2 pela fórmula das duas políticas, 2 pela inequação, 2 pela resposta com o empate.
  • (b) 8 pontos: 2 pela fórmula de VI com max, 3 pela primeira iteração, 3 pela segunda (incluindo o caso s=5).
  • (c) 6 pontos: 3 pela avaliação da candidata, 3 pela verificação de Bellman e pela política declarada.
  • Declare R(s)=4s e o comportamento de "andar" em s=5.

Simulado 1 · Bloco 5 · Perceptron · 10 pontos · ~12 min

Quatro pontos e uma reta final

Dados de treino (com viés implícito 1): (1,0) e (1,1) com rótulo +1; (0,3) e (2,4) com rótulo −1. Pesos iniciais (−1,2,0) na ordem (w1,w2,w0), η=1, y^=sign(z) e empate contando como −.

(a) [4 pontos] Execute uma passada pelos três primeiros dados, na ordem dada, e informe o vetor de pesos ao final da passada.

(b) [4 pontos] Continue o treino até uma época sem erros. Informe os pesos finais e as margens y⋅z.

(c) [2 pontos] Escreva a equação da fronteira de decisão final e diga se o conjunto é linearmente separável.

Abrir resolução — Simulado 1, bloco Perceptron

(a) [4] Ordem: (1,0), (1,1), (0,3).

  • (1,0): z=−1+0+0=-1 ⇒ previu −, era + ⇒ erro ⇒ w=(−1,2,0)+(1,0,1)=(0,2,1).
  • (1,1): z=0+2+1=3 ⇒ + ✔.
  • (0,3): z=0+6+1=7 ⇒ previu +, era − ⇒ erro ⇒ w=(0,2,1)−(0,3,1)=(0,−1,0).

Pesos ao fim da passada: (0,−1,0), com 2 erros. Ponto de atenção: esse vetor classifica todos os pontos como positivos (o escore é −x2), então ainda não serve — a próxima passada vai corrigir.

(b) [4] Época 2: (1,0) dá z=0 (empate ⇒ previu −, era + ⇒ erro) ⇒ w=(1,−1,1); os outros três ficam corretos. Erros: 1. Época 3: escores 2, 1, −2, −1 ⇒ 0 erros ⇒ convergiu com w=(1,-1,1).

Margens y⋅z: (1,0): 2; (1,1): 1; (0,3): 2; (2,4): 1 — todas positivas, logo a separação é estrita.

(c) [2] Fronteira z=0: x1−x2+1=0, isto é, x2=x1+1. O conjunto é linearmente separável — e a prova é construtiva: os pesos acima classificam todos os pontos corretamente com margem positiva.

Distribuição dos pontos e checklist

  • (a) 4 pontos: 2 pela tabela de z e decisões, 2 pelos dois pesos atualizados.
  • (b) 4 pontos: 2 pela continuação correta, 2 pelas margens.
  • (c) 2 pontos: 1 pela equação, 1 pela conclusão de separabilidade com justificativa construtiva.
  • Não esqueça de declarar a convenção de empate — ela decide o primeiro passo da época 2.

Simulado 1 · Bloco 6 · Redes neurais · 15 pontos · ~18 min

Rede quadrática com viés e um passo de descida

Rede x∈ℝ2, z=W1x+b1, y^=W2⊤g(z)+b2, g(z)=z⊙z, ℒ=12(y−y^)2. Dados: W1=[[1,−1],[0,2]], b1=(0,1), W2=(1,2), b2=0, x=(2,1), y=5.

(a) [5 pontos] Faça a ida, calcule ℒ e confirme as formas de z, g(z) e y^.

(b) [6 pontos] Calcule ∂ℒ/∂W2, ∂ℒ/∂b2, ∂ℒ/∂z e ∂ℒ/∂x (sem deixar g′).

(c) [4 pontos] Calcule ∂ℒ/∂W1 e ∂ℒ/∂b1; depois dê um passo com η=0,01 em W2 e mostre que a perda diminuiu.

Abrir resolução — Simulado 1, bloco Redes neurais

(a) [5] z=W1x+b1 =(1⋅2−1⋅1+0, 0⋅2+2⋅1+1) =(1,3) (2×1); g(z)=(1,9) (mesma forma); y^=1⋅1+2⋅9+0=19 (escalar); ℒ=12(5−19)2=98. δ=14.

(b) [6]

  • ∂ℒ/∂W2=δg(z)=(14,126) (forma 2×1);
  • ∂ℒ/∂b2=δ=14;
  • ∂ℒ/∂z=2δ(W2⊙z)=28⋅(1⋅1,2⋅3)=(28,168);
  • ∂ℒ/∂x=W1⊤(28,168)=(28,308) (pois W1⊤=[[1,0],[−1,2]]).

(c) [4] ∂ℒ/∂W1=(∂ℒ/∂z)x⊤= [[56,28], [336,168]] e ∂ℒ/∂b1=(28,168).

Passo em W2: W2← (1,2)−0,01⋅(14,126)= (43/50,37/50). Nova previsão: 4350⋅1+3750⋅9=37650=7,52, nova perda 12(5−7,52)2=3969/1250<98. A descida funcionou (a perda caiu de 98 para ≈ 3,18).

Distribuição dos pontos e checklist

  • (a) 5: 2 pelo forward, 1 pelas formas, 2 pela perda.
  • (b) 6: 2 por ∂ℒ/∂W2, 1 por ∂ℒ/∂b2, 2 por ∂ℒ/∂z, 1 por ∂ℒ/∂x.
  • (c) 4: 2 por ∂ℒ/∂W1 e ∂ℒ/∂b1, 2 pelo passo com verificação da perda.
  • O fator 2 da ativação quadrática aparece em ∂ℒ/∂z — esquecê-lo derruba (b) e (c).

Simulado 1 · bloco 4 · Árvores de decisão · 15 pontos

Raiz da árvore para “jogar”

Treino (8 exemplos)
#climaventoumidadejogar
1solfracoaltanão
2solfortealtanão
3nubladofracoaltasim
4chuvafraconormalsim
5chuvafortenormalsim
6chuvafraconormalnão
7nubladofortenormalsim
8solfraconormalsim

(a) (3 pts) em bits. (b) (8 pts) ganho de clima, vento e umidade com as entropias dos ramos. (c) (4 pts) raiz escolhida e justificativa em termos de pureza dos ramos.

Resolução didática — pontuação por subitem
  1. (3 pts) Sim nos exemplos 3, 4, 5, 7, 8 (5); não nos 1, 2, 6 (3). = 0.954434.
  2. (8 pts) Clima: sol → 1 sim, 2 não (H = 0,918296); nublado → 2 sim (H = 0); chuva → 2 sim, 1 não (H = 0,918296). Resto ; ganho = 0.265712. Vento: fraco → 3 sim, 2 não (H = 0,970951); forte → 2 sim, 1 não (H = 0,918296). Resto ; ganho = 0.003229. Umidade: alta → 1 sim, 2 não (H = 0,918296); normal → 4 sim, 1 não (H = 0,721928). Resto ; ganho = 0.158868.
  3. (4 pts) Raiz: clima (0,265712 > 0,158868 > 0,003229). Justificativa: clima é o único que isola um ramo puro (nublado, 2 exemplos, entropia 0) e deixa os outros dois com a menor mistura possível; umidade isola um ramo interno quase puro mas mantém cinco exemplos com 4 sim e 1 não; vento praticamente não reduz a mistura (0,003 bit).

Checklist. com unidade; entropias de todos os ramos; pesos 3/8, 2/8, 3/8 explícitos; ganhos em bits; decisão comparada em números.

Simulado 2

Simulado 2 · bloco 1 · Bayes exato · 20 pontos

Viagem, gripe, febre e cansaço: consulta na raiz com duas evidências

Rede: , , (viagem, gripe, febre, cansaço). Dados:

CPTs do bloco (frações de denominador 10)
Distribuiçãovalores
5/10 e 5/10
3/10 e 1/10
9/10 e 1/10
8/10 e 3/10
  1. (4 pts) Fatoração e identificação de consulta, evidência e ocultas para .
  2. (10 pts) Calcule e , com as massas de cada valor de .
  3. (6 pts) e são independentes na marginal? E dado ? Prove com números (use e ).
Resolução didática — pontuação por subitem
  1. (4 pts) . Consulta ; evidência e ; ocultas (e a própria permanece como variável de consulta). Só existe uma oculta — a conta é pequena, mas a fatoração precisa estar certa.
  2. (10 pts) Condicione em : e . Como e : = 21/125 (4 pts). Massas por valor de V: ; (4 pts). Soma ✓. Posterior: = 79/112 ≈ 0,7054 (2 pts). Viagem sobe de 0,5 para 0,705: febre e cansaço juntos empurram a gripe, e a gripe é mais provável com viagem.
  3. (6 pts) , enquanto = 13/125, com = 13/50 e = 2/5. Como , não são independentes na marginal — é o efeito da causa comum G. Dado , porém, = 18/25 e = 18/25: iguais, logo independentes condicionadas a G. Leitura formal: G é causa comum, então condicionar bloqueia o caminho; na marginal o caminho está ativo e a dependência aparece.

Checklist. Fatoração de quatro fatores; calculado antes; massas por valor de V separadas; as duas comparações numéricas da independência (produto contra conjunta).

Simulado 2 · bloco 2 · Amostragem · 10 pontos

Peso de verossimilhança com duas evidências

Mesma rede do bloco 1, com evidência e . Oito amostras de :

Amostras fornecidas (a evidência não é sorteada)
#VG
1+v+g
2+v−g
3−v+g
4−v−g
5+v+g
6−v−g
7+v−g
8−v+g
  1. (4 pts) Monte a tabela com o peso de cada amostra.
  2. (3 pts) Estime pela soma de pesos.
  3. (3 pts) Compare com o exato (79/112) e explique por que peso de verossimilhança é preferível à rejeição aqui.
Resolução didática — pontuação por subitem
  1. (4 pts) ; . Amostras 1, 3, 5, 8 têm (peso 0,72); 2, 4, 6, 7 têm (peso 0,03).
  2. (3 pts) Soma total = 3. Peso das amostras com : 1, 2, 5, 7 → = 3/2. Estimativa = 1/2.
  3. (3 pts) Exato: 79/112 ≈ 0,705; a estimativa 0,5 erra por 0,205 com apenas oito amostras e pesos muito desiguais (0,72 contra 0,03). Ainda assim, peso de verossimilhança é melhor que rejeição porque nenhuma amostra é descartada: com evidência conjunta rara, a rejeição aceitaria pouquíssimas amostras e o erro seria maior.

Checklist. Peso definido como verossimilhança da evidência (produto das duas CPTs), não como contagem; numerador e denominador são somas de pesos; comparação numérica com o exato.

Simulado 2 · bloco 3 · Naive Bayes · 10 pontos

Zero count que inverte a decisão

Treino (10 exemplos). Novo exemplo: .

Treino do bloco 3
#a1a2a3classe
1110S
2110S
3110S
4110S
5110S
6110S
7110S
8101N
9011N
10001N
  1. (4 pts) Classifique por máxima verossimilhança (sem suavização) e explique o que o zero faz.
  2. (4 pts) Refaça com suavização de Laplace em atributos e priors, mostrando os dois escores.
  3. (2 pts) A decisão muda? Qual resposta é defensável?
Resolução didática — pontuação por subitem
  1. (4 pts) Priors 7/10 e 3/10. Em S: , , . Escore S = 0. Em N: , , . Escore N = 1/30. Sem suavização, S é “impossível” e N tem posterior 1.
  2. (4 pts) Laplace com : em S, denominador e prior : , , → escore = 128/2187. Em N, denominador e prior : , , → escore = 16/375.
  3. (2 pts) Sim, a decisão inverte: , então a classe passa a ser S, com posterior = 1000/1729 ≈ 0,578. A resposta defensável é a com suavização: o zero era ausência de exemplo, não impossibilidade. A versão sem suavização não deve ser apresentada como probabilidade — ela é um artefato.

Checklist. Declarar a convenção de Laplace (denominador #classe + |X|); mostrar que o zero anula o produto; apresentar os dois escores em fração; comparar e concluir com a inversão.

Simulado 2 · Bloco 4 · MDP · 20 pontos · ~25 min

Três políticas, um empate e um valor finito que engana

Mesma grade de 1 a 5, Jim no 1, Pam no 5, R(d)=45−d, andar rende 0 e funciona com probabilidade p. Considere as políticas, todas a partir de s=1:

  • P1: descansar sempre.
  • P2: andar uma vez e depois descansar para sempre.
  • P3: andar duas vezes e depois descansar para sempre.

(a) [7 pontos] Com γ=0,5 e p=1, calcule o valor das três políticas e ordene-as.

(b) [7 pontos] Ainda com p=1, para qual γ as políticas P2 e P3 empatam? Quem vence acima e abaixo desse valor? Justifique com a razão entre as expressões.

(c) [6 pontos] Com γ=0,5 e p=1, faça duas iterações de valor. Explique por que V2(1) <16, embora P2 valha 16 e não seja ótima.

Abrir resolução — Simulado 2, bloco MDP

(a) [7] Com p=1, andar é determinístico.

  • P1: 41−0,5=8 (recompensa 4 desde t=0).
  • P2: recompensa 0 em t=0 e 16 de t=1 em diante: 0,5⋅161−0,5=16.
  • P3: recompensa 0 em t=0 e 1, e 64 de t=2 em diante: 0,52⋅641−0,5=32.

Ordem: P3 (32) > P2 (16) > P1 (8). O motivo é a razão 4 entre recompensas vizinhas contra o desconto 0,5: cada passo "perdido" custa 0,5 do valor e compra 4 vezes mais recompensa — 4⋅0,5=2>1, então andar compensa.

(b) [7] Em geral, para p=1: VP2=16γ1−γ e VP3=64γ21−γ. Igualando: 64γ2=16γ ⇒γ=1/4 (a raiz γ=0 é degenerada: os dois valores são 0).

A razão VP3/VP2=4γ é a chave: P3 ganha quando 4γ>1 e perde quando 4γ<1. Com γ=0,5 a razão é 2 (confere com 32/16). Note que comparei duas políticas fixas, não a ótima — a política ótima anda até o quadrado 5.

(c) [6] Iteração de valor com V0=0:

  • V1(s)=4s: 4, 16, 64, 256, 1024.
  • V2(s)=max{4s+0,5⋅4s,0,5⋅4s+1}=2⋅4s para s≤4: 8, 32, 128, 512; em s=5, max{1536,512}=1536.

Por que V2(1)=8<16? Porque Vk é o melhor valor com horizonte k: em k=2, a política "andar e descansar" só coleta a recompensa 16 uma vez (0,5⋅16=8), enquanto o valor de P2 soma a cauda infinita (16). Ou seja: um valor de VI com poucas iterações não é um limite superior para o valor de políticas de horizonte infinito — ele cresce até V*. Isso é uma boa frase para escrever na prova: "a tabela de VI é o valor ótimo truncado no horizonte".

Distribuição dos pontos e checklist

  • (a) 7: 5 pelas três somas geométricas (com o atraso correto de cada recompensa) e 2 pela ordenação com explicação.
  • (b) 7: 3 pelas expressões gerais, 2 pela igualdade, 2 pela discussão do sinal (quem vence de cada lado).
  • (c) 6: 3 pela tabela, 3 pela explicação do horizonte truncado.
  • Erro comum: esquecer o γ2 em P3 (a recompensa 64 só começa em t=2).

Simulado 2 · Bloco 5 · Perceptron · 10 pontos · ~12 min

Sete pontos que nenhuma reta separa

Dados (com viés implícito 1): positivos (1,2), (2,3), (3,4); negativos (0,2), (1,3), (2,1), (3,2). Pesos iniciais (−1,1,0), η=1, empate como −, ordem: positivos e depois negativos, como listados.

(a) [5 pontos] Execute duas épocas completas e informe os erros por época e os pesos ao final de cada uma.

(b) [5 pontos] Prove que não existe vetor de pesos que classifique os sete pontos perfeitamente. Use apenas desigualdades.

Abrir resolução — Simulado 2, bloco Perceptron

(a) [5] Época 1, w=(−1,1,0): os três positivos têm z=−x1+x2=1 ⇒ acertos. Os negativos (1,3), (2,1), (3,2) dão z<0 ⇒ acertos. Só (0,2) erra (z=2), e a atualização deixa w=(−1,−1,−1). Erros: 1.

Época 2, w=(−1,−1,−1): (1,2) dá −4 ⇒ erro ⇒ w=(0,1,0); (2,3) e (3,4) acertam (z>0); (0,2) erra ⇒ w=(0,−1,−1); os outros três negativos acertam. Erros: 2. Terceira época repete 2: o processo não zera.

Pesos ao fim das épocas: (−1,−1,−1) e (0,−1,−1); ao fim da terceira, (1,-1,-1) — os negativos (2,1) e (3,2) ficam exatamente sobre a fronteira (z=0), o que mostra por que a convenção de empate precisa estar escrita.

(b) [5] Suponha w=(a,b,c) com classificação perfeita. Então:

  • a+2b+c>0 (positivo) e a+3b+c≤0 (negativo) ⇒ subtraindo, −b>0⇒b<0.
  • 2a+3b+c>0 (positivo) e 2a+b+c≤0 (negativo) ⇒ subtraindo, 2b>0⇒b>0.

Contradição imediata (b<0 e b>0), logo não existe separador. Geometricamente: os positivos estão sobre a reta x2=x1+1 e os negativos aparecem dos dois lados dela.

Observação que vale ponto: a oscilação em (a) é evidência; a prova é (b). E note que um conjunto pode ter erros numa época e ser separável — o contrário (zero erros) é que garante separabilidade.

Distribuição dos pontos e checklist

  • (a) 5: 3 pelas duas épocas com contagem correta, 2 pelos pesos ao fim de cada época.
  • (b) 5: 2 pelas duas primeiras desigualdades, 2 pela segunda subtração, 1 pela conclusão.
  • Escreva w=(a,b,c) deixando claro que c é o viés.

Simulado 2 · Bloco 6 · Redes neurais · 15 pontos · ~18 min

Gradientes com um zero no meio

Rede com d=2, k=3: W1=[[1,0], [0,1],[1,1]], b1=(0,0,−2), W2=(1,1,3), b2=0, x=(1,1), y=3, g(z)=z⊙z, ℒ=12(y−y^)2.

(a) [5 pontos] Faça a ida e calcule ℒ; confirme as formas de W1, z e W2.

(b) [6 pontos] Calcule ∂ℒ/∂W2, ∂ℒ/∂b2, ∂ℒ/∂z, ∂ℒ/∂x, ∂ℒ/∂W1 e ∂ℒ/∂b1.

(c) [4 pontos] Explique por que a terceira linha de W1 e o terceiro elemento de b1 não são atualizados neste passo. A unidade está "morta" para sempre? Justifique.

Abrir resolução — Simulado 2, bloco Redes neurais

(a) [5] W1 é 3×2 (k×d); z=W1x+b1 =(1,1,1+1−2) =(1,1,0); g(z)=(1,1,0); y^=1+1+0=2; ℒ=12(3−2)2=1/2 e δ=-1.

(b) [6]

  • ∂ℒ/∂W2=δg(z)=(-1,-1,0); ∂ℒ/∂b2=-1.
  • ∂ℒ/∂z=2δ(W2⊙z)=−2⋅(1⋅1,1⋅1,3⋅0)= (−2,−2,0).
  • ∂ℒ/∂x=W1⊤(−2,−2,0)=(-2,-2) (pois as colunas de W1⊤ são 1+0 e 0+1).
  • ∂ℒ/∂W1=(−2,−2,0)(1,1)⊤= [[-2,-2], [-2,-2], [0,0]]; ∂ℒ/∂b1=(−2,−2,0).

(c) [4] Porque z3=0 e o gradiente da unidade é 2δW2,3z3=0. Com gradiente zero, a linha 3 de W1 e b1,3 não mudam neste passo. Mas dizer que ela está morta "para sempre" seria errado: os pesos atuais (1,1) com viés −2 só dão zero em entradas com x1+x2=2 — para outras entradas, z3≠0 e o gradiente é não nulo. Ela ficaria morta para todas as entradas só se W1,3⋅=0 e b1,3=0 — aí sim o gradiente é zero sempre e a unidade nunca sai de z=0.

Distribuição dos pontos e checklist

  • (a) 5: 2 pelo forward, 1 pelas formas, 2 por ℒ e δ.
  • (b) 6: 1 por ∂ℒ/∂W2, 1 por ∂ℒ/∂b2, 2 por ∂ℒ/∂z e ∂ℒ/∂x, 2 por ∂ℒ/∂W1 e ∂ℒ/∂b1 (a linha de zeros precisa aparecer).
  • (c) 4: 2 pela explicação do gradiente nulo, 2 pela distinção entre "inativa nesta entrada" e "morta sempre".

Simulado 2 · bloco 4 · Árvores de decisão · 15 pontos

Empate entre atributos e o viés do ganho

Treino (10 exemplos). X e Y são binários; Z tem três valores
#XYZclasse
111asim
211asim
311bnão
410bsim
510bnão
601bsim
701cnão
800csim
900cnão
1000cnão
  1. (3 pts) Calcule a entropia inicial H(S).
  2. (4 pts) Calcule o ganho de informação de X e de Y. O que o empate permite concluir?
  3. (5 pts) Para Z, calcule o ganho de informação, a informação da divisão e a razão entre os dois.
  4. (3 pts) Qual atributo você colocaria na raiz? Justifique considerando o viés.
Resolução didática — pontuação por subitem
  1. (3 pts) Sim nos exemplos 1, 2, 4, 6, 8 (5) e não em 3, 5, 7, 9, 10 (5) → bit = 1.000000.
  2. (4 pts) X: (1 a 5) → 3 sim, 2 não, H = 0,970951; (6 a 10) → 2 sim, 3 não, H = 0,970951. Resto 0,970951; ganho = 0.029049. Y tem exatamente a mesma tabela de contingência (5 exemplos com 3 sim/2 não e 5 com 2 sim/3 não) → ganho = 0.029049. Conclusão: empate exato — os dois atributos carregam a mesma informação sobre a classe; escolher um deles exige critério de desempate declarado, não intuição.
  3. (5 pts) Z: a → 2 exemplos, ambos sim (H = 0, peso 2/10); b → 4 exemplos, 2 sim e 2 não (H = 1, peso 4/10); c → 4 exemplos, 1 sim e 3 não (H = 0,811278, peso 4/10). Resto ; ganho = 0.275489. Informação de divisão: = 1.521928. Ganho de razão = 0.181013.
  4. (3 pts) Critério do enunciado (ganho puro): Z (0,2755 contra 0,0290) — 1,5 ponto. Mas Z tem três valores e fatia os dados em ramos menores; parte do ganho vem da fragmentação. O ganho de razão corrige isso e ainda favorece Z (0,181 contra 0,029), então a escolha é robusta aqui — 1,5 ponto. Resposta completa: Z na raiz, com a ressalva do viés e a comparação pelo ganho de razão.

Checklist. , os três ganhos, a informação de divisão e o ganho de razão; menção explícita ao empate X/Y; justificativa do viés em uma frase.

Folha de revisão

  • Bayes exato: escreva um fator por nó; some sobre as variáveis que não são observadas nem pedidas; divida pela probabilidade da evidência. Se ela for zero, o posterior não está definido.
  • Rejeição: divida os acertos entre aceitas pelo número de aceitas. Sem aceitas não há estimativa.
  • Naive Bayes: multiplique a probabilidade inicial da classe pelas probabilidades dos atributos dentro dela. Compare os produtos; divida pela soma se a questão pedir o posterior.
  • MDP: retorno = r₀ + γr₁ + γ²r₂ + … . Calcule a média sobre os sucessores para cada ação; só depois compare as ações. Na iteração de valor síncrona, leia somente a rodada anterior. Na iteração de política, avalie antes de melhorar.
  • Perceptron: calcule o produto escalar dos pesos pela entrada com um 1 para o viés. Em caso de erro, some η vezes o rótulo vezes essa entrada. Declare como trata o zero. Uma época com erro não prova que nenhuma reta separa os dados.
  • Rede quadrática: em A-Q3, z = W₁x. Na volta, a derivada do quadrado é 2z, componente por componente. Confira se cada gradiente tem o mesmo formato que a grandeza derivada.
  • Árvore: ganho = entropia inicial menos a média das entropias dos ramos, ponderada pela quantidade de exemplos em cada ramo. Use logaritmo na base 2 e adote 0 log₂ 0 = 0.

Antes de entregar: escrevi a convenção? Substituí os dados na fórmula? Mostrei as contas? Conferi sinais, dimensões, denominadores e empates? Respondi a todos os subitens?

Revisão separada: busca e jogos

Consultar somente depois da trilha principal

BFS prioriza profundidade; custo uniforme prioriza custo acumulado; A* combina custo acumulado e estimativa restante. Em minimax use máximo/mínimo; em expectimax, nós de acaso usam média ponderada. Alfa-beta poda sem mudar o valor minimax.

Fontes e convenções

Provas originais: A — Documento sem título.pdf, páginas físicas 1–3; B — prova2.pdf, páginas físicas 1–2. As resoluções são próprias, não gabaritos oficiais; treinos e simulados são autorais.

Referência complementar: CS188 — Berkeley, calendário Summer 2025. Aulas 8–9 (MDP), 12–15 (probabilidade, representação, independência e inferência), 16 (amostragem), 21 (Naive Bayes), 22 (perceptron), 23 (redes neurais) e 24 (árvores). Não há evidência de que a professora usou esta edição.

Consulta técnica: probabilidade e aprendizado · MDP, redes e perceptron. Frações exatas até a aproximação decimal; entropia em bits; vetores coluna e bias explícito. Em MDP, recompensa imediata no instante zero e VI síncrona. Quando a questão não fixa, perceptron com rótulos ±1, η=1 e score zero negativo. São convenções desta apostila, não atribuições à professora.