Aprendizagem de Máquina ao Alcance de Todos - (2)

Voltando sem muitas delongas ao exemplo da primeira parte desse artigo, vamos considerar novamente o nosso banco de dados de pessoas caracterizadas cada uma por um “registro” seguindo o mesmo formato, com campos de peso, altura, idade, sexo, etc. Agora, vamos supor que além dessa caracterização por dados biométricos sabemos que essas pessoas estão classificadas em dois grupos, digamos que com e sem histórico de problemas cardíacos. Em jargão de biologia, as pessoas com histórico cardíaco são “Casos”, as sem são “Controles”.

Em Aprendizagem de Máquina, a chamada Aprendizagem Supervisionada consiste em treinar um “modelo” (uma função ou algoritmo de classificação) a reconhecer casos e controles automaticamente. É o tipo de problema aplicável exatamente a massas de dados com informação de categoria, como a do exemplo acima. Essa massa de dados é chamada de “conjunto de treinamento”, justamente porque sua função é servir como uma coleção de exemplos que são usados para “dizer” ao classificador onde ele está errando e onde ele deve melhorar - daí o “supervisionado” no nome desse tipo de aprendizagem.

Exatamente como um método de classificação pode conseguir resultados melhores ou piores dado um conjunto de exemplos? Bom, existem inumeráveis algoritmos de aprendizagem supervisionada - redes neurais, métodos evolutivos, árvores de decisão, todos eles podem ser usados para classificação. Para fins didáticos, porém, vou focar aqui em um método bem geométrico, as SVMs (do Inglês Support Vector Machines).

Como já disse na Parte 1, cada “campo” do banco de dados descrevendo as coisas sendo classificadas (no exemplo pessoas) é visto como uma dimensão (no sentido espacial da coisa mesmo) em aprendizagem de máquina. Se os registros tiverem só três campos - digamos, peso, altura e idade - temos três dimensões, e as pessoas são “vistas” por um algoritmo de ML como pontos num espaço tridimensional com eixos de idade, peso e altura. Assim Fulano pode ocupar o ponto em 1,80 metros, 75 quilos e 36 anos, enquanto Beltrano está no ponto 1,72m, 60Kg, 28a. Esse é um exemplo não tão difícil de visualizar porque usa um espaço tridimensional como aquele de largura, comprimento e altura onde vivemos, mas na prática os problemas de ML lidam quase sempre com “hiperespaços” multidimensionais. Em problemas de Bioinformática são comuns espaços com milhares de dimensões, por exemplo.

De qualquer forma, voltando às SVMs, o que elas fazem é (supersimplificando a coisa) encontrar uma “hipersuperfície” que divide esse “espaço” do problema em dois lados. Uma divisão boa é aquela que deixa os pontos representando Casos de um lado da superfície e os pontos representando Controles do outro lado. No nosso exemplo das pessoas com e sem problemas cardíacos ocupando um espaço tridimensional, vamos enxergar o espaço 3D como um cubo e supor que a maioria dos casos ocupa a metade do cubo correspondendo a pessoas com mais peso e mais idade, enquanto os controles se concentram nas pessoas mais novas e magras. Um plano cortando o cubo em dois na diagonal, paralelo ao eixo de altura, já dá uma divisão razoável então. Talvez essa divisão razoável deixe muitos pontos ainda nos lados errados, então podemos experimentar outras coisas como inclinar o plano (talvez em relação ao eixo de altura, para fatorar pessoas que são pesadas porque são grandes), ou mesmo experimentar uma superfície que não seja plana, mas sim curva, correndo em uma forma meio ondulada que divida os dois conjuntos de pontos quase perfeitamente. (No caso de SVMs, o tipo de superfície é determinado pela chamada “função de kernel” - que no caso do plano é uma função linear.)

Finalmente, é interessante também computar a superfície de forma a que, além de separar o mais corretamente possível os pontos, ela também mantenha uma certa distância desses pontos, sem “passar raspando” em nenhum deles. Isso tem a ver com o que talvez seja a mais desejada e mais difícil de obter das características de um bom classificador: a capacidade de generalização. Isto é, a capacidade de corretamente classificar elementos novos, desconhecidos, que não estavam no conjunto de treinamento. No caso das SVMs, podemos visualizar que uma superfície correndo muito “rente” pelos pontos limítrofes da, digamos, Categoria Caso, pode erroneamente classificar um monte de pontos como Controle, mesmo eles caindo perto dos pontos de Caso, simplesmente porque a superfície está rente demais e não inclui pontos próximos que provavelmente também são Casos. Em casos assim, podemos “antropomorfizar” o que aconteceu dizendo que o classificador na verdade não aprendeu nada, apenas “decorou” os pontos que foram mostrados a ele…

No fim das contas, todo classificador gerado por aprendizagem supervisionada faz essencialmente a mesma coisa que a SVM - seccionar o espaço do problema em regiões correspondentes a categorias. Só que eles trabalham sob princípios que não são tão obviamente geométricos (e didáticos) como no caso da SVM, daí não vou falar sobre eles aqui. Finalmente, aprendizagem supervisionada não é categorização - coisas como regressão simbólica também caem nessa subdivisão de ML. Mas acho que isso já fugiria um pouquinho do nível “feijão com arroz” implicado pelo título. :)

Inteligência Artificial 1 Comentário

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

“Serve o vinho celeste, Ganymede”

Jupiter: …”Pour forth heaven’s wine, Idaean Ganymede, And let it fill the Daedal cups like fire.” Percy Bysshe Shelley, Prometheus Unbound

Na mitologia grega, Ganimedes era um príncipe troiano, filho de Tros, cuja beleza arrebatou Zeus (ou Júpiter na mitologia romana) de tal forma que ele mandou uma águia (ou se transformou em uma, dependendo da versão) para raptá-lo e levá-lo para o Olimpo. Lá, tornou-se um dos amantes de Zeus e copeiro dos deuses. Ganimedes também é a maior lua de Júpiter e a maior do sistema solar e foi a terceira descoberta por Galileu Galilei.

Agora, além desses significados, Ganymede (Ganimedes em inglês) também denomina a nova versão anual dos projetos da Eclipse Foundation lançada ontem, dia 25 de junho. Precedida por Europa e Callisto, ela é uma coleção de 23 projetos distintos, cujas novas versões são lançadas de forma coordenada, para evitar incompatibilidades entre eles e facilitar a vida dos usuários.

Apesar do Eclipse poder ser usado para o desenvolvimento em C, C++, Ruby e Python, o lançamento dessa nova versão é particularmente relevante para a comunidade de desenvolvimento Java, posto que o Eclipse tornou-se uma das IDEs mais utilizadas pelos desenvolvedores dessa linguagem. Algumas mudanças mais visíveis estão na IDE, como melhorias na área de assistência de contexto (as teclas Ctrl+Espaço), novos tipos de refactoring, uma nova interface para atualização de plugins, dentre outras novidades além de correções de bugs da versão anterior. Porém, há atualizações igualmente interessantes em outras áreas, como as novas versões da ferramenta de relatório BIRT e do Mylyn, um plugin de interface focada em tarefas (task-focused interface) e que faz integração entre a IDE e ferramentas de rastreamento de issues como o Bugzilla e o Trac, e novas adições como o Rich Ajax Platform (RAP), que permite a construção de aplicações Web baseadas em AJAX usando o mesmo modelo de desenvolvimento de aplicações RCP. Porém, nem tudo são flores: o suporte nativo ao sistema de controle de versão Subversion, outra adição bastante esperada, não está totalmente “transparente” como o do CVS. Para ativá-lo, é necessário que o usuário faça o download de componentes localizados em servidores fora da Eclipse Foundation, sendo que um deles possui versão compilada apenas para Win32 (no caso o conector JavaHL).

Para aqueles que querem instalar a nova versão, basta visitar o site do Eclipse Ganymede, onde também se encontra a lista com as mudanças ocorridas. E “deixa-o encher as taças como fogo”. :-D

Paulo Ferreira de Moura Junior, é arquiteto de sistemas com passagem em empresas como a Borland do Brasil e Vetta Technologies. Bacharel em Ciência da Computação pela UFMG, trabalha atualmente na Geolabs.

Desenvolvimento 0 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

Aprendizagem de Máquina ao Alcance de Todos - (1)

Volta e meia surge algum artigo aqui no blog falando de aplicações de inteligência artificial e frequentemente usando termos que podem soar meio misteriosos para muitos, como o críptico “aprendizagem de máquina”, às vezes também usado em sua forma original em Inglês, “machine learning”. Penso que talvez esse termo pode ainda evocar na cabeça de muitos uma imagem de coisa scifi incompreensível, então decidi escrever este artigo (em dois “capítulos”) sobre o beabá da aprendizagem de máquina para mostrar que, uma vez explicado, o tal Machine Learning (ou ML) pode até parecer meio prosaico…

A definição vaga e por alto (e não sei se existe uma definição exata e profunda, a propósito :) de ML como um todo é: um método ou algoritmo para descobrir de forma automatizada padrões em uma massa de dados. Acho que essa definição não diz muito coisa sem exemplos, então vamos dar alguns nomes a alguns bois.

Vamos supor que você tenha um banco de dados com características de várias pessoas. As características podem ser qualquer coisa (digamos, peso, altura, idade, etc), desde que possam ser comparadas de forma quantitativa ou lógica. Esse conjunto de valores de características descrevendo cada pessoa é chamado vetor de características, em jargão de ML.

Já que o valor da altura de uma pessoa é comparável com o valor da altura de outra, o mesmo acontecendo com peso, idade e demais dimensões (=outro jargão de ML - bem, na verdade de ciências exatas em geral, nesse caso :) do vetor de características, então acaba que dois vetores inteiros podem ser comparados um com o outro, levando em conta todas as suas dimensões ao mesmo tempo. É possível criar o que chamamos de medida de similaridade, que é simplesmente uma conta envolvendo todas as dimensões de dois vetores que no final solta um número - quanto mais alto esse valor, mais similares são esses vetores.

De posse dessa medida, já é possivel fazer coisas divertidas em ML - por exemplo juntar as pessoas parecidas umas com as outras, dividindo o conjunto original em vários subconjuntos de pessoas parecidas. Esse tipo de processo é o chamado clustering - ou aglomeração, traduzindo - e é a base da vertente de ML chamada de aprendizado não-supervisionado.

A parte do “aprendizado” nesse nome vem do fato de que antes os elementos do conjunto de dados sendo analisado eram completamente amorfos, não-estruturados, “farinha do mesmo saco” por assim dizer; após o clustering, porém, temos grupos separados nos quais veremos padrões. No exemplo do clustering de pessoas, talvez se forme um aglomerado de pessoas baixas e gordas, outro de pessoas altas, um de pessoas velhas de peso médio, e por aí vai.

Já a parte do “não supervisionado” vem do fato de que não é preciso dizer ao algoritmo de clustering sendo usado (existe uma infinidade deles) se os resultados que ele está produzindo são bons ou ruins, ele mesmo toma suas próprias “decisões” de como fazer melhor a aglomeração. Aliás, é difícil dizer quantitativamente e de forma geral, irrestrita, se um clustering é bom ou ruim, no sentido de que é algo um tanto subjetivo - existe uma multiplicidade de métricas de qualidade de clustering, com aplicações apropriadas caindo em vários casos diferentes.

Existe também, é claro, a aprendizagem supervisionada, o outro grande campo da Aprendizagem de Máquina. Mas isso é assunto para a Parte 2 deste artigo…

Data Mining, Inteligência Artificial 0 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

Interfaces telepáticas: quando o Mundo do Amanhã chega hoje mesmo

Recentemente, surgiu aqui no Labs um anteprojeto de um projeto para talvez, quem sabe, trabalharmos com a identificação automática de fases do sono em “polissonografias”, que são dados neurofisiológicos e cardio-respiratórios coletados de pessoas dormindo. A parte neurofisiológica da coisa serviu de inspiração para eu escrever este artigo acerca das “interfaces telepáticas”, como as chamo. Alguns diriam que “interfaces neurais” talvez seja um termo melhor, mas gosto das imagens de pulp scifi que “telepáticas” evoca. :)

Aliás, o tema de interfaces capazes de ler diretamente a mente do usuário é recorrente na ficção científica. A mais antiga referência _scifi_ sobre interfaces telepáticas de que me lembro está no clássico inesquecível O Planeta Proibido. Numa das cenas desse filme de 1956, um dos personagens usa um aparelho que é capaz de ler e interpretar sua mente, inclusive mostrando as imagens em que ele está pensando. No filme, essa tecnologia é alienígena e apresentada como algo centenas de milhares de anos à frente da ciência humana - o que é bastante curioso, considerando-se que o filme se passa séculos no futuro, em uma época onde os humanos viajam pelo espaço em discos voadores antigravitacionais e cruzam anos-luz em tempos razoáveis passando pelo “hiperespaço”.

Ou seja, esse parece ser mais um dos casos muito freqüentes em que a ficção científica acerta acerca de uma previsão sobre o futuro, mas erra feio a ordem do que virará realidade primeiro. Alguns experimentos com resultados inesperados e algumas teorias exóticas até dão alguma esperança de que um dia teremos antigravidade de disco voador ou saltos hiperespaciais como no filme, mas na melhor das hipóteses isso está num futuro imprevisivelmente distante. Já as interfaces telepáticas estão bem próximas. Mais precisamente, elas já estão aqui!

Lembro de pesquisas sobre leitura e interpretação de sinais cerebrais desde os anos 90. Inicialmente, essas pesquisas visavam ajudar pessoas com deficiências físicas, possibilitando a sinais de seus cérebros “contornar” paralisias e outras condições. A pesquisa de anos atrás sobre a movimentação do ponteiro de um mouse usando a mente é emblemática dessa era. Porém, como era de se esperar, essas pesquisas começam aos poucos a ser aplicadas ao mercado muito mais vasto de consumidores em geral…

Assim, há alguns meses surgiu a demonstração de uma interface de “subvocalização” para celulares, que capta os impulsos nervosos que o cérebro envia para a garganta e interpreta as palavras sem que a pessoa tenha de efetivamente verbalizá-las - ideal para ter conversas telefônicas privadas mesmo em ambientes cheios de gente. Também apareceu recentemente, e já está disponível comercialmente, um controle telepático para videogames.

Essas aplicações envolvem análise de sinais eletroencefalográficos ou atividade de conjuntos de nervos superficiais específicos - o que certamente já rende um bom número de aplicações divertidas, como exemplificado. Porém, esse meio de aquisição de certa forma capta apenas comandos que o cérebro emite “propositalmente”. Mas a verdadeira fronteira final das interfaces telepáticas, que vai além da captação de comandos diretos do cérebro, envolve a observação direta da atividade cerebral, que potencialmente poderia levar à possibilidade de saber o que uma pessoa está realmente pensando. Uma pesquisa divulgada poucas semanas atrás por exemplo descobriu que as mesmas áreas cerebrais tendem a se ativar quando pessoas diferentes estão pensando na mesma palavra, um princípio que se bem desenvolvido poderia levar a um “leitor universal de pensamentos”. Outra aplicação relativamente recente é o detetor de mentiras com 90% de acerto. Esta última, a propósito, cai no que muitos vêem como o “lado negro” das tecnologias de telepatia artificial, já que levanta uma série de questões éticas e legais.

É claro que, ao contrário do que acontece com as interfaces “eletroencefalográficas”, que no fim das contas usam simples eletrodos, essas aplicações bem mais ousadas observam a atividade cerebral por fMRI (do Inglês para Imagem por Ressonância Magnética Funcional), ou seja, usam máquinas enormes e caras, tornando difícil imaginar uma popularização desses métodos. Porém, avanços também recentes em magnetômetros atômicos acenam com a possibilidade de máquinas de fMRI portáteis e baratas em um futuro não muito distante. Mais espantosamente, magnetômetros atômicos poderiam em tese ser sensíveis o suficiente para monitorar o magnetismo até de neurônios individuais, podendo registrar a atividade cerebral com um nível de detalhe impensável hoje em dia. Talvez, quem sabe, até o suficiente para alcançar o “upload” tão almejado pelo movimento Trans-Humanista. Mas isso já é outra viagem, que talvez um dia eu tenha coragem de encarar em um artigo futuro. :)

Ciências cognitivas, Inovação, Memória, Usabilidade 0 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

Miniaturizando o Capital de Risco

Há algum tempo que essa história de “Web 2.0″ tem levado a um renascimento das startups web. Há até quem diga que estamos vivendo uma nova bolha especulativa, repetição daquela dos anos 90. Bobagem. O volume de dinheiro envolvido nessa nova onda de criação de startups é uma fração do volume de 10 anos atrás e ainda não tem ninguém lançando ações em bolsa antes de conquistar o primeiro cliente.

A verdade é que está cada vez mais barato criar uma startup, especialmente se ela for voltada para a web. Todo o software necessário é gratuito. Hospedagem e banda são muito mais baratas que há 10 anos atrás, e com serviços de cloud computing como os Amazon Web Services e o Google App Engine, ninguém precisa mais construir um data center enorme e caríssimo. Você escala na exata medida da sua necessidade e, assume-se, do seu bolso. O custo para levar sua grande idéia que vai revolucionar o mundo para o mercado nunca foi tão baixo. Se você além de ter idéias revolucionárias souber programar, o custo principal é o seu tempo.

Isso é um enorme problema para os venture capitalists, que administram fundos de capital de risco, porque as startups precisam de muito menos investimento que antes. À primeira vista isso pode parecer uma vantagem para os financiadores, mas não é. VCs não escalam “para baixo” facilmente. Eles têm fundos enormes para investir, e uma capacidade limitada de aprovar e monitorar investimentos. Então, para um VC típico, simplesmente não faz sentido investir, digamos, R$100.000,00 em 100 empresas ao invés de investir R$10.000.000,00 em uma única empresa.

VCs continuam operando um um regime de poucos negócios com um montante alto por negócio, mas a indústria de TI não se encaixa mais tão bem nesse modelo. Isso é especialmente crítico no caso de web, que sempre foi onde a maioria dos investimentos e grandes sucessos ocorrem. Alguns fundos simplesmente mudaram de indústria, e estão agora investindo em coisas mais futuristas e que ainda exigem muito dinheiro de pesquisa e desenvolvimento, como nanotecnologia e energia renovável.

Mas algumas pessoas viram nisso uma oportunidade. A Y Combinator, fundada pelo pioneiro de web applications Paul Graham e amigos, é uma firma de investimento bem peculiar. Eles só investem em empresas nascentes (o chamado capital semente). Os investimentos seguem sempre um template. Ao contrário da maioria dos VCs, você não precisa conhecer um amigo do VC para receber investimento. Eles fazem seleções abertas duas vezes por ano e só investem nos melhores projetos submetidos nessas seleções. Os contemplados recebem o suficiente para viver por três meses. E os felizardos são obrigados a se mudarem para a mesma cidade onde os investidores estão (Cambridge, MA no verão Vale do Silício no inverno) durante esses três meses.

A idéia é que a Y Combinator oferece mais que o dinheiro (que não é grande coisa, mas por outro lado não custa muito em termos de participação acionária). Eles oferecem experiência (o Paul Graham vendeu a ViaWeb, sua startup, pro Yahoo por US$50 milhões anos antes da bolha estourar), contatos, séries de palestras com empreendedores famosos, e um dia de demo em que todo mundo apresenta suas idéias para outros investidores que podem, então, financiar a vida das novas empresas depois dos três meses.

Esse modelo diferente, embora novo, já levou a vários casos de sucesso. A Reddit foi adquirida pela Condé Nast, dona da Wired. A Auctomatic foi adquirida por US$5 milhões menos de um ano após seu lançamento. A Zenter foi comprada pelo Google há mais ou menos um ano. A estimativa dos sócios da Y Combinator é que as startups que eles financiam têm uma taxa de sucesso de 50%, o que é impressionante. O típico na indústria de capital de risco é 20%, no máximo 30% para os melhores fundos.

A visibilidade e os resultados obtidos pela Y Combinator inspiraram diversos grupos a criar firmas nos seus moldes na Europa, Canadá e outras partes dos Estados Unidos. São os Y Imitators ;-). Até agora, nenhum chegou a lugar algum. Eu acho difícil reproduzir o que a Y Combinator tem, e agora eles estão criando uma massa crítica de empresas investidas que estão amadurecendo e formando suas redes de contatos, ex-fundadores ricos que podem investir nas próximas gerações de startups, e experiência em como determinar, o mais cedo possível, quais projetos vão vingar.

Uma forma ainda mais peculiar de investimento é a da Prototype Invest. Eles não te dão dinheiro, dão software. Se você se empolgou com a possibilidade de criar uma startup revolucionária sem precisar levantar rios de dinheiro, mas não sabe nada de tecnologia para transformar sua idéia em produto, eles fazem isso pra você em troca de participação acionária. Aí nem o custo de desenvolvimento você tem. Não conheço os caras e não tenho a menor idéia da capacidade (ou seriedade) deles. Mas se funcionar é um redutor de barreira de entrada interessante.

Inovação 0 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

E o anti-iPhone?

E a Apple anunciou o iPhone 3G, baixou o preço de compra (mas a AT&T, que tem exclusividade nos EUA, aumento o preço dos planos, então no balanço ficou mais caro) e diz que fechou com parceiros em 70 países. A Claro vai vender o iPhone 3G no Brasil até o fim do ano. Ainda não se sabe quanto vai custar, se vem com fidelização obrigatória até a terceira geração e outros detalhes. Mas os viciados em gadgets estão em polvorosa. E tem muita gente de olho nas possibilidades de desenvolver software para o iPhone. Não é à toa. É um aparelho com potencial revolucionário, e já tem até fundo de capital de risco dedicado exclusivamente a financiar empresas que desenvolvam para o iPhone. O nome? iFund, claro…

Há quem diga que até o fim do ano que vem a Apple deve vender 15 milhões de iPhones no mundo todo. Não é pouco, mas é menos de 1.5% do número de telefones celulares vendidos por ano no mundo. Em 2007, foram vendidos 1.15 bilhões de telefones. Pode ser revolucionário com 1.5% de market share? Claro que pode, afinal é um produto high end e que atrai early adopters de tecnologia.

Mas esses números mostram uma outra possibilidade. De acordo com a venerável The Economist, ainda esse ano teremos mais de 3.3 bilhões de usuários de telefonia celular no mundo. Ou seja, mais da metade da população do mundo terá um celular. A expectativa da Portio, uma empresa britânica especializada em pesquisa de mercado celular e wireless, é que a penetração chegue a 75% da população mundial até 2011. Sabe aquela história que até servente de pedreiro tem celular hoje em dia? Pois é, daqui a pouco os serventes de pedreiro da África também vão ter.

Claro que a imensa maioria desses usuários está na chamada “base da pirâmide”. Gente pobre, pobre mesmo, com o aparelho mais barato possível e plano pré-pago. A inclusão dessa numerosíssima base da pirâmide no mercado de consumo é um dos grandes desafios de estratégia corporativa e de marketing desse começo de século, e os celulares mostram algumas idéias interessantes de como isso pode acontecer.

Um exemplo que eu adoro é o M-PESA, desenvolvido pela Vodafone e pela Safaricom, uma operadora no Kênia. É um sistema simples de mobile banking, no qual você transfere dinheiro via SMS. Sistemas de pagamento via celular como o Oi Paggo estão se popularizando no Brasil, e o Banco do Brasil já tem uma iniciativa de mobile banking. Mas o potencial transformador do M-PESA é que ele funciona com quem não tem conta no banco. Com quem é pobre e excluído demais pra isso.

Uma combinação óbvia de mobile banking e base da pirâmide é usar mobile banking para microcrédito. Reduz burocracia, permite uma dispersão maior dos fundos, e tem um mecanismo interessante de incentivo ao pagamento — pode-se deduzir uma fração de cada recarga do plano pré-pago feita pelo devedor. Se ele não pagar o empréstimo, o celular é bloqueado.

Essa é só uma possibilidade. Eu acho que, embora o iPhone seja um produto interessante e com grande potencial para inovação, o pessoal que pensa em criar startups devia olhar também pra base da pirâmide. É um mercado grande demais e, finalmente, os estrategistas corporativos estão inventando maneiras para deixar de ignorá-lo.

Desenvolvimento, Inovação, Mobile 5 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

Diagrama de Voronoi

Imagine que você deseja abrir um negócio próprio, por exemplo, uma lanchonete. Sabe-se que grande parte do sucesso do negócio é devido à escolha do ponto comercial. Suponha que você tenha um mapa com a localização de todos os seus concorrentes. Qual seria um ponto ideal para a abertura da sua lanchonete? Para ajudá-lo a responder a essa pergunta, você pode utilizar o Diagrama de Voronoi.

Um Diagrama de Voronoi, nomeado assim depois que o russo Georgy Voronoi estudou sua versão n-dimensional em 1908, pode ser definido de uma maneira simples como:
Dado um conjunto S de pontos no plano, determinar para cada ponto s em S a região V(p) em que todos os pontos p da região estão mais próximos de s do que de qualquer outro ponto s’ em S. A figura abaixo ilustra um Diagrama de Voronoi. O que o diagrama indica é que, dentro da região amarela por exemplo, qualquer ponto (no plano) está mais próximo do ponto destacado da região do que de qualquer outro ponto destacado do plano. A complexidade do algoritmo é O(n log n).

No exemplo da lanchonete, os pontos destacados seriam as lanchonetes concorrentes e o plano seria a cidade (ou bairro, região, etc.). Com isso, você poderia verificar em qual local uma lanchonete concorrente cobre uma grande área, podendo ter um potencial para a abertura de outra. Claro que a sua decisão não deve ser baseada somente no diagrama. É preciso verificar o seu público-alvo, movimentação de pessoas na região, dentre outras coisas. Além disso, se uma região não possui concorrentes, não necessariamente significa que você é um gênio de ter identificado esse ponto primeiro. Pode ser que o local realmente não seja bom para esse tipo de negócio. Bom, mas isso não vem ao caso nesse post.

Durante minha iniciação científica sobre redes de sensores sem fio, publicamos um artigo utilizando Diagramas de Voronoi para identificar áreas de cobertura redundantes. Resumindo, identificávamos nodos sensores próximos uns dos outros pela área de Voronoi e esses nodos eram considerados redundantes, pois mais de um estavam cobrindo praticamente a mesma área. Assim, um deles poderia ser desligado para economizar energia e re-ligado novamente caso por algum motivo sua área esteja descoberta.

A idéia desse post era mesmo apresentar resumidamente o Diagrama de Voronoi. Talvez possa ser aplicado em algum caso específico dos leitores.

Ps.: Não me responsabilizo por decisões de escolha de ponto comercial

Geometria Computacional 1 Comentário

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

Sobre congressos, uvas e resveratrol (de novo!)

Estou de volta da XXXVII Reunião Anual da Sociedade Brasileira de Bioquímica e Biologia Molecular (SBBq) que aconteceu em Águas de Lindóia – SP semana passada.

Desde que eu me enveredei por essa área científica, há uns 10 anos atrás, tenho ido frequentemente a congressos (mais ou menos um por ano em média). Muitos acham um saco, mas eu acho bom por quatro motivos:

  • Conhecer pessoas - que trabalham com a mesma coisa que você e que fazem coisas completamente diferentes que você.
  • Atualização.
  • Quebra de rotina – que pode ser massacrante ;-)
  • Conhecer novos lugares – é bom viajar, principalmente quando recebemos auxílio financeiro pra isso! :-)

A SBBq tem uma seção só de bioinformática e daí dá pra tentar ver mais ou menos pra onde a área está se enveredando. Grosso modo, deu pra perceber, mesmo com o viés por ser um congresso de bioquímica, que as coisas estão migrando para a área de proteômica – eu vi diversos posters com modelagens 3D de proteínas e proteômica de um modo geral e nenhum sequer sobre microarrays, por exemplo.

Nesse congresso aproveitei para conversar com uma especialista em uvas. A garota se chama Caroline e é lá do Sul, mais especificamente do Instituto de Biotecnologia de Caxias do Sul – RS. O pôster dela me chamou atenção por se tratar de composição do extrato de uvas e eu queria saber a opinião dela sobre o resveratrol. Durante a conversa, deu pra perceber que ela estava bem por dentro do assunto (e depois deu pra saber por que: a moça tem diversos papers sobre estudos de compostos de uvas ).

Daí eu aproveitei pra perguntar se ela tomaria resveratrol em doses orais. A resposta foi bem incisiva: Não. Primeiro porque não existe nada realmente provado que o resveratrol combate o envelhecimento (apesar de proteger os camundongos contra doenças relacionadas a dietas hipercalóricas). E segundo porque as concentrações de resveratrol no vinho e suco de uva são muito menores do que doses orais de resveratrol puro – inclusive, algumas substâncias ditas antioxidantes em doses baixas, se tornam oxidantes em doses maiores, como é o caso da vitamina C.

Então, para os menos radicais, acho que o negócio é ficar só no suco de uva e vinho mesmo ;-)

Depois comento sobre o outro poster que eu vi que enfatiza os malefícios dos produtos da queima do diesel para células do sistema imune – seria uma propaganda para o biodiesel?

Biologia, Biotecnologia 4 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

Nano e Atom: pouco velozes mas ainda assim furiosos

Antigamente era fácil decidir qual era o melhor processador para o seu computador: o melhor era sempre o mais rápido, e para saber isso bastava ver a velocidade do clock (relógio). É claro que um Pentium 100 MHz era mais lento que um Pentium 200 MHz, e ninguém contestava isso.

Na verdade a questão é muitíssimo mais complexa, já que a arquitetura de um processador é muito mais importante para definir seu poder de processamento do que o a freqüência de clock. Ao longo dos anos, técnicas de projeto que nos anos 1970 eram exclusivas de supercomputadores foram incorporadas aos processadores domésticos, tais como uso de pipeline longos, execução fora de ordem e especulativa. São mudanças na arquitetura que fazem com que um processador moderno como um Core 2 Duo, rodando a 1.8 GHz, seja mais rápido que um Pentium IV da geração anterior, com clock de mais de 3 GHz.

Recentemente uma outro critério apareceu para deixar tudo ainda mais complicado: o consumo de energia. Não adianta ter um notebook rapidíssimo se a bateria dele dura apenas uma hora. E o sucesso dos subnotebooks (ou “netbooks” como preferem alguns, notebooks com telas pequenas - 10″ ou menos - e muitas vezes sem disco rígido) como o Apple Macbook Air, Asus EEE PC e o Mobo (da brasileira Positivo) fazem com que o dilema poder de processamento x consumo de energia seja ainda mais importante.

As duas estrelas recém-lançadas nessa cena são os novos processadores x86 (isto é, compatíveis com programas para computadores comuns, capazes de rodar Linux e Windows) de baixíssimo consumo: o Intel Atom e o VIA Nano.

Ambos são quase perfeitos para os subnotebooks, com desempenho mais do que suficiente e pouca necessidade de refrigeração. O interessante é que os dois têm arquiteturas radicalmente diferentes!

O Intel Atom é uma volta às origens; especificamente, uma volta ao velho 486. Para reduzir consumo e complexidade o Atom deixou para trás técnicas como execução fora de ordem, execução especulativa e renomeação de registradores, tornando-o um processador bastante convencional (alguns diriam “antiquado”, mas definitivamente não é o caso). Isso faz com que o desempenho dele não seja tão alto quanto o de um processador moderno com o mesmo clock.

Essa estratégia já tinha sido explorada pela VIA em seus processadores baratinhos antigos (um bom exemplo sendo o C7). A partir das experiências com o C7 a VIA resolveu ir bem além do Intel Atom: o VIA Nano é um processador 64-bit superescalar muito mais sofisticado que o seu concorrente, capaz de realizar reordenação de instruções e previsão de desvios poderosa.

Note que tudo usado no VIA Nano já existe em processadores tradicionais da Intel e da AMD; a decisão de não incluir esses recursos no Atom foi deliberada, e tomada tendo em vista quase que exclusivamente o consumo de energia.

A pergunta que todos estão fazendo, claro, é quem vai ganhar a briga. Será que o aumento do desempenho do Nano vai justificar a provável menor autonomia ? Será que o Intel Atom vai ser rápido o suficiente para as aplicações que o mercado espera ? Recentemente a VIA demonstrou um Nano rodando Crysis, um jogo pesadíssimo feito para PCs convencionais, o que impressionou bastante a audiência. Do lado Intel, a mais nova estrela dos subnotebooks, o MSI Wind, vai ser um dos primeiros já com o Atom, possui tela de 10″ e HDD de 80 GB (ausente no EEE e Macbook Air) e será vendido a partir de 16 de junho por um preço extremamente atraente (US$ 399 a versão com Linux).

Certamente os próximos meses nos reservam algumas surpresas.

Inovação 1 Comentário

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

WikiProteins: um site público para a anotação de proteínas

Está no ar o WikiProteins beta, que é parte de uma iniciativa iniciada anteriormente, o WikiProfessional. A idéia é a mesma do WikiPedia porém voltada para a anotação de proteínas.

A anotação é um processo de caracterização de proteínas, principalmente de sua função. Existem biólogos em constante processo de anotação de proteínas e genes. Esse processo pode se dar em intervalos curtos de tempo, como em projetos genomas, onde diversos novos genes são descobertos e precisam ser anotados. Ou como em projetos de longo prazo, como a anotação de todo o UniProt, por exemplo.

Em ambos os casos todos os tipos de informações sobre genes e proteínas tentam ser coletados, assim como dados de função, localização, informações estruturais, artigos científicos relacionados, etc. O WikiProteins provê exatamente esse tipo de informação de maneira editável por qualquer um.

É claro que foi necessário um esforço computacional inicial pesado pra reunir diversas informações de proteínas e genes em um único pool inicial pra servir de startup pro wiki. E os dados foram minerados de fontes bem confiáveis, como o PubMed, UniProt e BioMed Central.

Os autores fizeram uso de metodologias de text mining/data mining que demandaram a criação de um componente de software, denominado Knowlet. Os Knowlets, segundo os autores, “combinam múltiplos atributos e valores para os relacionamentos entre conceitos” (tradução minha). Mais sobre isso no paper da Genome Biology.

Só pra constar, eu andei testando o WikiProteins com uns genes que o Lúcio me passou ;-) Esses genes parecem ser relacionados com nefropatia em pacientes diabéticos. Mais especificamente o gene PCSK1, que é uma proteína neuroendócrina. O WikiProteins me retornou uma série de informações relevantes e minha impressão é que o site promete.

Infelizmente ele não me retornou exatamente o que eu queria saber - e isso eu obtive com o bom e velho Gene Cards :

…susceptibility gene for non insulin dependent diabetes (type II) and…”

Bom, acho que agora é hora de promover o site e editar o Wiki… ;-)

PS: Ah, esse post foi de dica de um amigo, o Durfan

Biologia, Biotecnologia, Data Mining 0 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...