Soluções — Aula 9: Redes Bayesianas e Modelos Gráficos Probabilísticos (PGMs) para Mineração de Itens Frequentes

Aprendizado Não Supervisionado

Autor

Marcos M. Raimundo — Instituto de Computação, UNICAMP

Data de Publicação

21 de outubro de 2026

Aula Exercícios

Respostas das Questões Discursivas

Questão 1: A Antimonotonicidade do Suporte e a Poda do Apriori

(a) Demonstração matemática de \(A \subseteq B \implies s(B) \le s(A)\): Seja \(\mathcal{T} = \{\mathbf{x}_1, \dots, \mathbf{x}_N\}\) a base de transações. O suporte de um itemset \(I\) é a proporção de transações que contêm todos os itens de \(I\): \[s(I) = \frac{|\{t \in \mathcal{T} \mid I \subseteq t\}|}{N}\] Seja \(\mathcal{T}_A = \{t \in \mathcal{T} \mid A \subseteq t\}\) e \(\mathcal{T}_B = \{t \in \mathcal{T} \mid B \subseteq t\}\). Como \(A \subseteq B\), qualquer transação \(t\) que contenha todos os itens de \(B\) conterá necessariamente todos os itens de \(A\) (\(B \subseteq t \implies A \subseteq t\)). Portanto, temos a inclusão de conjuntos \(\mathcal{T}_B \subseteq \mathcal{T}_A\). Pela monotonicidade da cardinalidade de conjuntos finitos: \[|\mathcal{T}_B| \le |\mathcal{T}_A| \implies \frac{|\mathcal{T}_B|}{N} \le \frac{|\mathcal{T}_A|}{N} \implies s(B) \le s(A)\]

(b) Aplicação na poda combinatorial do algoritmo Apriori: O espaço de busca com \(D\) itens contém \(2^D - 1\) itemsets não vazios. Em um catálogo moderado de \(D=100\), temos \(2^{100} \approx 1{,}26 \times 10^{30}\) combinações, inviabilizando a enumeração exaustiva. Pela contrapositiva da propriedade de antimonotonicidade: \[s(A) < s_{\min} \implies \forall B \supseteq A, \quad s(B) \le s(A) < s_{\min}\] Se o par \(\{X_1, X_2\}\) falha no teste de suporte mínimo (\(s(\{X_1, X_2\}) < s_{\min}\)), nenhum superconjunto que o contenha (como \(\{X_1, X_2, X_3\}\), \(\{X_1, X_2, X_4\}\), \(\dots\)) poderá atingir o suporte mínimo. O algoritmo Apriori gera candidatos de tamanho \(k\) unicamente a partir de combinações de itemsets frequentes de tamanho \(k-1\). Em uma base de \(10^7\) transações, isso evita milhões de varreduras em disco, podando preventivamente ramos exponenciais da árvore de busca.

Questão 2: A Falácia da Simetria do Lift e a Descoberta de Estrutura

(a) Demonstração da simetria do Lift: Por definição: \[\text{Lift}(A \Rightarrow B) = \frac{P(A \cap B)}{P(A)P(B)}\] Como a interseção de eventos probabilísticos é estritamente comutativa (\(A \cap B = B \cap A\) e \(P(A \cap B) = P(B \cap A)\)) e a multiplicação real é comutativa no denominador (\(P(A)P(B) = P(B)P(A)\)): \[\text{Lift}(A \Rightarrow B) = \frac{P(B \cap A)}{P(B)P(A)} = \text{Lift}(B \Rightarrow A)\]

(b) Cálculo numérico e interpretação estrutural: Dados do enunciado: \(P(A) = 0{,}01\), \(P(B \mid A) = 0{,}90\) e \(P(B \mid \neg A) = 0{,}05\). Pela lei da probabilidade total: \[P(B) = P(B \mid A)P(A) + P(B \mid \neg A)P(\neg A) = (0{,}90)(0{,}01) + (0{,}05)(0{,}99) = 0{,}009 + 0{,}0495 = 0{,}0585\] Calculando a probabilidade conjunta: \[P(A \cap B) = P(B \mid A)P(A) = (0{,}90)(0{,}01) = 0{,}009\] Calculando o Lift: \[\text{Lift}(A \Rightarrow B) = \frac{P(A \cap B)}{P(A)P(B)} = \frac{0{,}009}{(0{,}01)(0{,}0585)} = \frac{0{,}009}{0{,}000585} \approx 15{,}38\] Pela simetria provada no item (a), \(\text{Lift}(B \Rightarrow A) = 15{,}38\). Discussão: Embora o Lift seja idêntico nas duas direções (\(15{,}38\)), as dinâmicas condicionais subjacentes são completamente assimétricas: - A confiança \(c(A \Rightarrow B) = P(B \mid A) = 0{,}90\) (\(90\%\) dos que ativam \(A\) ativam \(B\)); - A confiança inversa \(c(B \Rightarrow A) = P(A \mid B) = \frac{P(A \cap B)}{P(B)} = \frac{0{,}009}{0{,}0585} \approx 0{,}1538\) (apenas \(15{,}4\%\) dos que ativam \(B\) vieram de \(A\)). O valor de Lift avalia apenas que a co-ocorrência supera a hipótese de independência em 15 vezes, mas é incapaz de distinguir entre \(A \to B\), \(B \to A\), uma causa comum \(A \leftarrow C \to B\) ou uma relação puramente simétrica. Depender do Lift para extrair regras de recomendação pode sugerir erroneamente que promover \(B\) impulsionará as vendas de \(A\), o que é uma falácia causal.

Questão 3: Paradoxo de Simpson e a Causa Comum (Tail-to-tail)

(a) Probabilidades marginais e probabilidade conjunta marginal: Pela lei da probabilidade total: \[P(A=1) = P(A=1 \mid C=1)P(C=1) + P(A=1 \mid C=0)P(C=0) = (0{,}80)(0{,}20) + (0{,}10)(0{,}80) = 0{,}16 + 0{,}08 = 0{,}24\] \[P(B=1) = P(B=1 \mid C=1)P(C=1) + P(B=1 \mid C=0)P(C=0) = (0{,}70)(0{,}20) + (0{,}05)(0{,}80) = 0{,}14 + 0{,}04 = 0{,}18\] Como \(A\) e \(B\) são condicionalmente independentes dado \(C\): \[P(A=1, B=1 \mid C) = P(A=1 \mid C)P(B=1 \mid C)\] Logo: \[P(A=1, B=1) = \sum_{c \in \{0, 1\}} P(A=1 \mid C=c)P(B=1 \mid C=c)P(C=c)\] \[P(A=1, B=1) = (0{,}80)(0{,}70)(0{,}20) + (0{,}10)(0{,}05)(0{,}80) = (0{,}56)(0{,}20) + (0{,}005)(0{,}80) = 0{,}112 + 0{,}004 = 0{,}116\]

(b) Cálculo do Lift na população agregada: \[\text{Lift}(A \Rightarrow B) = \frac{P(A=1, B=1)}{P(A=1)P(B=1)} = \frac{0{,}116}{(0{,}24)(0{,}18)} = \frac{0{,}116}{0{,}0432} \approx 2{,}685\] O Lift agregado é \(2{,}685 \gg 1\), sugerindo uma forte associação positiva aparente.

(c) Comparação com o DAG \(A \leftarrow C \to B\): Dentro de cada estrato condicional: - Para clientes de alta renda (\(C=1\)): \(\text{Lift}(A \Rightarrow B \mid C=1) = \frac{P(A=1, B=1 \mid C=1)}{P(A=1 \mid C=1)P(B=1 \mid C=1)} = \frac{(0{,}80)(0{,}70)}{(0{,}80)(0{,}70)} = 1{,}0\). - Para clientes de baixa renda (\(C=0\)): \(\text{Lift}(A \Rightarrow B \mid C=0) = \frac{P(A=1, B=1 \mid C=0)}{P(A=1 \mid C=0)P(B=1 \mid C=0)} = \frac{(0{,}10)(0{,}05)}{(0{,}10)(0{,}05)} = 1{,}0\). Interpretação: Condicionalmente à renda (\(C\)), comprar café gourmet e comprar torradeira de alta potência são completamente independentes (\(\text{Lift} = 1{,}0\)). A associação de \(\text{Lift} = 2{,}685\) encontrada pela mineração de dados agregados é uma correlação puramente espúria induzida pela causa comum \(C\) (alta renda impulsiona a probabilidade de ambos os produtos separadamente). Esse é o Paradoxo de Simpson em cestas de compras, resolvido de forma imediata quando representamos o processo gerador através do DAG \(A \leftarrow C \to B\).

Questão 4: Derivação Analítica do Explaining Away no Colisor

(a) Independência marginal: Como \(A\) e \(B\) são nós raízes independentes no grafo \(A \to C \leftarrow B\): \[P(A=1, B=1) = P(A=1)P(B=1) \implies P(A=1 \mid B=1) = \frac{P(A=1, B=1)}{P(B=1)} = P(A=1) = 0{,}20\]

(b) Probabilidade \(P(A=1 \mid C=1)\): Pela lei da probabilidade total, a marginal de \(C=1\) é: \[P(C=1) = \sum_{a, b \in \{0, 1\}} P(C=1 \mid A=a, B=b) P(A=a) P(B=b)\] Com as probabilidades das 4 configurações: - \(a=1, b=1\): \(P(A=1)P(B=1) = (0{,}20)(0{,}30) = 0{,}06 \implies (0{,}99)(0{,}06) = 0{,}0594\) - \(a=1, b=0\): \(P(A=1)P(B=0) = (0{,}20)(0{,}70) = 0{,}14 \implies (0{,}90)(0{,}14) = 0{,}1260\) - \(a=0, b=1\): \(P(A=0)P(B=1) = (0{,}80)(0{,}30) = 0{,}24 \implies (0{,}90)(0{,}24) = 0{,}2160\) - \(a=0, b=0\): \(P(A=0)P(B=0) = (0{,}80)(0{,}70) = 0{,}56 \implies (0{,}00)(0{,}56) = 0{,}0000\)

Somando: \[P(C=1) = 0{,}0594 + 0{,}1260 + 0{,}2160 + 0{,}0000 = 0{,}4014\] Agora calculamos \(P(A=1, C=1)\): \[P(A=1, C=1) = P(A=1, B=1, C=1) + P(A=1, B=0, C=1) = 0{,}0594 + 0{,}1260 = 0{,}1854\] Portanto: \[P(A=1 \mid C=1) = \frac{P(A=1, C=1)}{P(C=1)} = \frac{0{,}1854}{0{,}4014} \approx 0{,}4619 \quad (46{,}19\%)\] A ocorrência do efeito \(C=1\) elevou a probabilidade de \(A=1\) de seu valor marginal de \(20\%\) para \(46{,}19\%\).

(c) Probabilidade \(P(A=1 \mid C=1, B=1)\) e Explaining Away: Por definição de probabilidade condicional: \[P(A=1 \mid C=1, B=1) = \frac{P(C=1 \mid A=1, B=1) P(A=1 \mid B=1)}{P(C=1 \mid B=1)}\] Sabemos que \(P(A=1 \mid B=1) = P(A=1) = 0{,}20\) e \(P(C=1 \mid A=1, B=1) = 0{,}99\). Calculando o denominador \(P(C=1 \mid B=1)\): \[P(C=1 \mid B=1) = P(C=1 \mid A=1, B=1)P(A=1) + P(C=1 \mid A=0, B=1)P(A=0)\] \[P(C=1 \mid B=1) = (0{,}99)(0{,}20) + (0{,}90)(0{,}80) = 0{,}198 + 0{,}720 = 0{,}918\] Portanto: \[P(A=1 \mid C=1, B=1) = \frac{(0{,}99)(0{,}20)}{0{,}918} = \frac{0{,}198}{0{,}918} \approx 0{,}2157 \quad (21{,}57\%)\] Conclusão: \[P(A=1 \mid C=1, B=1) \approx 0{,}2157 < 0{,}4619 \approx P(A=1 \mid C=1)\] Ao saber que a causa concorrente \(B\) estava ativa (\(B=1\)), ela “explica e afasta” o efeito observado \(C=1\), reduzindo substancialmente a probabilidade a posteriori de que \(A\) tenha ocorrido (de \(46{,}19\%\) para \(21{,}57\%\)). Este cálculo comprova formalmente que \(A\) e \(B\) tornaram-se dependentes condicionalmente a \(C\), exibindo dependência negativa induzida.

Gabarito dos Testes Conceituais (Verdadeiro ou Falso)

Teste 1: Mineração de Regras e Propriedades de Suporte

  • (a) V: Pela propriedade de antimonotonicidade, qualquer subconjunto possui suporte maior ou igual ao do superconjunto (\(S \subseteq I \implies s(S) \ge s(I) \ge s_{\min}\)).
  • (b) F: A confiança é direcional: \(c(A \Rightarrow B) = P(B \mid A)\), enquanto \(c(B \Rightarrow A) = P(A \mid B)\). Elas só coincidem se \(P(A) = P(B)\).
  • (c) F: Um conjunto de 20 itens gera \(2^{20} - 1 = 1.048.575\) combinações não vazias (cerca de \(1{,}05 \times 10^6\), não exatamente \(10^6\)).
  • (d) V: Como \(c(A \Rightarrow B) = P(B \mid A)\), se \(B\) ocorre em 95% das transações independentemente de \(A\), \(P(B \mid A) = P(B) = 0{,}95\).

Teste 2: Métricas de Associação e Falácias do Lift

  • (a) V: O Lift é definido exatamente como a razão \(\frac{P(A \cap B)}{P(A)P(B)}\), medindo a divergência em relação à independência perfeita.
  • (b) F: O Lift mede apenas correlação simétrica observada; ele não estabelece direcionalidade nem exclui causas comuns latentes ou confundidores.
  • (c) V: Decorre de \(A \cap B = B \cap A\) e da comutatividade da multiplicação em \(\mathbb{R}\).
  • (d) V: \(\text{Lift} < 1 \iff P(A \cap B) < P(A)P(B)\), indicando que a presença de um item inibe a presença do outro (relação de substituição).

Teste 3: Grafos Acíclicos Direcionados e Fatoração Conjunta

  • (a) V: A ausência de ciclos direcionados é condição necessária e suficiente para estabelecer uma ordenação topológica que viabilize a fatoração consistente da regra da cadeia.
  • (b) V: Uma tabela completa exige \(2^{15} - 1 = 32.767\) parâmetros livres. Uma árvore com \(15\) nós tem \(1\) raiz (\(1\) parâmetro) e \(14\) nós com \(1\) pai (\(14 \times 2 = 28\) parâmetros), totalizando \(1 + 28 = 29\) parâmetros.
  • (c) V: Um grafo direcionado totalmente conectado representa a regra da cadeia da probabilidade sem simplificações (\(p(x_1, \dots, x_K) = \prod p(x_k \mid x_1, \dots, x_{k-1})\)), sem impor independências condicionais.
  • (d) F: A ausência de aresta entre \(X\) e \(Y\) indica independência condicional dada uma configuração de nós intermediários ou pais, mas não necessariamente independência marginal.

Teste 4: As Três Geometrias Canônicas de 3 Nós

  • (a) V: Em \(A \to B \to C\), o nó intermediário \(B\) bloqueia o caminho head-to-tail, garantindo que \(p(a, c \mid b) = p(a \mid b)p(c \mid b)\).
  • (b) F: Na causa comum \(A \leftarrow B \to C\), \(A\) e \(C\) são marginalmente dependentes; condicionar em \(B\) dissipa a correlação espúria e torna-os independentes.
  • (c) V: No colisor \(A \to C \leftarrow B\), os pais são marginalmente independentes, mas condicionar em \(C\) abre o canal e gera o fenômeno de explaining away.
  • (d) F: Na cadeia \(A \to B \to C\), quem bloqueia o caminho entre as pontas é a variável intermediária \(B\); condicionar em \(A\) não torna \(B\) e \(C\) independentes.

Teste 5: O Critério de d-Separação

  • (a) V: Por definição de Pearl (1988), um caminho que passa por um colisor head-to-head está bloqueado se nem o colisor nem seus descendentes forem condicionados.
  • (b) V: É o teorema fundamental da equivalência entre separação gráfica e independência condicional probabilística.
  • (c) F: Para que \(A \perp\!\!\!\perp B \mid C\), todos os caminhos possíveis entre qualquer nó de \(A\) e qualquer nó de \(B\) devem estar bloqueados.
  • (d) V: Condicionar em qualquer descendente de um colisor tem o mesmo efeito de condicionar no próprio colisor, abrindo o canal e induzindo dependência.

Teste 6: Cobertura de Markov e Equivalência Observacional

  • (a) F: A Cobertura de Markov de \(X\) inclui seus pais, seus filhos e os outros pais de seus filhos (co-pais), que são necessários para bloquear os colisores ativados pelos filhos.
  • (b) V: Condicionado na Cobertura de Markov, \(p(X \mid MB(X), \text{resto}) = p(X \mid MB(X))\), tornando \(X\) independente de todo o restante do grafo.
  • (c) V: Todas as três estruturas compartilham o mesmo esqueleto (\(A - B - C\)) e não possuem colisores (v-structures), pertencendo à mesma classe de equivalência de Markov.
  • (d) F: O colisor \(A \to B \leftarrow C\) possui uma v-structure não blindada que codifica \(A \perp\!\!\!\perp C\) marginalmente, sendo observacionalmente distinguível da cadeia \(A \to B \to C\).