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.
Nenhum resultado nos módulos e questões.
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.
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 P(passa): somei a coluna e joguei fora a informação “estudou”. A condicional P(passa | estudou) 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ímbolo
Lê-se
Significado operacional
probabilidade de A
fração dos casos em que A acontece
probabilidade conjunta
fração em que A e B acontecem juntos (uma célula)
A dado B
célula dividida pela linha/coluna de B escolhida como universo
alfa
fator 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, aproximadamente
P̂ é calculada a partir de amostras; 1/3 ≈ 0,333 indica um arredondamento.
√, argmax
raiz quadrada, opção de maior valor
√9 = 3. Se A vale 2 e B vale 5, o argmax é B; o máximo é 5.
A segunda igualdade é o teorema de Bayes: ela só troca a condicional de lado multiplicando a verossimilhança P(B | A) pelo prior P(A). O denominador P(B) é 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
Nomeie as variáveis e os valores (+a e −a para binárias). Sem isso, o denominador é escolhido por acidente.
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.
Escreva a conjunta como produto de condicionais, da causa para o efeito (regra do produto). Cada termo tem que ser uma entrada de tabela.
Some o que você não quer (marginalize). Somar uma variável é apagá-la da tabela.
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)
Grupo
passa
não passa
total
estudou
45
15
60
não estudou
10
30
40
total
55
45
100
Conjunta (estudou e passou): = 45/100.
Marginal passar: = (45+10)/100. Somei a coluna inteira; “estudou” desapareceu.
Condicional passar dado que estudou: = 45/60. Universo = linha “estudou”.
Condicional invertida ter estudado dado que passou: = 45/55. Universo = coluna “passa”. Note 3/4 ≠ 9/11: condicional não é simétrica.
Entre quem não estudou, 10 dos 40 passaram: 10/40 = . Compare com os 3/4 entre quem estudou. A tabela mostra uma associação; sozinha, não prova a causa.
Conferência das quatro células: , 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 P(estudou | passou) = P(passou | estudou)·P(estudou)/P(passou) = (3/4 · 3/5)/(11/20) = (9/20)/(11/20) = 9/11. A taxa base P(estudou) = 3/5 é o que impede a resposta de ser 3/4.
Erros que custam ponto
Trocar o denominador.P(A|B) divide por P(B), não por P(A). 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 P(+c | −t) 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 P(+b | +e) 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.
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 P(nó | pais). 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.
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 C tem dois filhos (S e D) e que T 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:
Contagem de números livres. Binárias: P(A) e P(C) custam 1 número cada; P(S|A,C) tem 4 linhas de pais, logo 4 números; P(D|C) custa 2; P(T|S,D) custa 4. Total , contra 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
Termo
Definição
Como aparece na conta
CPT
tabela de probabilidade condicional de um nó dados os pais
uma linha por combinação de pais; a linha soma 1
raiz
nó sem pais
entra como prior P(X)
fator
tabela sobre um conjunto de variáveis
produto e soma operam sobre fatores
caminho ativo
caminho que transporta dependência dada a evidência
se todos os caminhos estão bloqueados, há d-separação
Receita: atacar qualquer questão de rede
Transcreva as arestas a partir das CPTs (quem é pai de quem). Sem isso, a fatoração sai errada e todo o resto também.
Escreva a fatoração como produto de um termo por nó. É a etapa que a correção procura primeiro.
Marque consulta, evidência e ocultas no grafo. Ocultas são as que serão somadas.
Instancie a evidência nas tabelas: a linha da evidência vira número fixo, não variável.
Escolha o método: enumeração (poucas ocultas), eliminação (muitas), amostragem (rede grande ou pergunta sobre estimativa).
Normalize no fim sobre os valores da consulta.
Exemplo pequeno: duas variáveis, conta completa
Rede de brinquedo: A (alarme tocou) e S (vizinho saiu de casa), com A → S. Dados: P(+a) = 3/4, P(+s | +a) = 9/10, P(+s | −a) = 2/10. Pergunta: P(+a | +s).
Fatoração: P(a,s) = P(a)P(s|a).
Marginalizar A para obter o denominador: P(+s) = (3/4)(9/10) + (1/4)(2/10) = 27/40 + 2/40 = 29/40 = .
Numerador: P(+a,+s) = 27/40.
Posterior: P(+a|+s) = (27/40)/(29/40) = 27/29 = , isto é, o alarme sobe de 3/4 = 0,75 para 0,931.
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.
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.
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 é P(filho | pais), nunca P(pai | filho).
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 P(A) 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.
Enumeração soma todas as ocultas de uma vez: para k ocultas binárias, são 2^k 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.
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
Termo
Definição
Exemplo do módulo
fator
tabela indexada por um conjunto de variáveis
g(R) = P(+w|R)
produto
para cada combinação de valores, multiplique as entradas compatíveis dos fatores
h(C,R) = P(R|C)·g(R)
soma
elimina uma variável somando todas as suas entradas
f(C) = Σ_r h(C,r)
maior fator
fator intermediário com mais entradas — mede o custo
aqui, 4 entradas
Receita: eliminação em cinco passos
Liste os fatores iniciais (um por CPT) e restrinja cada um à evidência: linhas incompatíveis viram zero e podem sair.
Escolha a ordem começando pela variável oculta que aparece em menos fatores. A ordem não muda o resultado, só o custo.
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.
Some a variável do fator resultante. Por que somar: você quer a massa independente do valor dela — é a definição de marginalização.
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)
Etapa 1 — fatorar. Rede C → R → W (chuva, rua molhada, grama molhada): P(c,r,w) = P(c)P(r|c)P(w|r). Consulta P(+c | +w); oculta R.
Etapa 2 — restringir a evidência.P(+w|R) vira o fator g(+r) = 9/10, g(−r) = 1/10. A coluna −w não interessa mais.
Dados do exemplo (chuva, rua molhada, grama molhada)
Distribuição
valores
P(+c) / P(−c)
2/5 e 3/5
P(+r | +c) / P(−r | +c)
4/5 e 1/5
P(+r | −c) / P(−r | −c)
1/5 e 4/5
P(+w | +r) / P(+w | −r)
9/10 e 1/10
Contas, na ordem da figura: h(+c,+r) = 18/25 = ; h(+c,−r) = 1/50 = ; f(+c) = 37/50 = ; f(−c) = 13/50 = . Aplicando os priors: P(+c)f(+c) = 37/125 = e P(−c)f(−c) = 39/250 = . Normalizando: P(+c|+w) = 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 r diretamente: P(+c,+w) = (2/5)[(4/5)(9/10) + (1/5)(1/10)] = (2/5)(37/50) = 37/125. 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.
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.
Figura 4.1 — Rejeição passo a passo com oito amostras. As três linhas vermelhas são descartadas porque a evidência é +w; 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 +c: 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 (+w 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étodo
Fórmula
Quando usar
rejeição
P̂(q|e) = #(q ∧ e aceitas) / #(e aceitas)
evidência comum, poucas variáveis
peso de verossimilhança
P̂(q|e) = Σ w_i [q] / Σ w_i, w_i = P(e | pais de e)
evidência rara; não descarta amostras
prior (sem evidência)
P̂(q) = #(q)/n
pergunta marginal
Receita: rejeição em cinco passos
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.
Sorteie cada nó pela sua CPT, condicionando nos valores já sorteados dos pais.
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.
Conte as aceitas (denominador) e, entre elas, as que têm o valor da consulta (numerador).
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 C → R → W com os mesmos números do módulo de eliminação (P(+c) = 2/5, P(+r|+c) = 4/5, P(+w|+r) = 9/10). Consulta P(+c | +w), agora estimada por rejeição.
Amostras aceitas (coluna +w): 1, 3, 6, 7, 8 → .
Entre as aceitas, com +c: 1, 6, 8 → .
Estimativa: = 0,6.
Valor exato (eliminação): ≈ 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 1/√n; 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 w = P(e | pais de e). A estimativa é a média dos pesos, não a contagem simples.
Exemplo: rede C → R, evidência +r, consulta P(+c | +r). Sorteie só C: amostras +c, +c, −c, +c com pesos 4/5, 4/5, 1/5, 4/5. Soma dos pesos 13/5; peso das amostras com +c = 12/5; estimativa 12/13 ≈ 0,923. O valor exato é P(+c,+r)/P(+r) = (2/5·4/5)/(11/25) = 8/11 ≈ 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 +e, 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.
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: P(y) = #(y)/N e P(x_i | y) = #(x_i ∧ y)/#(y). Classificar é comparar P(y)·∏ P(x_i|y) 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.
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ímbolo
Significado
Como calcular
P(y)
prior da classe
#(y)/N
P(x_i | y)
verossimilhança do atributo na classe
#(x_i ∧ y)/#(y)
escore(y)
produto não normalizado
P(y)∏P(x_i|y)
P(y|x)
posterior
escore(y)/Σ escore
Laplace
suavização add-1
(#(x_i∧y)+1)/(#(y)+|X_i|)
Receita: classificar em cinco passos
Conte as classes (prior) e, dentro de cada classe, cada valor de cada atributo. Monte a tabela de contagens antes de qualquer conta.
Calcule as verossimilhanças dividindo pela contagem da classe — nunca pelo total de exemplos. Por que: a pergunta é “dentro da classe y”.
Multiplique prior e verossimilhanças do novo exemplo em cada classe. Por que multiplicar: é a hipótese de independência condicional aplicada ao produto.
Compare os escores e escolha o maior; empate é empate (declare a convenção, por exemplo a classe de menor índice).
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: G = contém “grátis” (1/0); R = contém “reunião” (1/0). Classe: S spam, N normal. Novo e-mail: G = 1, R = 0.
Dados de treino (6 exemplos)
#
G
R
classe
1
1
1
S
2
1
0
S
3
0
1
N
4
1
0
N
5
0
0
N
6
0
1
N
Priors: P(S) = 2/6 = 1/3 = e P(N) = 4/6 = 2/3 = .
Verossimilhanças na classe S (exemplos 1 e 2): P(G=1|S) = 2/2 = 1 = ; P(R=0|S) = 1/2 = .
Na classe N (exemplos 3 a 6): P(G=1|N) = 1/4 = ; P(R=0|N) = 2/4 = 1/2 = .
Escores: S = (1/3)(1)(1/2) = 1/6 = ; N = (2/3)(1/4)(1/2) = 1/12 = .
Posterior: P(S|x) = (1/6)/(1/6+1/12) = 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 P(G=1|S) = 1 contra 1/4 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 G=1, então P(G=1|N) = 0 e o escore de N seria 0 — o modelo diria “impossível”, não “improvável”. A suavização de Laplace troca 0/(4) por (0+1)/(4+2) = 1/6 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.
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ímbolo
Nome
Leitura em português
estados
o conjunto de situações em que o agente pode estar
ações
o que se pode fazer estando em
transição
probabilidade de terminar em depois de fazer em
recompensa
o que se ganha naquele passo (não é o total)
desconto
quanto vale hoje uma recompensa de amanhã;
política
função que diz qual ação tomar em cada estado
valor da política
soma esperada de recompensas descontadas começando em e seguindo
valor da ação
o mesmo, mas forçando a primeira ação a ser
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
tem apenas três argumentos.
Normalização: para cada par ,
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
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
Liste os estados e escreva o que cada um significa. Se a recompensa depende da distância
, converta: implica
.
Por quê: usar diretamente inverte a escala e produz 256 no início.
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.
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.
Declare a recompensa como
ou ,
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.
Declare o horizonte e o desconto (infinito? terminal? ).
Por quê: sem e sem terminal, a soma pode divergir.
Só então escreva ou
.
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.
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:
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 .
Zere todos os estados: .
Estado terminal fica 0 para sempre e não entra no .
Para cada estado, calcule o valor de cada ação: recompensa imediata + vezes
a média dos valores anteriores dos destinos, ponderada por .
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".
Repita até os valores pararem de mudar (ou pelo número de iterações pedido).
No fim, extraia a política: .
Receita 3 — iteração de política (PI)
Em vez de varrer valores, PI aposta numa política e melhora. Dois passos alternados:
Avaliar a política atual resolvendo as equações de esperança — sem :
.
Melhorar: para cada estado, escolha a ação que maximiza
com o que você acabou de calcular.
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 ;
iteração de valor e melhoria de política têm. Se você colocar 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 ,
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 .
Modelo do exemplo: duas ações, dois estados
Estado
Ação
Destino (prob.)
Recompensa
M (mesa)
estudar
M (1,0)
2
M (mesa)
descansar
S (1,0)
0
S (sofá)
estudar
M (1,0)
1
S (sofá)
descansar
S (1,0)
3
Passo a passo da iteração de valor neste exemplo (5 etapas)
Etapa 1 — ponto de partida.
e . Sem valores futuros,
cada estado vale apenas a recompensa imediata da melhor ação.
;
.
Etapa 2 — o futuro começa a contar. Agora usar
como "o que vem depois". Note que o destino depende da ação: descansar em M leva a S, cujo valor é 3.
Etapa 3 — continue.
;
.
Os valores sobem, mas cada vez menos: o desconto amortece.
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
e .
Resolvendo cada autorreferência:
e .
Etapa 5 — conferir se essa política é mesmo ótima. Em M, descansar valeria
.
Em S, estudar valeria .
Nenhuma troca melhora, então
e .
Iteração de valor no exemplo (síncrona, )
Estado
M (mesa)
0
3,5
S (sofá)
0
5,25
A coluna 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.
Este é o desenho que explica a equação de Bellman: cada ação abre um leque de
destinos com pesos . 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 )
Política inicial: descansar sempre, .
Logo e
.
Passo B — melhorar (com )
Em M: estudar dá ;
descansar dá ⇒ estudar.
Em S: estudar dá ;
descansar dá ⇒ descansar.
Nova política .
Repetindo o passo A com ela, sai 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
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:
e .
Na tabela, significa estudar na mesa (M) e
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
.
O roteiro de resolução é o seguinte, e cada item usa uma receita diferente:
Item (a) — comparar duas políticas em com
: use a soma geométrica em cada política e resolva a
inequação em . O critério final é
(empate em ).
Item (b) — mesma comparação com , agora isolando
: dá .
Item (d) — duas rodadas de PI partindo de
(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
Erro
Como perceber sozinho
Usar em vez de
no início () você obteria 256, mas o enunciado dá
Somar em vez de tomar entre ações
o valor do estado sairia maior que qualquer ação isolada; teste um estado com ação obviamente ruim
Colocar 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 não bate com nenhuma iteração síncrona
Comparar políticas em estados diferentes
escreva "a partir de " 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 soma 1.
(2) Todo novo é maior ou igual ao anterior quando
e as recompensas são positivas — se caiu, há erro de sinal. (3) A política final, avaliada, satisfaz
:
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
.
Para quaisquer dois vetores e ,
,
porque o não aumenta distâncias e a média ponderada também não. Como
, existe um único ponto fixo (teorema de Banach) e
.
Sem (ou sem terminal) o fator seria 1 e nada garante convergência.
Melhoria de política. Seja gulosa em relação a
. Então .
Separando o primeiro passo e iterando,
,
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 (
por iteração); PI faz poucas iterações caras (resolver um sistema ).
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ímbolo
Significado
Detalhe que vale ponto
entrada com o termo de viés
o no fim é o que permite deslocar a reta
pesos
é o viés (bias), não a primeira característica
escore
quanto maior, mais "positivo" o ponto é
previsão
declare o que acontece em
taxa de aprendizado
no perceptron clássico costuma ser 1
O que uma atualização faz com a reta
Leitura orientada. No painel da esquerda, a reta inicial erra o ponto
positivo. A atualização soma
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
, que separa os rótulos neste exemplo.
Receita — treinar um perceptron à mão
Declare a convenção: rótulos em
(ou ), limiar em
(ou ) 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.
Monte a tabela com colunas ,
, , rótulo, e deixe espaço para
, , "erro?" e "pesos novos".
Para cada exemplo, calcule .
Se acertou, não mexa nos pesos. Se errou, atualize:
(rótulos )
ou
(rótulos ).
Por quê: somar aumenta o escore do ponto quando ele é positivo e diminui quando é negativo; é o mínimo necessário para consertar aquele erro.
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.
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: ,
empate () conta como , ,
e a atualização é . Pesos iniciais
(na ordem ).
Uma época completa: quatro pontos, dois erros, duas atualizações
Fim da época: erros. Nova época com
:
escores 2, 1, −3, −1 ⇒ erros. Os pesos finais são
e as margens são
, ,
e — 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
erros, com o maior comprimento de vetor de entrada e
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
Leitura orientada. O desenho não é a prova, mas mostra onde ela nasce:
os positivos estão sobre a reta
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
teria de satisfazer (com o viés). Para os dados da prova:
positivos e
negativos :
(ponto positivo)
e (ponto negativo) — subtraindo,
dá .
e
— subtraindo,
dá .
e
— subtraindo,
dá , e com
isso força .
Mas a primeira linha dá : contradição. Logo não existe separador.
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 , 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
Erro
Como perceber
Não declarar a convenção de rótulos, limiar ou empate
a correção não consegue reproduzir seus pesos
Atualizar quando acertou
o peso muda e o escore do ponto já correto fica pior
Trocar a ordem dos pesos
com o viés no fim; escreva isso na folha
Concluir não separabilidade por uma época
rode 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 escore
margem é ; a cota do teorema usa a margem geométrica (distância)
Conferência rápida: depois de treinar, calcule 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
, uma camada escondida com ativação
quadrática
(quadrado componente a componente) e saída escalar. Sem funções de ativação "de biblioteca": aqui é só o quadrado.
Contabilidade de dimensões — o item (a) da prova é exatamente esta tabela
Grandeza
Forma
Por que
dado do problema: características
para existir, o número de colunas tem de ser
com
mesma de
ativação elemento a elemento não muda a forma
é ; para o produto dar escalar, precisa ter entradas
escalares
a saída é um número real
Conclusão que a prova quer, em uma linha:
(número de neurônios escondidos, igual ao número de pesos de saída) e
(dimensão da entrada).
Note que é , e não
: é a ordem que faz o produto existir.
Receita 1 — ida (forward)
Leitura orientada. Siga as formas da esquerda para a direita: a matriz
"achata" a entrada de para
valores; a ativação quadrática só eleva cada um ao quadrado; e
combina esses números em um único escore.
A perda é a distância ao quadrado entre esse escore e o valor verdadeiro .
Verifique as formas antes de multiplicar. é
, então é
. Por quê: 90% dos erros de conta em prova vêm de multiplicar matrizes incompatíveis.
Aplique a ativação componente a componente:
eleva cada entrada ao quadrado. Por quê: a derivada dessa etapa será , e é aí que a maioria deixa na resposta.
Calcule a saída como produto interno: .
Calcule a perda e, de brinde, o "erro assinado" .
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: , ,
, ,
com , e .
Ida: ,
, ,
.
Erro assinado: .
Negativo porque a previsão ficou abaixo do alvo — e o gradiente vai empurrar os pesos para aumentar .
Gradiente do peso de saída: .
Gradiente na entrada da ativação: .
Aqui já foi substituída: era isso que o enunciado proibia deixar simbólico.
Gradiente do peso de entrada: .
Gradiente na entrada (para propagar a outra camada): .
Conferência por diferenças finitas (o teste que você pode fazer na calculadora):
aumentando em e diminuindo na mesma
quantidade, a razão
vale , praticamente o gradiente exato .
Se a sua conta de backprop discordar disso, a conta está errada.
Receita 2 — volta (backprop)
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
; multiplicar por e por
para voltar a ; multiplicar por
para chegar em .
Cada gradiente tem a forma da grandeza que ele afeta: vetor para , matriz para
. Se a forma não bate, a conta está errada.
As quatro regras, com o motivo de cada uma:
:
derivada da perda em relação à previsão. Por quê: derivada em dá (o ½ cancela o 2).
"vê" :
o gradiente é . Por quê: , então a derivada em é .
Volte por : cada componente recebe .
Para a ativação quadrática, — substitua, não deixe símbolo.
Por quê: é a regra da cadeia, e o fator vem do expoente 2 da ativação.
Chegue em com
e em com o produto externo .
Por quê: é ; o produto externo de um vetor por um vetor tem exatamente essa forma.
Exemplo vetorial resolvido
Mesma arquitetura, com ,
,
,
, .
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
Ida: ;
;
;
.
Erro: .
Saída: .
Camada escondida: .
Entrada: .
Pesos da primeira camada: .
Teste de descida: atualize só W₂, mantendo W₁ fixo, com :
.
Recalculando,
e , menor que 2: a perda caiu.
A fórmula geral que a prova pede
Com , a derivada da ativação é
. Substituindo nas
quatro regras e escrevendo tudo com as grandezas que o enunciado permite:
Em coordenadas, para quem preferir sem matrizes:
Note que nenhuma das duas expressões contém :
a derivada já foi absorvida. Era exatamente isso que o enunciado exigia —
deixar simbólico conta como resposta incompleta.
Onde isso aparece na prova
A Questão 3 da Prova A dá
e e pede:
(a) e em termos de
e ; (b)
e 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
— isso resolve (b).
Erros típicos e como conferir
Erro
Como detectar antes de entregar
Deixar na resposta
o enunciado proíbe; substitua por
Trocar por
a forma de precisa ser
Esquecer o fator 2 da ativação quadrática
diferenças finitas denunciam imediatamente
Inverter o sinal de
; com ,
Dizer que
teste com números: é , então
Usar grande e concluir que "desceu" sem conferir
recalcule 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 ,
cada unidade escondida contribui com ,
isto é, uma forma quadrática em . Somando, a saída é
com
(simétrica, de posto no máximo ). Consequências que valem ponto numa discussão:
Sem viés e sem termo linear, a rede não representa
nem uma constante diferente de zero (com , a saída é sempre 0).
Representa bem funções quadráticas — inclusive .
Se , então ,
e
:
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 é H(antes) − média ponderada de H(depois), 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.
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ímbolo
Significado
Unidade
H(S)
entropia da distribuição de classes
bits
H(S|A)
entropia média depois de dividir por A
bits
Ganho(A)
H(S) − H(S|A)
bits
|S_v|/|S|
peso do ramo v
adimensional
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.
Conte a coluna alvo e calcule H(S). Sem esse número você não tem contra o que comparar.
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.
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.
Subtraia de H(S) para obter o ganho de cada atributo candidato.
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).
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 = .
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 = .
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 H(S); 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 H(S).
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 H(S).
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 H(S), 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.
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 — P(C = +c | T = −t) 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: A = conjunto de alarmes; S = dorme demais; D = papai está atrasado; C = combate ao crime na noite; T = chega na hora. Arestas da figura: A→S, C→S, C→D, S→T, D→T. Pedido: “Calcule P(C=+c / T=−t) usando eliminação de variáveis.”
P(S | A, C) — transcrita da prova
A
C
S
P(S | A,C)
+a
+c
+s
11/16
+a
+c
−s
5/16
+a
−c
+s
1/8
+a
−c
−s
7/8
−a
+c
+s
9/10
−a
+c
−s
1/10
−a
−c
+s
1/5
−a
−c
−s
4/5
P(T | S, D) — transcrita da prova
T
D
S
P(T | S,D)
+t
+d
+s
1/20
+t
+d
−s
2/5
+t
−d
+s
1/5
+t
−d
−s
1
−t
+d
+s
19/20
−t
+d
−s
3/5
−t
−d
+s
4/5
−t
−d
−s
0
P(D | C) — terceira tabela impressa na prova
C
D
P(D | C)
+c
+d
1/4
+c
−d
3/4
−c
+d
0
−c
−d
1
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)
C
P(C)
A
P(A)
−c
4/5
−a
1/4
+c
1/5
+a
3/4
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 é T = −t; a consulta é C = +c. As quatro tabelas acima são as do enunciado, incluindo P(D|C) — a tabela do meio, que é indispensável e está impressa na prova; a resolução numérica abaixo usa P(+d|+c) = 1/4 e P(+d|−c) = 0. 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 u = P(+d|+c) e v = P(+d|−c), para o caso de a cópia da prova chegar ilegível.
Fórmula.
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.
Instancie a evidência.P(−t | S, D) vira o fator g(S,D) com 19/20, 3/5, 4/5 e 0 (tabela da esquerda na figura).
Multiplique por P(D|+c) e some D. Para S = +s: (19/20)(1/4) + (4/5)(3/4) = 19/80 + 3/5 = 67/80 = . Para S = −s: (3/5)(1/4) + 0·(3/4) = 3/20 = . Esse é o fator f_6(+c, S); D foi eliminado.
Multiplique por P(S|A,+c) e some S, mantendo A: para +a, (11/16)(67/80) + (5/16)(3/20) = 737/1280 + 60/1280 = 797/1280 = . Para −a, (9/10)(67/80) + (1/10)(3/20) = 603/800 + 12/800 = 615/800 = 123/160 = . S foi eliminado.
Pese pelos priors de A e pelo prior de C:P(+c)[(3/4)(797/1280) + (1/4)(123/160)] = (1/5)(2391/5120 + 984/5120) = (1/5)(3375/5120) = 675/5120 = 135/1024 = . A foi eliminado.
Repita para C = −c. Agora P(+d|−c) = 0 e P(−d|−c) = 1: f_6(−c,+s) = (19/20)(0) + (4/5)(1) = 4/5 = e f_6(−c,−s) = (3/5)(0) + 0·(1) = 0 = . Com as CPTs de S para −c: +a → (1/8)(4/5) = 1/10 = e −a → (1/5)(4/5) = 4/25 = . Ponderando: (4/5)[(3/4)(1/10) + (1/4)(4/25)] = (4/5)(3/40 + 1/25) = (4/5)(23/200) = 23/250 = .
Leitura do resultado. O prior de +c é pequeno (1/5), mas a evidência de atraso favorece +c por dois caminhos: P(+d|+c) = 1/4 contra P(+d|−c) = 0, e P(−t|+d,+s) = 19/20, alto quando o papai está atrasado. Ainda assim o atraso é mais provável com S = −s e D = −d, e nesse canto P(−t|−s,−d) = 0: a massa que sobra é pequena, o que explica o denominador 28651/128000 ≈ 0,224. O efeito final é P(+c|−t) ≈ 0,589 contra o prior 0,2 — uma subida forte, mas longe de certeza.
Forma simbólica em u = P(+d|+c) e v = P(+d|−c)
Com P(−d|+c) = 1−u e P(−d|−c) = 1−v:
Levando isso às somas sobre S e A e depois normalizando, obtém-se
Conferências: com u = 1/4 e v = 0 (valores impressos) o numerador é 3792 + 1707/4 = 16875/4 e o denominador 6736 + 1707/4 = 28651/4, reproduzindo 16875/28651. Com outro par, u = 1/2 e v = 1/4, a mesma fórmula dá . 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 {A, S, D}.
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.
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 e falha com probabilidade ;
quando falha, Jim fica no mesmo lugar, e a ação tem recompensa 0. O descanso sempre funciona e proporciona
,
onde é a distância entre Jim e Pam. Por exemplo, no início ;
se Jim decide parar, recebe .
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
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 e razão
é .)
b) Agora, suponha que . Ainda assumindo que Jim
começa no quadrado 1, para quais valores de desconto a Política 1 é superior à Política 2?
c) Assuma e .
Faça 2 iterações de Iteração de Valor.
States
0
0
0
0
0
(a preencher)
(a preencher)
d) Assuma e .
Realize duas iterações de iteração de política para os seguintes locais de Jim.
States
right
rest
rest
rest
rest
(a preencher)
(a preencher)
(a preencher)
(a preencher)
Abrir resolução didática — A-Q2 (não é gabarito oficial)
Hipóteses e convenções declaradas
Estados ;
a recompensa depende só do estado e da ação:
(pois ) e .
Transições: ;
,
para ; em 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 a Política 1 supera a Política 2, com ?
Contas, etapa por etapa
Política 1 (descansar sempre). A recompensa é constante e começa em :
.
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 e em 1 com
probabilidade ; a partir daí descansa para sempre. Por isso:
.
O fator
é o que transforma a soma a partir de em "o valor da recompensa
vezes 1".
Comparação:
.
Resposta: a Política 1 é superior para ; em
as duas valem 8 (empate); para
mover vale mais a pena.
Interpretação. Mover troca 4 de recompensa certa (descansar agora) por uma chance
de valer 16 a partir do passo seguinte, além de abrir mão de 4. A comparação exata é
: os 8 do "descansar sempre"
só ganham enquanto o acréscimo esperado não supera os 4 de diferença, ou
seja, enquanto .
(b) Com , para quais a Política 1 supera a 2?
Com o movimento é determinístico. A Política 1 vale
e a Política 2 vale
(a recompensa 16 só começa no instante 1, daí o fator ).
.
Resposta: ; em
empatam. Vale escrever que com e horizonte infinito as duas políticas
têm valor infinito — a comparação só faz sentido com .
Se os dois parâmetros variarem: para e com 0 ≤ p ≤ 1 e 0 ≤ γ < 1,
,
logo .
Conferindo: dá
(item a) e dá (item b).
(c) Duas iterações de valor (, )
Fórmula declarada, com :
Cálculo da primeira e da segunda iteração
Iteração 1 ():
.
É a recompensa imediata, sem futuro.
Iteração 2, estado por estado. Note que em
a ação right leva a 5 (não existe 6), por isso o valor de right é .
Descansar vale 1536; mover vale 512. Escolha descansar, sem empate.
Tabela final (o formato que a prova pede):
States
2
3
4
5
0
0
0
0
0
Conferência que impressiona: para ,
:
cada iteração dobra o valor, porque "andar" busca o vizinho e o fator
aparece. Em não há para onde andar e o valor vem de descansar
(), por isso .
(d) Duas iterações de política (, )
Avaliação, melhoria, avaliação — com as equações
Avaliação de .
Sem , equações de esperança:
;
;
;
;
.
Cada autorreferência dá
: então ,
, ,
e
.
Melhoria. Para cada estado, compare
com o calculado. Em , right fica em 5:
e ⇒ rest.
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.
e seu valor
States
1
2
3
4
5
right
rest
rest
rest
rest
Melhoria de política: de cada ação
Estado
Nova ação
1
right
2
right
3
right
4
right
5
rest
Logo
(a quinta coluna é ).
Avaliação de e segunda melhoria
Avaliar
(andar até 4, descansar em 5):
,
,
,
,
.
Voltando: ,
,
,
.
Melhorar de novo. Em :
rest
e right
⇒ right continua. Em :
rest e
right ⇒ rest.
Nos estados 1 a 3 as comparações também mantêm right
(
contra , por exemplo).
Parada: . Então
e "andar até o 5, depois descansar".
Resultado do item (d)
States
1
2
3
4
5
right
rest
rest
rest
rest
Verificação de otimalidade (fecha a resposta): com
, em descansar valeria
e em andar valeria .
Nenhuma troca isolada melhora, logo a política é ótima.
O que escrever na prova (checklist)
O modelo: , , , ,
, horizonte infinito, sem terminal — e a conversão .
Em (a) e (b): a soma geométrica escrita antes de substituir, e a comparação “a partir de ”.
Em (c): fórmula de VI com , tabela e a observação de que em right fica em 5.
Em (d): equações de avaliação sem , tabela de 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.
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 é e a saída é um
número real . Temos 2 matrizes de pesos:
e , onde
são números conhecidos e você precisa determinar os valores de
e . Considere:
;
com uma função quadrática de ativação
(exemplo: )
e função de perda .
a) Quais os valores de e
? Você pode escrever os valores em termos de
e .
b) Calcule a derivada da função de perda em relação às seguintes grandezas:
e . Sua resposta NÃO deve
incluir a função de ativação (ou seja, você precisa calcular explicitamente a derivada em vez de escrever
). Mas pode incluir
e .
Abrir resolução didática — A-Q3 (não é gabarito oficial)
(a) e
A resposta formal é uma cadeia de dimensões, não um palpite:
é . Para
existir, o número de colunas de tem de ser
⇒ .
Então tem
linhas, isto é, ; a ativação
é elemento a elemento, logo tem a mesma forma.
é escalar e , então
é e
precisa ter entradas ⇒
.
Resposta: (neurônios
escondidos) e (dimensão da entrada), ou seja,
.
(b) As derivadas, sem deixar
Derivação completa (regra da cadeia)
Comece pela perda. Com :
.
Como
(porque ):
.
Para a entrada, encadeie por . Cada componente:
(aqui a derivada da quadrática, , já foi substituída).
Em forma vetorial: .
Como , temos
e a regra da cadeia matricial dá multiplicando:
.
Respostas em destaque:
Em coordenadas (caso a correção prefira sem matrizes):
.
Conferência numérica (para não entregar uma fórmula "no escuro")
Tome ,
,
,
e
. Então:
,
,
e .
Com :
.
.
(igual porque ).
Um passo com :
, nova previsão
e nova perda
— coerente com descida de gradiente.
O que escrever na prova (checklist)
(a) A cadeia de dimensões em três linhas, terminando em
e ; dizer por que (para os produtos existirem).
(b) Declarar ,
escrever e só então encadear.
Substituir —
deixar na resposta é erro explícito do enunciado.
Naive Bayes com dois atributos — classificação de X1 = 1, X2 = 0
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)
#
X1
X2
Y
1
0
0
1
2
0
1
0
3
1
0
0
4
1
0
0
5
1
0
1
6
1
1
1
7
1
1
1
8
1
1
1
Resolução didática — não gabarito oficial
Hipóteses.Y 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).
Conte as classes.Y = 1 nos exemplos 1, 5, 6, 7, 8 → P(Y=1) = 5/8 = . Y = 0 nos exemplos 2, 3, 4 → P(Y=0) = 3/8 = .
Verossimilhança de X1 = 1 em cada classe. Entre os cinco de Y=1, quatro têm X1=1 (5, 6, 7, 8) → . Entre os três de Y=0, dois têm X1=1 (3, 4) → .
Verossimilhança de X2 = 0 em cada classe. Em Y=1: exemplos 1 e 5 → . Em Y=0: exemplos 3 e 4 → .
Escore de cada classe (prior × verossimilhanças): Y=1 → (5/8)(4/5)(2/5) = 40/200 = 1/5 = ; Y=0 → (3/8)(2/3)(2/3) = 12/72 = 1/6 = .
Compare.1/5 = 0,200 > 1/6 ≈ 0,167, logo a classificação é Y = 1.
Posterior (opcional, mas recomendado).P(Y=1 | x) = (1/5)/(1/5 + 1/6) = (6/30)/(11/30) = 6/11 = ≈ 0,5455 e P(Y=0 | x) = 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 Y=1 com X2=0, para o escore de Y=1 virar 0 e o modelo declarar a classe impossível. A resposta formal seria aplicar Laplace, (#+1)/(#(Y=1)+2) 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).
Uma iteração do perceptron e a existência de um separador
Enunciado (transcrição). Considere treinar um perceptron com 2 características
() e o termo bias, no
conjunto de treinamento mostrado na tabela. Os pesos iniciais são
,
onde os pesos correspondem a ,
e 1, respectivamente.
Label
3
4
+
1
3
−
2
3
+
4
1
−
1
2
+
2
4
−
3
1
−
a) Depois de executar uma iteração do algoritmo nos 3 primeiros dados da tabela, qual é o
novo vetor de pesos ?
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 ;
entrada ;
escore ;
previsão com
empate () contando como ;
taxa ; atualização
somente quando erra.
(a) Uma passada pelos três primeiros dados
#
Dado
Erro?
Pesos depois
0
—
—
—
—
—
1
+
+
não
2
+
−
sim
3
−
+
sim
As contas, sem pular nenhum passo
Dado 1: , rótulo +.
⇒ previsão +, igual ao rótulo ⇒ sem atualização.
Resposta: ,
com erros nos três dados.
Robustez de convenção: com rótulos e
,
,
os mesmos três passos levam ao mesmo —
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
teria de
satisfazer (com o viés):
A cadeia de desigualdades (3 subtrações e a contradição)
Do positivo e do negativo
:
.
Do positivo e do negativo
:
.
Do negativo e do positivo
:
.
Como , isso força .
Contradição: e .
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 , os erros por época são
, e
— não caem para zero. Ao fim da primeira época os pesos são
.
Isso é indício, não prova: a prova é a contradição acima.
Leitura geométrica. Os positivos
são colineares (sobre );
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
)
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 , previsão, rótulo, "erro?" e pesos novos — e a resposta
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).
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).”
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 P(+b | +e)
Passo 1 — fatoração. Um termo por nó, com os pais do desenho:
Em notação compacta: . São cinco fatores, dos quais dois são priors de raiz (B e D) e três são condicionais.
Passo 2 — consulta e ocultas. Consulta B, evidência E; ocultas A, C e D — três variáveis binárias, logo 2³ = 8 combinações por valor de B (16 no total, se você escrever o denominador por extenso).
Passo 3 — equação. Com α normalizando sobre b:
e, explicitando o normalizador, α = 1 / [P(+b|+e) + P(−b|+e)] calculado com a mesma soma trocando +b por −b. Termos contados: produtos por valor de B, com 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) P(+b | +e) por amostragem por rejeição
Hipótese. As seis amostras são a lista completa fornecida; amostras com −e são descartadas; a estimativa é a proporção de +b entre as aceitas.
Figura B-Q3.2 — A lista da prova marcada: 4 aceitas, 2 rejeitadas, 1 acerto de +b entre as aceitas.
Filtre pela evidência. Amostras com +e: 2, 4, 5 e 6 → aceitas; as amostras 1 e 3 (−e) são descartadas → rejeições.
Conte a consulta entre as aceitas. Apenas a amostra 4 tem +b → .
Divida.P̂(+b | +e) = 1/4 = = 0,25.
Comente o estimador. Com quatro aceitas, o erro amostral é grande: o erro padrão é √(0,25·0,75/4) ≈ 0,216, então o valor não é “a” probabilidade, é uma estimativa compatível com uma faixa larga. A amostra 5 (+e com −d) é 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.
Á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.
Fiction
Age
Award
Rating
Length
Read
1
no
new
no
hi
short
Yes
2
yes
ancient
no
med
long
No
3
yes
old
yes
hi
medium
Yes
4
yes
old
no
med
medium
No
5
yes
ancient
yes
low
short
No
6
no
new
no
low
short
No
7
yes
new
no
hi
short
Yes
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 0,000001 nas somas vêm do arredondamento.
Distribuição inicial. Read = Yes nos exemplos 1, 3, 7 (3 de 7) e No nos exemplos 2, 4, 5, 6 (4 de 7). H(S) = −(3/7)log₂(3/7) − (4/7)log₂(4/7) = 0,985228 = . Esse é o teto de ganho: nenhum atributo pode passar disso.
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: .
Age. new → 1, 6, 7: 2 Yes e 1 No, H = ; 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 = .
Fiction. yes → 2, 3, 4, 5, 7: 2 Yes e 3 No, H = ; no → 1, 6: 1 Yes e 1 No, H = 1. Resto = (5/7)(0,970951) + (2/7)(1) = 0,979251. Ganho = .
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 = .
Length. short → 1, 5, 6, 7: 2 Yes e 2 No, H = ; 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 = .
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).
Pior atributo binário. Os atributos binários são Fiction e Award, e ambos têm o mesmo ganho, 0,005978 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.
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
H(S) 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.
Comentário. A combinação (−s, −c) 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 B→A, D→A, A→C, C→E, B→E. CPTs: P(+b) = 6/10, P(+d) = 5/10; P(+a|+b,+d) = 9/10, P(+a|+b,−d) = 7/10, P(+a|−b,+d) = 4/10, P(+a|−b,−d) = 1/10; P(+c|+a) = 8/10, P(+c|−a) = 3/10; P(+e|+b,+c) = 9/10, P(+e|+b,−c) = 6/10, P(+e|−b,+c) = 4/10, P(+e|−b,−c) = 1/10. Calcule P(+a | +e), informe quantos termos a enumeração tem por valor da consulta e justifique a fatoração.
Solução completa
Fatoração.P(A,B,C,D,E) = P(B)P(D)P(A|B,D)P(C|A)P(E|B,C). Consulta A, evidência E; ocultas B, C, D → termos por valor de A.
Interna em C: P(+e|B,c) com P(c|A).
Para A=+a: Σ_c P(c|+a)P(+e|b,c) vale 0,8·0,9 + 0,2·0,6 = 0,84 para b=+b e 0,8·0,4 + 0,2·0,1 = 0,34 para b=−b.
Para A=−a: 0,3·0,9 + 0,7·0,6 = 0,69 e 0,3·0,4 + 0,7·0,1 = 0,19.
Some D com P(a|b,d). Para A=+a: b=+b → 0,5·0,9 + 0,5·0,7 = 0,80; b=−b → 0,5·0,4 + 0,5·0,1 = 0,25. Para A=−a: 0,20 e 0,75.
Combine B: P(+a,+e) = 0,6·(0,80·0,84) + 0,4·(0,25·0,34) = 0,4032 + 0,034 = 0,4372. Como a CPT de A já está condicionada em B, não existe prior P(+a) para multiplicar — A não é raiz.
Comentário. Este treino cobra a diferença entre nó raiz e nó com pais: multiplicar P(+a) — 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 P(+x | +z) usando eliminação com ordem ⟨Y⟩. Mostre o fator intermediário.
Roteiro orientador
Quais fatores contêm Y? P(y|x) e P(+z|y).
Fixe a evidência em P(+z|y).
Multiplique e some Y, mantendo X → fator de duas entradas.
Multiplique pelo prior de X e normalize.
Solução completa
Evidência: P(+z|+y) = 8/10 e P(+z|−y) = 1/10.
Some Y para X = +x: (7/10)(8/10) + (3/10)(1/10) = 56/100 + 3/100 = 59/100 = .
Para X = −x: (2/10)(8/10) + (8/10)(1/10) = 16/100 + 8/100 = 24/100 = 6/25 = .
Aplicando os priors: (6/10)(59/100) = 354/1000 e (4/10)(24/100) = 96/1000.
Soma = 450/1000 = 9/20, que é P(+z) — coerente com o T-enum-1.
P(+x|+z) = 354/450 = 59/75 = ≈ 0,7867.
Treino · Eliminação · nível prova
T-elim-2 — quatro variáveis, evidência no nó folha
Rede: A→B, A→C, B→D, C→D. Dados: P(+a) = 4/10; P(+b|+a) = 8/10, P(+b|−a) = 3/10; P(+c|+a) = 6/10, P(+c|−a) = 5/10; P(+d|+b,+c) = 9/10, P(+d|+b,−c) = 6/10, P(+d|−b,+c) = 5/10, P(+d|−b,−c) = 1/10. Calcule P(+a | +d) por eliminação, na ordem ⟨B, C⟩, e informe o maior fator intermediário.
Solução completa
Fatoração: P(a,b,c,d) = P(a)P(b|a)P(c|a)P(d|b,c). Restrinja a evidência: f(b,c) = P(+d|b,c), com 9/10, 6/10, 5/10 e 1/10.
Multiplique e some B para cada A. Para A=+a:
Σ_b P(b|+a)[Σ_c P(c|+a)f(b,c)] = (8/10)[(6/10)(9/10) + (4/10)(6/10)] + (2/10)[(6/10)(5/10) + (4/10)(1/10)]= (8/10)(0,78) + (2/10)(0,34) = 0,624 + 0,068 = 0,692.
P(+a|+d) = 0,2768/0,5378 = 1384/2689 = ≈ 0,5147. A evidência quase não move o prior 0,4: sobe só para 0,515.
Maior fator intermediário: ao multiplicar P(b|a)·P(c|a)·f(b,c) aparece um fator sobre (A,B,C) 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 P(+b | +d) na ordem ⟨A, C⟩, diga o tamanho do maior fator e explique o que muda se você eliminar C antes de A.
Solução completa
Restrinja f(b,c) = P(+d|b,c) como no T-elim-2. Fixe B = +b e elimine C primeiro (ele só depende de A):
Σ_c P(c|a)f(+b,c) vale 0,78 para a=+a e 0,75 para a=−a.
Some A com P(a)P(+b|a): (4/10)(8/10)(0,78) + (6/10)(3/10)(0,75) = 0,2496 + 0,135 = 0,3846 = 1923/5000 = .
Para B = −b, o mesmo caminho dá (4/10)(2/10)(0,34) + (6/10)(7/10)(0,30) = 0,0272 + 0,126 = 0,1532.
P(+d) conferido: 0,3846 + 0,1532 = 0,5378 — igual ao T-elim-2, como tem de ser.
P(+b|+d) = 0,3846/0,5378 = 1923/2689 = ≈ 0,7151.
Maior fator: P(b|a)·P(c|a)·f(b,c) sobre (A,B,C) → 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 A → B. Amostras de (A, B): 1 (+a,+b); 2 (+a,−b); 3 (−a,+b); 4 (+a,+b); 5 (−a,−b); 6 (−a,+b). Estime P(+a | +b) por rejeição.
Roteiro orientador
Marque quais amostras têm +b.
Conte as aceitas (denominador).
Conte quantas aceitas têm +a (numerador).
Divida e escreva “estimativa”.
Solução completa
Aceitas (+b): 1, 3, 4, 6 → ; rejeitadas: 2 e 5.
Com +a entre as aceitas: 1 e 4 → .
Estimativa: 2/4 = 1/2 = .
Comentário. Duas amostras −a com +b foram aceitas: a evidência não filtra a consulta, apenas a condição. Se você tivesse descartado as −a, teria calculado outra coisa.
Treino · Amostragem por rejeição · nível prova
T-rej-2 — dez amostras com duas variáveis observáveis
Rede R → W, R → U (chuva, rua molhada, guarda-chuva). Amostras de (R, W, U): 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 P(+r | +w) por rejeição e diga quantas amostras foram descartadas.
Solução completa
Aceitas pela evidência +w: 1, 2, 3, 5, 6, 9, 10 → ; descartadas: 4, 7 e 8 (3 amostras).
Com +r entre as aceitas: 1, 2, 5, 9 → .
Estimativa: 4/7 = ≈ 0,571.
Comentário. A amostra 3 (−r com +w) é 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 D → T (doença, teste positivo). Doze amostras de (D, T): 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 P(+d | +t) 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
(a) Aceitas (+t): 1 e 6 → . Com +d: apenas 1 → . Estimativa 1/2 = .
(d) Com evidência rara, ~5 de cada 6 amostras são jogadas fora. O peso de verossimilhança fixa T = +t, sorteia só D e pondera cada amostra por P(+t|D): 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 (x1 = 1, x2 = 0) com Naive Bayes, sem suavização.
Roteiro orientador
Conte A e B (priors).
Conte x1 = 1 e x2 = 0 dentro de cada classe.
Monte os dois escores (prior × duas verossimilhanças).
Compare; normalize se quiser o posterior.
Solução completa
Priors: A tem 3 exemplos (1, 2, 6) e B tem 3 (3, 4, 5) → P(A) = P(B) = 1/2.
Classe A: P(x1=1|A) = 3/3 = 1; P(x2=0|A) = 1/3 (só o exemplo 6).
Classe B: P(x1=1|B) = 1/3 (exemplo 3); P(x2=0|B) = 2/3 (exemplos 3 e 5).
Escores: A = (1/2)(1)(1/3) = 1/6 = ; B = (1/2)(1/3)(2/3) = 1/9 = .
Como 1/6 > 1/9, a classe é A; posterior (1/6)/(1/6+1/9) = (3/18)/(5/18) = 3/5 = .
Treino · Naive Bayes · nível prova
T-nb-2 — oito exemplos, três atributos
Classifique o novo exemplo (1,1,1). Tabela de treino:
Treino do T-nb-2 (8 exemplos)
#
a1
a2
a3
classe
1
1
1
0
S
2
1
0
1
S
3
0
1
1
S
4
1
1
1
N
5
0
0
1
N
6
1
0
0
N
7
0
1
0
S
8
0
0
0
N
Solução completa
Priors: S nos exemplos 1, 2, 3, 7 → 4 de 8; N nos exemplos 4, 5, 6, 8 → 4 de 8. Ambos 1/2.
Escores: S = (1/2)(3/4)(1/2)(1/2) = 3/32 = ; N = (1/2)(1/2)(1/4)(1/2) = 1/32 = .
Posterior S = (3/32)/(4/32) = 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 a2=1 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 (a1, a2, a3, classe), 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 (1,1,1) (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?
Posterior de S = (35/1024)/(35/1024 + 25/432) = 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 (A, B, jogar): (1,1,sim), (1,0,sim), (0,1,não), (0,0,não). Calcule H(S), o ganho de A e o ganho de B, e diga qual vai para a raiz.
Roteiro orientador
Conte sim e não → entropia inicial.
Divida por A: entropia de cada ramo e média ponderada.
Repita para B.
Subtraia de H(S) em cada caso.
Solução completa
2 sim e 2 não → H(S) = 1 bit = .
Atributo A: A=1 tem 2 exemplos, ambos sim → H = 0; A=0 tem 2, ambos não → H = 0. Resto 0, ganho 1 = .
Atributo B: B=1 tem um sim e um não → H = 1; B=0 também → H = 1. Resto (1/2)(1) + (1/2)(1) = 1, ganho 0 = .
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 H(S) e o ganho dos três atributos; indique a raiz.
Treino do T-arv-2 (6 exemplos)
#
clima
vento
umidade
jogar
1
sol
fraco
alta
não
2
sol
forte
alta
não
3
chuva
fraco
normal
sim
4
chuva
fraco
normal
sim
5
sol
fraco
normal
sim
6
chuva
forte
normal
sim
Solução completa
4 sim e 2 não → H(S) = −(4/6)log₂(4/6) − (2/6)log₂(2/6) = 0,918296 = .
Clima: sol → 3 exemplos (1 sim, 2 não) H = 0,918296; chuva → 3 exemplos (3 sim) H = 0. Resto = (3/6)(0,918296) = 0,459148; ganho = .
Vento: fraco → 4 exemplos (3 sim, 1 não) H = 0,811278; forte → 2 (1 sim, 1 não) H = 1. Resto = (4/6)(0,811278) + (2/6)(1) = 0,874185; ganho = .
Umidade: alta → 2 exemplos (2 não) H = 0; normal → 4 (4 sim) H = 0. Resto 0; ganho = .
Raiz: umidade, que separa perfeitamente (ganho igual a H(S)). 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 (X, Y, Z, classe) 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 H(S) e os ganhos de X, Y e Z. Explique o empate e discuta se Z é realmente “melhor”.
Solução completa
Classes: 3 sim (exemplos 1, 3, 5) e 5 não → H(S) = 0,954434 = .
X: X=1 → exemplos 1 a 4, com 2 sim e 2 não (H = 1); X=0 → 5 a 8, com 1 sim e 3 não (H = 0,811278). Resto = 0,5 + 0,405639 = 0,905639; ganho = 0,048795 = .
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 = 0,25 + 0,5 = 0,75; ganho = 0,204434 = .
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”.
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 . Horizonte infinito,
sem estado terminal.
(a) Monte a tabela de transição e calcule ,
e por iteração de
valor, com .
(b) Mostre que a política "ir em A, ficar em B" satisfaz a equação de Bellman de
otimalidade com .
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.
;
.
Note que já na segunda rodada "ir" passa a ser melhor em A.
;
.
(b) Verificação de otimalidade. Com
e
:
Em A: ir
e ficar ⇒ ir, valor 4 ✔.
Em B: ficar
e ir ⇒ ficar, valor 8 ✔.
As duas equações de Bellman se confirmam, então
(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:
componente a componente (3 ≤ 4 e 7 ≤ 8) e a sequência é monótona crescente, como esperado com
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, ). Desconto .
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 .
(b) Determine 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.
(c) Porque 6 é recompensa imediata, enquanto "parar" rende 4 para sempre:
.
Com , uma recompensa recorrente de 4 vale
;
seria diferente com pequeno (aí o imediato venceria).
Armadilha evitada: colocar na avaliação. Se a política é dada, você resolve
o sistema; o 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; ).
Comece com .
(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 .
Abrir resolução — T-mdp-3
(a) Rodada 1 — avaliar .
Como E1 "parar" vai direto para F: .
Em E2 "avançar" vai para F com 6: .
Melhoria. Em E1: avançar
contra parar ⇒ avançar.
Em E2: parar
contra avançar ⇒ parar.
Então .
Rodada 2 — avaliar :
e
(mesma conta da T-mdp-2). O ganho na primeira melhoria foi
em E1.
Melhoria: em E1 avançar
e parar
; em E2 parar
e avançar
. Nada muda:
, convergiu.
Valores iniciais: .
(b) Se é gulosa em relação a
, então
para todo . A melhoria é estrita em se a desigualdade for estrita em
algum estado alcançável a partir de 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 e horizonte infinito, os valores podem
divergir: "parar" em E2 vale ,
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 —
não tem solução para
.
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 e
com rótulo +1;
e
com rótulo −1. Pesos iniciais
(ordem
),
,
e empate contando como −.
(a) Percorra os quatro pontos na ordem dada, época por época, até zero erros.
(b) Calcule as margens no fim e diga se a separação
é estrita.
Roteiro: monte uma tabela com , previsão, rótulo, "erro?" e pesos novos.
Cuidado: no empate a previsão é −, então um ponto positivo empatado conta erro.
Abrir resolução — T-perc-1
(a) Ordem: +, +, −, −.
Época 1. (1,0): ⇒ previsão −, era + ⇒ erro ⇒
.
(2,0): ⇒ acertou. (1,2):
⇒ previu +, era − ⇒ erro ⇒ .
(2,3): ⇒ acertou. Erros:
.
Época 2. (1,0) com :
⇒ empate ⇒ previsão −, era + ⇒ erro ⇒
.
(2,0): ✔; (1,2): ✔;
(2,3): ✔. Erros:
.
Época 3. Escores 2, 3, −2, −3 com :
todos corretos ⇒ erros . Convergiu.
(b) Margens: (1,0): 2; (2,0): 3; (1,2): 2; (2,3): 3. A menor é
> 0, então a separação é estrita e os pesos
atuais são um certificado de separabilidade: a reta é .
Conferência: se todos os 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: e
com rótulo +1;
e
com rótulo −1. Pesos iniciais
, ,
empate como −.
(a) Execute duas épocas e mostre os erros por época.
(b) Prove que não existe
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, :
(0,1) +: ✔ (erro 0 até aqui).
(1,0) +: ✔.
(0,0) −: ⇒ empate ⇒ previsão −, que é o rótulo ⇒ ✔.
(1,1) −: ⇒ previu +, era − ⇒ erro ⇒
.
Erros na época 1: . Época 2, com
(escore sempre −1, tudo previsto como −): (0,1) + erra ⇒ ;
(1,0) + erra ⇒ ;
(0,0) −: erra ⇒ ;
(1,1) −: erra ⇒ .
Erros: . Terceira época volta a
e o ciclo se repete.
(b) Suponha que exista
com correto em todos. Então:
(0,0) −: .
(1,1) −: .
(0,1) +: .
(1,0) +: .
Somando as duas últimas: .
Como , isso obriga
(porque
exige ). Contradiz .
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 e
com classe 1;
e
com classe 0. Pesos iniciais
, ,
e atualização .
(a) Treine até zerar os erros e diga quantos erros ocorreram por época.
(b) Repita com rótulos e a regra
. O resultado é o mesmo? Justifique.
(c) Calcule a cota
para o separador
e compare com os erros observados.
Abrir resolução — T-perc-3
(a) Ordem: 1, 1, 0, 0.
(2,1), ⇒
(empate não passa de 0), mas ⇒ erro ⇒
.
(1,2): ⇒ ✔.
(0,0): ⇒ , era 0 ⇒ erro ⇒
.
(1,0): ⇒ , era 0 ⇒ erro ⇒
.
Segunda época: (2,1): 2+1−1=2 ✔; (1,2): 1+2−1=2 ✔; (0,0): −1 ✔; (1,0): 1−1=0 ⇒
✔ (empate do lado 0). Erros:
e .
(b) Com rótulos , a regra é
quando .
A regra é
,
com .
Se e ,
o incremento é , igual a com
; se e
, o incremento é
, igual a com
. Nos acertos nada muda em nenhuma das duas. Logo as
sequências coincidem:
nas duas convenções — e a versão confirma:
.
(c)
(o ponto ). O separador unitário é
; as distâncias
dos pontos à reta
são 1,5/√2 (positivos) e, para ,
— então
,
e .
Cota:
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 fica exatamente
na fronteira
com os pesos finais? Não: com
seu escore é 0. Por isso a convenção importa: ele é classificado
como 0 e conta acerto. Se você usar , 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: ,
com e ;
;
com e
; alvo ;
perda .
(a) Faça a ida e calcule .
(b) Calcule ,
,
e
.
(c) Calcule também
e .
Roteiro: calcule
uma vez e use em tudo. Não esqueça que
deve ser substituído por número.
Abrir resolução — T-redes-1
(a) Ida. ;
;
;
.
(b) .
.
.
.
.
(c) O viés soma direto em
: .
O viés entra em , então
.
Conferência por diferenças finitas: aumentando em
0,001, vira 6,002, 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 , :
,
,
,
;
,
,
,
.
(a) Calcule , e
.
(b) Calcule ,
,
, ,
e
.
(c) Verifique a forma de cada gradiente contra a da grandeza correspondente.
Abrir resolução — T-redes-2
(a) .
Ativação: .
Saída: .
Perda: .
(b) .
;
;
;
(porque );
;
.
(c) Formas: é e seu
gradiente também; é e
o gradiente é ; e
são vetores , e os gradientes também.
Esse teste pega o erro clássico de esquecer a transposta.
Conferência: todos os gradientes compartilham o fator ; 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 : ,
,
,
,
, ,
.
(a) Calcule a ida, e todos os gradientes.
(b) Explique por que a segunda unidade escondida nunca sai de
se os pesos dela começam todos nulos (e o viés também).
(c) Sem viés de saída e com ,
que funções a rede representa? E com livre?
Abrir resolução — T-redes-3
(a) ;
;
;
;
.
;
.
.
.
.
(b) Com
e , temos
para qualquer entrada. Seu gradiente é
:
a linha de e o viés
não recebem atualização
(é o que aparece como linha de zeros em ).
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 ,
uma forma quadrática homogênea. Com ,
e :
a rede representa apenas a constante — e, como o
gradiente de é zero, ela fica presa nesse ponto. Sem
, 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
( é 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: C → T, T → A, M → A (chuva, trânsito, motoboy sai tarde, atraso). Todas binárias. Dados:
CPTs do bloco (valores em frações de denominador 10)
Distribuição
valores
P(+c) / P(−c)
3/10 e 7/10
P(+t | +c) / P(+t | −c)
8/10 e 3/10
P(+m) / P(−m)
4/10 e 6/10
P(+a | +t,+m) / P(+a | +t,−m)
9/10 e 6/10
P(+a | −t,+m) / P(+a | −t,−m)
5/10 e 2/10
(4 pts) Escreva a fatoração da conjunta e identifique consulta, evidência e ocultas para a pergunta P(+c | +a).
(10 pts) Calcule P(+a) e depois P(+c | +a), mostrando as massas intermediárias.
(3 pts) Escolha uma ordem de eliminação para P(+c | +a) e informe o número de entradas do maior fator intermediário.
(3 pts)C e M são independentes? E condicionadas a A? Justifique com d-separação.
Resolução didática — pontuação por subitem
(4 pts) Um fator por nó: P(c,t,m,a) = P(c)P(t|c)P(m)P(a|t,m). Consulta C; evidência +a; ocultas T e M (2 pontos pela fatoração, 1 pela consulta/evidência, 1 pelas ocultas).
(10 pts) Primeiro marginalize T: P(+t) = (3/10)(8/10) + (7/10)(3/10) = 24/100 + 21/100 = 45/100, logo P(−t) = 55/100. Depois A dado T: P(+a|+t) = (4/10)(9/10) + (6/10)(6/10) = 0,36 + 0,36 = 0,72; P(+a|−t) = (4/10)(5/10) + (6/10)(2/10) = 0,20 + 0,12 = 0,32. Então P(+a) = 0,45·0,72 + 0,55·0,32 = 0,324 + 0,176 = 0,500 = 1/2 = (4 pts).
Agora a massa conjunta: P(+c,+a) = P(+c)[P(+t|+c)P(+a|+t) + P(−t|+c)P(+a|−t)] = 0,3[0,8·0,72 + 0,2·0,32] = 0,3·0,64 = 0,192 = 24/125 = (4 pts). Posterior: P(+c|+a) = 0,192/0,5 = 0,384 = 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: P(+m,+a) = 0,4[0,45·0,9 + 0,55·0,5] = 0,4·0,68 = 0,272 = 34/125 = e P(+m|+a) = 0,272/0,5 = 0,544 = 68/125 = .
(3 pts) Ordem ⟨C, M, T⟩: eliminar C primeiro produz um fator sobre T com 2 entradas; em seguida f(t)·P(m)·P(+a|t,m) é um fator sobre (T,M) com 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.
(3 pts)C e M são raízes ligadas por um único caminho C→T→A←M, que tem um colisor em A. Sem observar A (nem descendentes dele, e não há), o caminho está bloqueado: são independentes — 1,5 ponto. Observando A, 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; P(+t) 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 (C, T, M, A), na ordem topológica:
Amostras fornecidas (na ordem em que foram sorteadas)
#
C
T
M
A
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
(4 pts) Marque as amostras aceitas e as rejeitadas para a evidência +a e escreva numerador e denominador.
(3 pts) Estime P(+c | +a).
(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
(4 pts) Aceitas: 1, 2, 4, 6, 7, 8, 9 → . Rejeitadas: 3, 5 (evidência −a), 10 (idem). Com +c entre as aceitas: 1, 2, 7, 8 → .
(3 pts)P̂(+c|+a) = 4/7 = ≈ 0,571.
(3 pts) Exato: ≈ 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 1/√n 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)
#
a1
a2
classe
1
1
1
S
2
1
1
S
3
1
0
S
4
0
1
S
5
0
1
N
6
0
0
N
7
0
0
N
8
1
1
N
Classifique (a1 = 1, a2 = 0). (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
(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. P(a1=1|S) = 3/4 (1, 2, 3); P(a2=0|S) = 1/4 (3); P(a1=1|N) = 1/4 (8); P(a2=0|N) = 2/4 = 1/2 (6, 7).
(2 pts)3/32 = 3/32 e 1/16 = 2/32, 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
(com a distância até Pam). Andar para a direita funciona com probabilidade
e rende 0. Horizonte infinito, sem terminal. Agora use
e em todos os itens.
(a) [6 pontos] Com , para quais valores de
a Política 1 (descansar sempre) é superior à Política 2 (mover uma vez e depois
descansar para sempre)? Comece em .
(b) [8 pontos] Com , faça duas iterações de
iteração de valor a partir de e preencha a
tabela (declare a fórmula usada).
(c) [6 pontos] Determine e
para e
, verificando a otimalidade com a equação de Bellman.
States
1
2
3
4
5
0
0
0
0
0
(a preencher)
(a preencher)
Abrir resolução — Simulado 1, bloco MDP
Convenções.
(pois ): 4, 16, 64, 256, 1024. Em
, andar fica em 5. Atualização síncrona; desempate mantendo a ação
anterior.
(a) [6] Política 1:
.
Política 2: no instante 0 a recompensa é 0 (andar); a partir do instante 1, Jim está em 2 e descansa:
.
Comparando: . Resposta:
;
em 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 .
(b) [8] Fórmula:
(com quando ).
Iteração 1: como , sai
.
Iteração 2, estado por estado:
;
;
;
;
.
States
1
2
3
4
5
0
0
0
0
0
(c) [6] Candidata .
Avaliando: ;
depois ,
,
,
.
Verificação: em , descansar vale
(andar); em , descansar vale
;
em , andar vale
(descansar). Nenhuma troca melhora ⇒ ótima. Política:
.
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 , 3 pela primeira iteração, 3 pela segunda
(incluindo o caso ).
(c) 6 pontos: 3 pela avaliação da candidata, 3 pela verificação de Bellman e pela política declarada.
Declare e o
comportamento de "andar" em .
Simulado 1 · Bloco 5 · Perceptron · 10 pontos · ~12 min
Quatro pontos e uma reta final
Dados de treino (com viés implícito ):
e com rótulo +1;
e
com rótulo −1.
Pesos iniciais
na ordem ,
,
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
.
(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: ,
,
.
:
⇒ previu −, era + ⇒ erro ⇒ .
: ⇒ + ✔.
:
⇒ previu +, era − ⇒ erro ⇒ .
Pesos ao fim da passada: ,
com erros. Ponto de atenção: esse vetor classifica
todos os pontos como positivos (o escore é ),
então ainda não serve — a próxima passada vai corrigir.
(b) [4] Época 2: dá
(empate ⇒ previu −, era + ⇒ erro) ⇒
;
os outros três ficam corretos. Erros:
. Época 3: escores 2, 1, −2, −1 ⇒
erros ⇒ convergiu com
.
Margens : (1,0): 2; (1,1): 1; (0,3): 2; (2,4): 1 — todas positivas,
logo a separação é estrita.
(c) [2] Fronteira :
,
isto é, .
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 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 ,
,
,
,
.
Dados: ,
,
,
,
, .
(a) [5 pontos] Faça a ida, calcule e confirme as formas de
, e
.
(b) [6 pontos] Calcule ,
,
e
(sem deixar ).
(c) [4 pontos] Calcule
e ; depois dê um passo com
em e mostre que a
perda diminuiu.
Abrir resolução — Simulado 1, bloco Redes neurais
(a) [5]
();
(mesma forma);
(escalar); .
.
(b) [6]
(forma );
;
;
(pois ).
(c) [4]
e .
Passo em : .
Nova previsão: ,
nova perda .
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 ,
1 por ,
2 por , 1 por
.
(c) 4: 2 por
e , 2 pelo passo com
verificação da perda.
O fator 2 da ativação quadrática aparece em — esquecê-lo derruba (b) e (c).
Simulado 1 · bloco 4 · Árvores de decisão · 15 pontos
Raiz da árvore para “jogar”
Treino (8 exemplos)
#
clima
vento
umidade
jogar
1
sol
fraco
alta
não
2
sol
forte
alta
não
3
nublado
fraco
alta
sim
4
chuva
fraco
normal
sim
5
chuva
forte
normal
sim
6
chuva
fraco
normal
não
7
nublado
forte
normal
sim
8
sol
fraco
normal
sim
(a) (3 pts)H(S) 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
(3 pts) Sim nos exemplos 3, 4, 5, 7, 8 (5); não nos 1, 2, 6 (3). H(S) = −(5/8)log₂(5/8) − (3/8)log₂(3/8) = 0,954434 = .
(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 = (3/8)(0,918296) + (2/8)(0) + (3/8)(0,918296) = 0,688722; ganho = .
Vento: fraco → 3 sim, 2 não (H = 0,970951); forte → 2 sim, 1 não (H = 0,918296). Resto = (5/8)(0,970951) + (3/8)(0,918296) = 0,951205; ganho = .
Umidade: alta → 1 sim, 2 não (H = 0,918296); normal → 4 sim, 1 não (H = 0,721928). Resto = (3/8)(0,918296) + (5/8)(0,721928) = 0,795566; ganho = .
(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.H(S) 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: V → G, G → F, G → C (viagem, gripe, febre, cansaço). Dados:
CPTs do bloco (frações de denominador 10)
Distribuição
valores
P(+v) / P(−v)
5/10 e 5/10
P(+g | +v) / P(+g | −v)
3/10 e 1/10
P(+f | +g) / P(+f | −g)
9/10 e 1/10
P(+c | +g) / P(+c | −g)
8/10 e 3/10
(4 pts) Fatoração e identificação de consulta, evidência e ocultas para P(+v | +f, +c).
(10 pts) Calcule P(+f, +c) e P(+v | +f, +c), com as massas de cada valor de V.
(6 pts)F e C são independentes na marginal? E dado G? Prove com números (use P(+f) = 0,26 e P(+c) = 0,40).
Resolução didática — pontuação por subitem
(4 pts)P(v,g,f,c) = P(v)P(g|v)P(f|g)P(c|g). Consulta V; evidência +f e +c; ocultas G (e a própria V permanece como variável de consulta). Só existe uma oculta — a conta é pequena, mas a fatoração precisa estar certa.
(10 pts) Condicione em G: P(+f,+c|+g) = 0,9·0,8 = 0,72 e P(+f,+c|−g) = 0,1·0,3 = 0,03. Como P(+g) = 0,5·0,3 + 0,5·0,1 = 0,2 e P(−g) = 0,8:
P(+f,+c) = 0,2·0,72 + 0,8·0,03 = 0,144 + 0,024 = 0,168 = 21/125 = (4 pts).
Massas por valor de V: P(+v,+f,+c) = 0,5[0,3·0,72 + 0,7·0,03] = 0,5·0,237 = 0,1185; P(−v,+f,+c) = 0,5[0,1·0,72 + 0,9·0,03] = 0,5·0,099 = 0,0495 (4 pts). Soma 0,1185 + 0,0495 = 0,168 ✓.
Posterior: P(+v|+f,+c) = 0,1185/0,168 = 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.
(6 pts)P(+f,+c) = 21/125 = 0,168, enquanto P(+f)P(+c) = 0,26·0,40 = 0,104 = 13/125 = , com P(+f) = 13/50 = e P(+c) = 2/5 = . Como 0,168 ≠ 0,104, não são independentes na marginal — é o efeito da causa comum G. Dado G = +g, porém, P(+f,+c|+g) = 18/25 = e P(+f|+g)P(+c|+g) = 0,9·0,8 = 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; P(+g) 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 +f e +c. Oito amostras de (V, G):
Amostras fornecidas (a evidência não é sorteada)
#
V
G
1
+v
+g
2
+v
−g
3
−v
+g
4
−v
−g
5
+v
+g
6
−v
−g
7
+v
−g
8
−v
+g
(4 pts) Monte a tabela com o peso w = P(+f|G)P(+c|G) de cada amostra.
(3 pts) Estime P(+v | +f, +c) pela soma de pesos.
(3 pts) Compare com o exato (79/112) e explique por que peso de verossimilhança é preferível à rejeição aqui.
(3 pts) Exato: ≈ 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: (1,1,1).
Treino do bloco 3
#
a1
a2
a3
classe
1
1
1
0
S
2
1
1
0
S
3
1
1
0
S
4
1
1
0
S
5
1
1
0
S
6
1
1
0
S
7
1
1
0
S
8
1
0
1
N
9
0
1
1
N
10
0
0
1
N
(4 pts) Classifique por máxima verossimilhança (sem suavização) e explique o que o zero faz.
(4 pts) Refaça com suavização de Laplace em atributos e priors, mostrando os dois escores.
(2 pts) A decisão muda? Qual resposta é defensável?
Resolução didática — pontuação por subitem
(4 pts) Priors 7/10 e 3/10. Em S: a1=1 → 7/7, a2=1 → 7/7, a3=1 → 0/7. Escore S = (7/10)(1)(1)(0) = 0 = . Em N: a1=1 → 1/3, a2=1 → 1/3, a3=1 → 3/3. Escore N = (3/10)(1/3)(1/3)(1) = 1/30 = . Sem suavização, S é “impossível” e N tem posterior 1.
(2 pts) Sim, a decisão inverte: 128/2187 ≈ 0,0585 > 16/375 ≈ 0,0427, então a classe passa a ser S, com posterior = (128/2187)/(128/2187 + 16/375) = 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, ,
andar rende 0 e funciona com probabilidade . Considere as políticas, todas a partir de
:
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 e ,
calcule o valor das três políticas e ordene-as.
(b) [7 pontos] Ainda com , 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 e ,
faça duas iterações de valor. Explique por que , embora P2 valha 16 e não seja ótima.
Abrir resolução — Simulado 2, bloco MDP
(a) [7] Com , andar é determinístico.
P1:
(recompensa 4 desde ).
P2: recompensa 0 em e 16 de
em diante: .
P3: recompensa 0 em e , e 64 de
em diante:
.
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 do valor e compra vezes mais
recompensa — , então
andar compensa.
(b) [7] Em geral, para :
e .
Igualando:
(a raiz é degenerada: os dois valores são 0).
A razão
é a chave: P3 ganha quando e perde quando
. Com
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 :
:
4, 16, 64, 256, .
para : ,
, ,
; em ,
Por que ?
Porque é o melhor valor com horizonte k: em
, a política "andar e descansar" só coleta a recompensa 16 uma vez
(), enquanto o valor de P2 soma a cauda
infinita (). 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é .
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 em P3 (a recompensa 64 só começa em
).
Simulado 2 · Bloco 5 · Perceptron · 10 pontos · ~12 min
Sete pontos que nenhuma reta separa
Dados (com viés implícito 1): positivos ,
, ;
negativos ,
, ,
. Pesos iniciais
,
, 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, :
os três positivos têm
⇒ acertos. Os negativos ,
,
dão ⇒ acertos. Só
erra (),
e a atualização deixa .
Erros: .
Época 2, :
dá ⇒ erro ⇒
;
e
acertam (); erra ⇒
;
os outros três negativos acertam. Erros: .
Terceira época repete : o processo não zera.
Pesos ao fim das épocas:
e ;
ao fim da terceira,
— os negativos e
ficam exatamente sobre a fronteira
(), o que mostra por que a convenção de empate precisa estar escrita.
(b) [5] Suponha
com classificação perfeita. Então:
(positivo)
e (negativo)
⇒ subtraindo, .
(positivo)
e (negativo)
⇒ subtraindo, .
Contradição imediata ( e ),
logo não existe separador. Geometricamente: os positivos estão sobre a reta
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
deixando claro que é o viés.
Simulado 2 · Bloco 6 · Redes neurais · 15 pontos · ~18 min
Gradientes com um zero no meio
Rede com , :
,
,
,
,
, ,
,
.
(a) [5 pontos] Faça a ida e calcule ; confirme as formas de
, e .
(b) [6 pontos] Calcule ,
,
,
,
e
.
(c) [4 pontos] Explique por que a terceira linha de
e o terceiro elemento de não são atualizados neste passo. A unidade
está "morta" para sempre? Justifique.
Abrir resolução — Simulado 2, bloco Redes neurais
(a) [5] é
(); ;
;
;
e .
(b) [6]
;
.
.
(pois as colunas de são e ).
;
.
(c) [4] Porque e o gradiente da
unidade é .
Com gradiente zero, a linha 3 de e
não mudam neste passo. Mas dizer que ela está morta "para sempre" seria errado: os pesos atuais
com viés só dão
zero em entradas com
— para outras entradas, e o gradiente é
não nulo. Ela ficaria morta para todas as entradas só se
e — aí sim o
gradiente é zero sempre e a unidade nunca sai de .
Distribuição dos pontos e checklist
(a) 5: 2 pelo forward, 1 pelas formas, 2 por e .
(b) 6: 1 por ,
1 por ,
2 por e
, 2 por
e
(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
#
X
Y
Z
classe
1
1
1
a
sim
2
1
1
a
sim
3
1
1
b
não
4
1
0
b
sim
5
1
0
b
não
6
0
1
b
sim
7
0
1
c
não
8
0
0
c
sim
9
0
0
c
não
10
0
0
c
não
(3 pts) Calcule a entropia inicial H(S).
(4 pts) Calcule o ganho de informação de X e de Y. O que o empate permite concluir?
(5 pts) Para Z, calcule o ganho de informação, a informação da divisão e a razão entre os dois.
(3 pts) Qual atributo você colocaria na raiz? Justifique considerando o viés.
Resolução didática — pontuação por subitem
(3 pts) Sim nos exemplos 1, 2, 4, 6, 8 (5) e não em 3, 5, 7, 9, 10 (5) → H(S) = 1 bit = .
(4 pts) X: X=1 (1 a 5) → 3 sim, 2 não, H = 0,970951; X=0 (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.
(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 = 0 + 0,4 + 0,324511 = 0,724511; ganho = 0,275489 = . Informação de divisão: H(2/10, 4/10, 4/10) = 1,521928 = . Ganho de razão = 0,275489/1,521928 = 0,181013 = .
(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.H(S), 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.
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.
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.