Monty Hall

Problema: Num programa de televisão, existem 6 painéis, numerados 1 a 6. Atrás de 1 deles está o prêmio, enquanto os outros 5 nada contém. O participante escolhe 1 painel no início, mas ainda não revela-se o seu conteúdo. O apresentador então, sabendo onde está o prêmio, começa a abrir os painéis restantes. Ele abre 4 painéis, nenhum com o prêmio. Sobram então 2 painéis, o º 3 que o participante escolheu e o nº 6. O apresentador então pergunta se ele deseja ficar com o que escolheu ou se quer trocar, sendo que depois disso o prêmio será revelado. Qual é a decisão mais recomendada?

Essa é uma variação do famoso problema de Monty Hall, ou da Porta dos Desesperados ou paradoxo dos 3 prisioneiros. Se o objetivo da participante for maximizar a probabilidade de ganhar o prêmio, então a resposta é que ele deve sim trocar de painel. Isso porque a probabilidade de ele ter acertado no início (1/6) não mudou. Cada painel iniciou com essa mesma probabilidade, mas o apresentador fez o favor de reduzir todos os 5/6 de chance restantes a uma única opção. Ou seja, é como se a escolha fosse entre 1 painel ou 5 painéis.

Agora, se enunciarmos o problema um pouco diferente: O participante escolhe 1 painel. O apresentador, sem saber onde está o prêmio, vai abrindo os outros paineis aleatoriamente e chega-se na mesma situação final (4 abertos sem prêmio). E agora, qual a melhor escolha?

Nesse caso, a probabilidade de estar em cada um dos painéis é a mesma, de 50%. O fato do apresentador não saber e ir abrindo aleatoriamente faz com que a chance não mude pois nenhuma nova informação foi adicionada, apenas "deu sorte" de não ter aberto o prêmio ainda.

Estimativa de relevância de domínio semântico em textos

Resumo de: Gliozzo, A., Magnini, B. and Strapparava , C. “Unsupervised domain relevance

estimation for word sense dis ambiguation” In: Conference on Empirical Methods in

Natural Language Processing, 2004. Disponível em: http://wndomains.fbk.eu/publications/EMNLP04.pdf

O artigo apresenta o Domain Relevance Estimation (DRE), uma técnica para identificar a relevância de um texto dentro de certo domínio. Os domínios são conhecidos e pré-fixados, com palavras associadas. Dado um texto, calcula-se quão relevante ele é nesse domínio, e essa informação pode ser importante para resolver o problema de desambiguação do sentido das palavras no texto. Esse trabalho pode ser classificado como resolvedor do problema de Categorização de textos.

Inicia-se com um conjunto de domínios (categorias), tais como Medicina, Matemática ou Esportes, cada um com uma lista de palavras relacionadas. Essas listas foram extraídas do WORDNET DOMAINS, que é uma extensão do WORDNET (uma base de dados de palavras com informações léxicas e semânticas e ligações entre as palavras, como sinônimos, antônimos, derivados, formando uma grande rede), atribuíndo a cada palavra um ou mais labels de domínio. A estrutura de domínios é hierárquica e apresenta 200 domínios diferentes. Cada significado presente em uma palavra no WORDNET ganha label de domínio e a frequência do sgnificado é também computada através do SemCor. Por fim, existe uma label genérica, para palavras que não possuem um domínio de conhecimento específico.

A idéia básica é simples: quanto mais palavras de um certo domínio um certo texto contém, mais relevância para aquele domínio ele possuirá. E a WORDNET é útil nesse cálculo da relevância de uma palavra para o domínio. Ela é definida como sendo uma somatória das relevâncias te todos ossignificados presentes na rede da palavra.

No entanto, a simples contagem de frequências não é adequada pois introduziria ruído ao contar domínios não-relevantes. Normalmente para se contornar isso, usa-se uma aprendizagem supervisionada, mas não é esse o caso. O artigo usa o Gaussian Mixture Model, usando uma técnica de aprendizagem não-supervisionada: estima parâmetros baseado em estatísticas de um grande corpus de palavras. O GMM é um modelo que consiste numa composição de gaussianas e permite representar toda função densidade de probabilidade contínua como uma combinação linear de gaussianas. Nesse caso, será usado um modelo com 2 gaussianas: uma com a densidade de probabilidade relevante para o domínio e outra para o que não é relevante.

Usando Bayes, a relevância R do domínio D para o texto t numa posição j é:

Onde F é a frequência. Não-D é o oposto ao domínio, tudo que não é relacionado ao domínio D em questão. E para aplicar essa fórmula é necessário estimar a função densidade de probabilidade para a frequência dos termos no domínio e para isso um algoritmo de Expectation-Maximization é usado para maximizar o "likelihood" e formar o modelo GM.

No contexto do problema de desambiguação do sentido das palavras, um dos métodos é a desambiguação dirigida por domínio (DDD) onde somente informação de domínio é utilizada.

Concluindo, esse é um método interessante para categorizar textos sem o uso de exemplos prévios, exceto pelo fato do uso do SemCor que possui as frequências dos sentidos das palavras.

Relevance Vector Machine

Resumo do artigo: Michael E. Tipping; Sparse Bayesian Learning and the Relevance Vector Machine; Journal of Machine Learning Research Volume 1(Jun):211-244, 2001.

Disponível em: http://www.jmlr.org/papers/volume1/tipping01a/tipping01a.pdf

Este artigo propõe uma modificação à famosa Support Vector Machine (SVM), aqui denominada Relevance Vector Machine (RVM). Essa modificação tem como base o uso de técnicas de aprendizagem Bayesianas e introduz probabilidades na saída.

O artigo cita como desvantagens da SVM:

• Número de Support Vectors aumenta linearmente com o tamanho do conjunto de treinamento;
• Predições não são probabilísticas;
• Necessidade de estimar parâmetro de erro C (desperdício de computação e dados)
• A função de Kernel K(x,xi) deve satisfazer a condição de Mercer.

A RVM não sofre de nenhuma dessas limitações. O artigo apresenta modelos para os problemas de regressão e classificação.

É dita "esparsa" porque tipicamente o modelo aprendido após o aprendizado é uma soma ponderada de funções básicas, e o resultado mais esparso significa mais coeficientes, ou seja, menos funções consideradas (resposta mais simples).

(A teoria é complexa e não será explicitada aqui.)

O autor aplicou alguns testes comparativos entre RVM e SVM e conseguiu resultados que demonstram menor erro e muito menos vetores resultantes. Por exemplo, na regressão de uma função sinc(x), com 100 amostras, SVM apresentou desvio de 0,029 e 29 vetores enquanto o RVM teve um desvio de 0,0245 e apenas 6 vetores usados.

Apresentação

Nesse blog pretendo postar tudo o que eu ler/aprender relativo ao meu mestrado, i.e., resumos de artigos, livros, exercícios de disciplias e outros, de modo que funcione como um método de controle do meu avanço e de revisão do que já li.

A saber, meu mestrado é na área de Inteligência Artificial - aprendizado de máquina (Machine Learning), lá na Poli/USP sob orientação da profª. Anna Helena Reali Costa e teve início em janeiro de 2011.