IX Congresso Brasileiro de Redes Neurais e Inteligência Computacional

Hoje foi o terceiro dia (propriamente dito) do IX Congresso Brasileiro de Redes Neurais e Inteligência Computacional (CBRN 2009), sendo realizado aqui em Ouro Preto.

Neste mesmo dia, apresentei o meu singelo trabalho de graduação entre tantos outros trabalhos de mestrado e doutorado. E graças a Deus, tudo deu certo!

E além disto, o melhor de tudo foi ter a oportunidade de assistir a trabalhos muito interessantes apresentados nessa conferência. A começar pelo trabalho da primeira sessão plenária, muito bem elaborado e muito, muito bem apresentado.

Os trabalhos que assisti e que mais me chamaram a atenção foram:

Redes Neurais sob Criterios de Entropia: Previsão de Potência Eólica e Outras Aplicações

Ao invés de minimizar os erros, o autor minimiza a entropia dos erros das redes neurais. Muito genial, pois evita que erros de medição contaminem o aprendizado. Professor Vladimiro Miranda, INESC Porto.

Analise de Desempenho de Cursos de Pós-Graduação Utilizando Mapas Auto-Organizáveis Parciais

Mostra o como podemos analisar o conceito CAPES de diversas maneiras para ter uma visão melhor sobre a pós-graduação no país. Muito interessante observar os resultados graficamente! Flavius da L. Gorgônio, José A. F. Costa

Uma Interface Humano-Máquina Inteligente Baseada no Rastreamento Ocular para comunicação Escrita de Pacientes com Síndrome Locked-In

A construção de um sistema de comunicação pra pessoas com paralisia total em que a única forma de comunicação seja o movimento e piscar de olhos. Graduação. Amanda L. Nascimento, Fernando B. L. Neto, Sérgio C. Oliveira, Hugo S. B. Filho

E também o meu, é claro 😛

Avaliação Prognóstica de Complicações Pós-Operatórias em Pacientes Submetidos à Cirurgia de Revascularização do Miocárdio

Uma investigação de aplicabilidade de redes neurais no problema específico do prognóstico de complicações pós-operatórias desta cirurgia cardíaca, utilizando análise de componente principal, regularização bayesiana e curvas ROC. Graduação. César Roberto de Souza, Ednaldo B. Pizzolato, Renata Mendes, Audrey B. Silva, Maurício Machado, Paulo Correa

Recebi algumas sugestões de como melhorar a pesquisa. Afinal, a apresentação foi produtiva!

Análise de Poder Discriminativo Através de Curvas ROC

contingencia_thumb-5B1-5D

Quando desenvolvemos sistemas, métodos ou testes que envolvem a detecção, diagnósticos ou previsão de resultados, é importante validar seus resultados de forma a quantificar seu poder discriminativo e identificar um procedimento ou método como bom ou não para determinada análise. No entanto, devemos levar em conta que a simples quantificação de acertos num grupo de teste não necessariamente reflete o quão eficiente um sistema é, pois essa quantificacao dependerá fundamentalmente da qualidade e distribuição dos dados neste grupo de teste.

 

Para exemplificar, tomemos o exemplo de um sistema para detecção de diabetes em pacientes, cuja saída é 1 ou 0 indicando se o paciente possui a condição ou não.  Agora, suponha que ao aplicamos este sistema num grupo de teste contendo 100 pacientes, dos quais já sabemos quais tem diabetes ou não, o sistema acerta 90% dos diagnósticos. Parece muito bom, não?

Não exatamente. O que não levamos em conta foi a distribuição da condição no grupo de teste. Revelamos agora que, no grupo de teste, 90% dos pacientes, na verdade, tinham a condição. O sistema, portanto, poderia simplesmente ter dito “1” a qualquer entrada apresentada, e mesmo assim, ainda conseguiria 90% de acerto já que os restantes 10% eram saudáveis. A esta altura, já não podemos ter a certeza de que o tal sistema seria tão bom assim.

 

contingencia
Tabela de Contingência (matriz de confusão)

Para casos como este, outras medidas foram criadas a fim de desconsiderar eventuais desbalanceamentos nos grupos de teste. Antes de entrar nestas medidas, apresento-lhe a chamada tabela de contingência (ou matriz de confusão), que servirá de base para as demais medidas apresentadas. Seu funcionamento é simples: consideramos valores positivos que o sistema julgou positivos como verdadeiros positivos (acerto), valores positivos que o sistema julgou negativos como falso negativo (erro), valores negativos que o sistema julgou como negativos como verdadeiros negativos (acerto), e valores negativos que o sistema julgou positivos como falso positivos (erro).

 

A seguir, apresentamos algumas medidas dela derivadas.

Acurácia

    A proporção de predições corretas, sem levar em consideração o que é positivo e o que é negativo. Esta medida é altamente suscetivel a desbalanceamentos do conjunto de dados e pode facilmente induzir a uma conclusão errada sobre o desempenho do sistema.

    ACC = TOTAL DE ACERTOS / TOTAL DE DADOS NO CONJUNTO

            = (VP + VN) / (P + N)

Sensibilidade

    A proporção de verdadeiros positivos: a capacidade do sistema em predizer corretamente a condição para casos que realmente a têm.

    SENS = ACERTOS POSITIVOS / TOTAL DE POSITIVOS

             = VP / (VP + FN)

Especificidade

    A proporção de verdadeiros negativos: a capacidade do sistema em predizer corretamente a ausência da condição para casos que realmente não a têm.

    SPEC = ACERTOS NEGATIVOS / TOTAL DE NEGATIVOS

             = VN / (VN + FP)

Eficiência

    A média aritmética da Sensibilidade e Especificidade. Na prática, a sensibilidade e a especificidade variam em direções opostas. Isto é, geralmente, quando um método é muito sensível a positivos, tende a gerar muitos falso-positivos, e vice-versa. Assim, um método de decisão perfeito (100 % de sensibilidade e 100% especificidade) raramente é alcançado, e um balanço entre ambos deve ser atingido.

    EFF = (SENS + ESPEC) / 2

Preditividade Positiva

Preditividade Negativa

Coeficiente de Correlação de Matthews – ou Coeficiente φ (phi)

    O coeficiente de correlação de Matthews é uma medida de qualidade de duas classificações binárias que pode ser usada mesmo se as classes possuem tamanhos bastante diferentes. Retorna um valor entre −1 e +1, em que um coeficiente de +1 representa uma predicao perfeita, 0 uma predicao aleatoria media, e –1 uma predicao inversa. Esta estatistica é equivalente ao coeficiente phi, e tenta, assim como a eficiência, resumir a qualidade da tabela de contingência em um único valor numérico passivel de ser comparado.

    MCC = φ = (VP*VN – FP*FN) / sqrt((VP + FP)*(VP + FN)*(VN + FP)*(VN + FN))

    Note que, se qualquer uma das somas no denominador for igual a zero, o denominador pode ser considerado 1, resutando num MCC igual a 0 que seria o limite correto para esta situação.

 

A Curva de Receiver Operating Characteristic (ROC)

A curva ROC (ou curva de ROC) foi desenvolvida por engenheiros elétricos e engenheiros de sistemas de radar durante a Segunda Guerra Mundial para detecter objetos inimigos em campos de batalha, tambem conhecida como teoria de detecção de sinais. A análise ROC tem sido utilizada em medicina, radiologia, psicologia e outras areas por muitas décadas e, mais recentemente, foi introduzida à áreas como aprendizado de máquina e mineracao de dados.

 

example-roc-curves
Curvas ROC de diferentes classificadores

Como o resultado de sistemas de classificação em classes geralmente são contínuos, ou seja, produzem um valor situado dentro de um determinado intervalo contínuo, como [0;1], é necessário definir um ponto de corte, ou um limiar de decisão, para se classificar e contabilizar o número de predições positivas e negativas (como diagnósticos verdadeiros e falsos no caso de ocorrência de uma patologia). Como este limiar pode ser selecionado arbitrariamente, a melhor prática para se comparar o desempenho de diversos sistemas é estudar o efeito de seleção de diversos limiares sobre a saída dos dados.

Para cada ponto de corte são calculados valores de sensibilidade e especificidade, que podem então serem dispostos em um gráfico denominado curva ROC, que apresenta no eixo das ordenadas os valores de sensibilidade e nas abscissas o complemento da especificidade, ou seja, o valor (1-especificidade).

 

Um classificador perfeito corresponderia a uma linha horizontal no topo do gráfico, porém esta dificilmente será alcançada. Na prática, curvas consideradas boas estarão entre a linha diagonal e a linha perfeita, onde quanto maior a distância da linha diagonal, melhor o sistema. A linha diagonal indica uma classificação aleatória, ou seja, um sistema que aleatoriamente seleciona saídas como positivas ou negativas, como jogar uma moeda para cima e esperar cara ou coroa. Definitivamente, não é o tipo de sistema mais confiável possível. No entanto, um sistema cuja curva ROC esteja localizada abaixo da diagonal ainda pode ser convertido num bom sistema – basta inverter suas saídas e então sua curva também será invertida.

Uma medida padrão para a comparacao de sistemas é a área sob a curva (AUC), que pode ser obtida por métodos de integração numérica, como por exemplo, o método dos trapézios. Teoricamente, quanto maior a AUC, melhor o sistema.

 

Exemplo de como fazer uma curva ROC no Excel.

 

Calculando a área de uma curva ROC no Microsoft Excel®

    Coloque os pares sensibilidade e (1-especificidade) nas colunas A e B, respectivamente. Caso sejam 10 pontos (de A1 a B10), utilize a seguinte fórmula:

    =SUMPRODUCT((A6:A15+A5:A14)*(B5:B14-B6:B15))*0,5

Determinando o melhor ponto de corte

Finalmente, a partir de uma curva ROC, devemos poder selecionar o melhor limiar de corte para obtermos o melhor desempenho possível. Para isto, podemos utilizar como parâmetro de comparação a medida de eficiência apresentada acima ou o valor φ (phi). Assim, podemos obter o limiar que apresente a melhor combinação de valores de especificidade e sensibilidade para o sistema.

Determinando o erro padrão no cálculo da área

O erro padrão de uma curva ROC se refere ao desvio padrão assumido ao aplicarmos nosso sistema a uma amostra da população do que se aplicássemos a população inteira. Esta medida parte do fato que, dependendo de quais amostras de uma população tomemos os valores para produzir nossa análise ROC, a área sob a curva poderá variar de acordo com a distribuição particular desta amostra.

O calculo do erro é, em certo ponto, simples, pois parte de apenas três valores conhecidos: a área A sob a curva ROC, o número Na de casos da amostra que apresentam a condição investigada (por exemplo, com diabetes) e o número Nn de casos que não a apresentam (sem).

ERRO = sqrt((A*(1 – A) + (Na– 1)*(Q1 – A²)+(Nn– 1)(Q2 – A²))/(Na * Nn))

em que:

    Q1 = A/(2 – A)
    Q2 = 2*A²/(1 + A)

 

Código

Na segunda parte da versão em inglês deste artigo está disponível uma implementação de curvas ROC em C#, incluindo código-fonte e aplicativos de demonstração.

 

Guias Recomendados

Receiver Operating Curves: An Introduction – Excelente página sobre curvas ROC e suas aplicações. Inclui excelentes applets que permitem brincar com as curvas, compreender melhor seu funcionamento e seu significado. Direcionado tanto a quem busca uma rápida introdução ao tema quanto a pesquisadores já familiarizados com a área.

 

Referências

WIKIPEDIA, The Free Encyclopedia, “Receiver Operating Characteristic”, Disponível em: <http://en.wikipedia.org/wiki/Receiver_operating_characteristic> Acesso em: 07 jul. 2009.

SABATTINI, R. M. E.; “Um Programa para o Cálculo da Acurácia, Especificidade e Sensibilidade de Testes Médicos”; Revista Informédica, 2 (12): 19-21, 1995. Disponível em: <http://www.informaticamedica.org.br/informed/sensib.htm> Acesso em: 07 jul. 2009.

ANAESTHESTIST.COM, “Receiver Operating Curves: An Introduction”, Disponível em: <http://www.anaesthetist.com/mnm/stats/roc/Findex.htm> Acesso em: 13 jul. 2009.

 

Notícias Interessantes

BBC NEWS MAGAZINE, A scanner to detect terrorists; Artigo muito interessante sobre como estatísticas são mal interpretadas quando divulgadas pela mídia. “To find one terrorist in 3000 people, using a screen that works 90% of the time, you’ll end up detaining 300 people, one of whom might be your target”. Escrito por Michael Blastland.

I am my own Grandpa!

The following is a (probably buggy) solution for the problem "I am my own grandfather" presented in many Prolog courses. I know it is buggy because some queries produces infinite loops, and some ended up crashing SWI-Prolog – after all, I’ve started learning Prolog today. But at least it answers the ultimate question correctly:

?- grandfather_in_law(i,i).
true .

 

erm.. Does the term "grandfather-in-law" even exist?

 

The Problem

The problem is stated as it follows (in english):

I married a widow (let’s call her w) who has grow-up daughter (call her d). My father (f), who visited us quite often, fell in love with my step-daughter and married her. Hence my father became my son-in-law and my step-daughter became my mother. Some months later, my wife gave birth to a son (s1), who became the brother-in-law of my father, as well as my uncle. The wife of my father, that is my step-daughter, also had a son (s2). Now I am my own grandfather. (aus N. Wirth, "Algorithms + data structures = programs"

In portuguese:

Eu me casei com uma viúva (W) que tem uma filha adulta (D). Meu pai (F), que nos visitava
freqüentemente, apaixonou-se por minha enteada e casou-se com ela. Logo, meu pai se tornou meu enteado e minha enteada tornou-se minha madrasta. Alguns meses depois, minha mulher teve um filho (S1), que se tornou cunhado do meu pai, assim como meu tio. A mulher do meu pai, isto é, minha enteada, também teve um filho (S2). Agora eu sou meu próprio avô.

And as a Youtube video:

 

The Proof

(Feel free to correct me if you wish)

    male(i).
    male(f).
    male(s1).
    male(s2).
    married(i,w).
    parent(w,d).
    parent(f,i).
    married(f,d).
    parent(w,s1).
    parent(i,s1).
    parent(f,s2).
    parent(d,s2).

    married(X,Y) :- tmarried(X,Y).
    tmarried(X, Y) :- married(Y,X).

    female(X) :- not(male(X)).

    %% Normal relationships
    father(Parent, Child) :-
        parent(Parent, Child),
        male(Parent).

    mother(Parent, Child) :-
        parent(Parent, Child),
        female(Parent).

    sibling(X,Y) :-
        parent(F, X),
        parent(F, Y), X = Y.

    uncle(Uncle, Nephew) :-
        parent(Parent, Nephew),
        sibling(Parent, Uncle),
        male(Uncle).

    grandparent(Grandfather, Grandchild) :-
        parent(X,Grandchild), parent(Grandfather,X).

    %% In-law relationships
    sibling_in_law(X,Y) :-
        parent(P,X),
        parent_in_law(P,Y),
        X = Y.

    sibling_in_law(X,Y) :-
        parent(P,Y),
        parent_in_law(P,X),
        X = Y.

    parent_in_law(Parent, Child) :-
        parent(Partner, Child),
        married(Parent, Partner).

    uncle_in_law(Uncle, Nephew) :-
        parent_in_law(Parent, Nephew),
        sibling(Parent, Uncle),
        male(Uncle).

    grandparent_in_law(Grandparent, Grandchild) :-
       ( parent_in_law(X, Grandchild), parent_in_law(Grandparent, X) );
       ( parent(X, Grandchild), parent_in_law(Grandparent, X) );
       ( parent_in_law(X, Grandchild), parent(Grandparent, X) ).

    grandfather_in_law(Grandfather, Grandchild) :-
        grandparent_in_law(Grandfather, Grandchild),
        male(Grandfather).

 

Now lets try and query grandfather_in_law(i,i). to see what if gives back.

And the answer is…

42 .

 

Now I know why everybody loves this language so much 🙂

The End of The Earth?

ZZ2B58355E

The first attempt to circulate a beam in the Large Hadron Collider (LHC) will be made on 10 September.

Let’s just hope everything works fine… Because otherwise the entire world may be sucked into the first human-created black hole!

Update: The test has finished and…. we are still alive! Well, for the while, at least! Thats because the experiment did not actually collide any particles yet, it just served to test the creation of the clockwise and counter-clockwise beams, without crossing each other. The Cern team hasn’t yet announced when it will start smashing particles together, but low-energy collision may happen as soon as the next few days.

Update 2: The countdown has started again. The deadline is now October 21, 2008!

Note: It’s obvious the Large Hadron Collider will not “create a mammoth black hole that will swallow up the earth“. While it may look as a giant device in our human eyes, in universe terms it lacks even the tiniest fraction of the power needed to create such – still hipothetical – black holes. The countdown exists because a lot of things may change in the way we comprehend the universe. Things that till today have only been predicted by theory may finally be observed in the real world.