segunda-feira, maio 29, 2006

O Que Há com a Microsoft?

Faz algum tempo que está acontecendo um fenômeno estranho com a Microsoft, estranho não porque está acontecendo, mas porque ninguém parece estar prestando atenção nele...

Tudo começou quando a Microsoft anunciou, a coisa de um mês atras, que ia adiar o lançamento do Windows Vista, uma queda no preço das ações nessas condições é normal e até esperado, e como esperado, aconteceu. Daí, a empresa anunciou uma reestruturação da divizão do Windows (apesar de todos saberem que não é bom mexer no time de projetos em execução), e no dia seguinte veio a grande pérola: O Bill Gates anunciou em uma reportagem (com todo o jeito de comprada) que iria utilizar as patentes de software da Microsoft contra o Linux.

Este terceiro acontecimento me pegou de surpresa. (Até que os outros dois eram esperados :). ) A Microsoft tem evitado trazer atenção para a forma como as patentes de software são usadas, provavelmente para melhorar suas chances de aprovar estas patentes na Europa. Citar as patentes de software me pareceu um último recurso, bastante extremo, para desviar a atenção dos acionistas de algum problema. E um problema bem grave.

Bom, neste dia eu comecei a acompanhar o valor das ações da Microsoft. Como era de se esperar, elas estavam caindo já a três dias (desde o adiamento do Vista). Nada de mais, mas elas continuaram caindo, e caindo, e recuperando um pouco, mas voltando a cair... O resultado é que a queda chegou a quase 20%. Agora elas se recuperaram de novo, não sei se vão voltar a cair ou não.



A figura acima mostra o preço das ações desde o começo de 2006 até o dia 26 de Maio (sexta) (fonte: yahoo!). (O tempo está em segundos desde o começo de 1970, quando eu conseguir um programa que me faça este gráfico de forma correta e fácil, eu corrijo isso.) As bolsas do mundo inteiro deram uma oscilada na semana do dia 26 de Maio, mas isso mal aparece no gráfico, essa variação toda é quase exclusividade da Microsoft.

Bom, mas como eu já disse, o estranho não é nem tanto que as ações estão caindo. O que é estranho mesmo é que ninguém está comentando isso. Não é todo dia que uma empresa do tamanho da Microsoft oscila desta forma, e não aparece nenhuma menção nos jornais. Nem a imprensa especializada está dando bola, nem mesmo slashdot comentou! Como pode?

segunda-feira, maio 01, 2006

IA: Busca de Soluções

Há duas formas bastante distintas de se resolver um problema matemático. Por exemplo, para resolver a equação x = 3x + 1, pode-se aplicar as propriedades da igualdade, e subtrair 3x dos dois termos: -2x = 1, e depois divir-los por -2, obtendo x = -1/2. Outra possibilidade é testar vários valores de x na equação, até encontrar algum que a satisfaça. Este segundo método, em que soluções são testadas até se encontrar a desejada, é denominado "busca de soluções", e é o que normalmente é utilizado em inteligência artificial.

Sair tentando valores de x a esmo até encontrar algum que sirva não parece uma forma muito boa de resolver o problema, e não é mesmo. Mas em alguns casos, ninguém conheçe outro jeito, assim, a única alternativa é escolher bons valores para testar. Cria-se, então um algorítmo para gerar valores com maior probabilidade de serem os desejados. Informalmente, estes algorítmos são denominados "heurísticas" (formalmente, só alguns deles são heurísticas, os outros são pseudo-heurísticas).

Agora, para melhor projetar uma heurística, o desenvolvedor tem que saber quais são os possíveis valores que a solução pode assumir. O conjunto destes valores é chamado de "espaço de busca". Alguns dados sobre o espaço de busca são extremamente relevantes. São eles o número de dimensões deste espaço, ou seja, quantos valores são independentes na solução, ou, de forma mais fácil para um programador, é nescessário um vetor de que tamanho para representar a solução? E para cada dimensão, é importante saber se os valores são contínuos (que só podem ser representados por números reais) ou discretos (que podem ser representados com números inteiros) e se são limitados ou não, ou seja, se eles estão dentro de um intervalo bem conhecido ou se vão (desde ou) até infinito.

Por fim, outra característica extremamente importante de cada dimensão é se ela tem uma topologia ou não. Dizer que um conjunto tem uma "topologia" é dizer que os elementos deste conjunto têm uma seqüência, por exemplo, os números inteiros têm topologia, assim, entre 1 e 4 existem os números 2 e 3, já o endereço dos entrevistados em uma pesquisa não tem topologia (a não ser que eles morem em Brasília). Em geral, as pessoas usam números (ou vetores) para representar valores de conjuntos com topologia, e nomes para conjuntos sem topologia, e, em geral conjuntos sem topologia são limitados e discretos (ou seja, finitos).

Agora, se você quer encontrar uma solução para algum problema, você precisa avaliar cada ponto do espaço de busca, ou seja, dar uma "nota" para eles. No caso da equação acima, poderia-se dar uma nota zero a pontos que não resolvem a equação, e 1 a pontos que resolvem a equação (só x = -1/2). De forma alternativa, poderia-se subistituir o x dos dois lados da igualdade, e usar a diferença (o módulo dela) entre os dois valores como nota (eu não disse que notas altas são melhores que baixas). É fácil perceber que a segunda nota contém muito mais informação do que a primeira (sim, informação é algo que se pode medir, mas isso dá uma seqüência inteira de artigos), e em geral, quanto mais informação se coloca na nota, melhor. Isso é fácil de ver neste caso, onde com a segunda nota pode-se saber se a busca está se aproximando ou afastando da solução observando se a nota aumenta ou diminui, já com a primeira nota, isso não é posível.

Depois de cada ponto do espaço de busca avaliado, o resultado é uma "superfície", onde as soluções são os ponto mais altos (ou mais baixos) desta superfície. Estes pontos têm a característica de que todos os seus vizinhos têm nota menor (ou maior) do que a sua, o que torna fácil identificá-los. Mas isso também pode acontecer com outros pontos, mesmo sem eles serem soluções, como na figura abaixo:

Os pontos A, B e C da figura acima têm a característica de ter maior nota do que seus vizinhos. Pontos com esta característica são chamados de "máximos", A e C são "máximos locais", mas só o ponto B é solução, chamado de "máximo global". De forma equivalente, há também 3 mínimos neste gráfico, sendo um deles global e dois locais. Existe um grande número de algorítmos que resolvem problemas em que todos os máximos (ou mínimos) locais são também globais. Estes algorítmos costumam ser rasoavelmente rápidos e símples. Mas há muito poucos algorítmos que resolvem problemas com máximos não globais, e estes costumam ser lentos e não garantir que encontrem a resposta. Alias, em geral para garantir que um máximo seja global em um problema em que podem haver máximos locais é preciso testar todos os pontos do espaço de busca.

Pronto, fim (ou quase) da teoria. Nos próximos artigos eu vou ser mais prático e falar de algorítmos e implementações... Até lá.