Alai

Em 2004, a equipe de Pesquisa da Microsoft e de Pesquisa na Web da Microsoft iniciou um esforço conjunto para melhorar a relevância dos nossos resultados de pesquisa na Web. Seguiu-se um esforço sustentado que, nos anos seguintes, resultou no nosso envio de três gerações de algoritmos de ranking de busca na web, culminando nos conjuntos de árvores impulsionados que o Bing utiliza hoje em dia. Nós chamamos o primeiro destes algoritmos de ranking de RankNet. Recentemente o RankNet, que foi publicado na Conferência Internacional sobre Aprendizagem de Máquinas (ICML) em 2005, ganhou o prêmio “Test of Time” do ICML, um prêmio dado a cada ano àquele único trabalho apresentado na conferência dez anos antes, que foi considerado como tendo tido o maior impacto acadêmico geral ao longo dos anos intermediários. Esta é uma grande honra e também uma oportunidade de olhar para trás e avaliar o nosso progresso ao longo da última década. Neste artigo, eu gostaria de contar esta história.

Trabalhos de pesquisa na web, essencialmente levando a consulta do usuário e avaliando a relevância de cada documento indexado para ela. Nem todas as páginas da web estão no índice, mas o índice contém centenas de bilhões de documentos, armazenados em uma estrutura de dados especial para fazer uma pesquisa rápida. Como os principais resultados devem ser apresentados ao usuário em algumas centenas de milissegundos, isso requer um processo de filtragem e classificação extremamente eficiente. Os classificadores aqui descritos trabalham em um subconjunto (ainda grande) dos documentos, escolhidos usando este rápido processo de filtragem inicial. Basicamente, um classificador funciona através de uma lista de números, cada um dos quais mede a qualidade de uma determinada consulta/documento de uma determinada forma (por exemplo, um número binário que representa se a consulta contém ou não uma palavra no título do documento). O classificador então mapeia essa lista de números para uma única medida de relevância, que é então utilizada para classificar todos os documentos para essa consulta. A lista ordenada de números que o classificador mapeia para uma única pontuação é chamada de vector de característica.

Assim, quando usado em tempo de execução, para uma determinada consulta, o classificador leva o vector de característica para cada par de consulta/documento e mapeia-o para um número que capta a relevância desse documento para a consulta. O RankNet é um modelo de rede neural feedforward. Antes de poder ser usado, seus parâmetros devem ser aprendidos usando uma grande quantidade de dados etiquetados, chamados de conjunto de treinamento. O conjunto de treinamento consiste de um grande número de pares de consulta/documento, onde para cada par, um número que avalia a qualidade da relevância do documento para aquela consulta é atribuído por especialistas humanos. Embora a etiquetagem dos dados seja uma tarefa lenta e de grande intensidade humana, o treinamento da rede, dado os dados etiquetados, é totalmente automático e bastante rápido. O sistema usado pela Microsoft em 2004 para treinar o classificador foi chamado de The Flying Dutchman. Descobrimos que, enquanto o The Flying Dutchman levou vários dias e um cluster para produzir um modelo treinado, o RankNet foi capaz de produzir um modelo de ranking em apenas algumas horas usando apenas uma máquina. O RankNet também melhorou significativamente a relevância em relação ao ranker usado anteriormente, uma vez que as redes neurais podem modelar uma grande variedade de mapeamentos possíveis, enquanto o sistema anterior estava limitado a apenas mapeamentos lineares.

Até agora tudo bem, mas será que poderíamos ter feito melhor? A resposta é Sim, mas para ver porquê, preciso de explicar um pouco sobre como a RankNet é treinada. Para cada consulta do conjunto de treinamento, para cada par de documentos a serem classificados para aquela consulta, RankNet é mostrado os dois vetores de característica e então ele ajusta um pouco seus parâmetros, usando um método chamado Stochastic Gradient Descent (SGD), para que a pontuação de saída ajustada para as duas características se mova na direção certa – ou seja, a pontuação para o documento mais relevante aumenta, e para o menos, diminui. Mas isso significa que o RankNet irá trabalhar arduamente para elevar documentos altamente relevantes que são muito baixos na classificação, e também para baixar a pontuação alta, mas documentos menos relevantes. Ao gastar os seus recursos desta forma, não dá tanta atenção como deveria apenas aos poucos links que são mostrados ao utilizador. De facto, na altura, a nossa métrica de avaliação era uma pontuação chamada NDCG, que dá um único número que avalia a qualidade geral da classificação, com uma ênfase muito maior nos poucos resultados superiores que são mostrados ao utilizador. O NDCG é, portanto, uma medida mais natural para a pesquisa na web do que o erro de pares. Isto nos apresentou um desafio: SGD se resume a uma busca em um espaço contínuo, mas NDCG é fundamentalmente uma medida discreta, na medida em que seu valor só muda quando pelo menos dois documentos mudam de posição na lista classificada. Alterações suficientemente pequenas nas pontuações dos modelos não dão nenhuma mudança no NDCG, e como o SGD funciona explorando pequenas alterações nas pontuações, é difícil ver como otimizar o NDCG usando SGD.

Encontramos uma resposta para este quebra-cabeça, que chamamos de LambdaRank. O truque era notar que todo o procedimento de treinamento para uma rede neural só precisa dos gradientes da função custo, não da função custo em si. Você pode pensar nesses gradientes como pequenas setas anexadas a cada documento da lista de classificação, indicando a direção que gostaríamos que esses documentos fossem movidos. O LambdaRank simplesmente pegou os gradientes do RankNet, que sabíamos que funcionavam bem, e escalou-os pela mudança no NDCG encontrada ao trocar cada par de documentos. Descobrimos que esse treinamento gerou modelos com relevância significativamente melhorada (conforme medido pelo NDCG) e teve um bônus adicional de descobrir mais um truque que melhorou a velocidade geral de treinamento (tanto para o RankNet quanto para o LambdaRank). Além disso, surpreendentemente, encontramos evidências empíricas (ver também este artigo) de que o procedimento de treinamento realmente otimiza o NDCG, embora o método, embora intuitivo e sensato, não tenha tal garantia.

Até agora tudo bem, mas, novamente, poderíamos ter feito melhor? A resposta foi novamente Sim. Conhecíamos uma classe de modelos chamados conjuntos de árvores impulsionadas que eram conhecidos por fazer classificadores multiclasse muito fortes. O que acontece se você apenas tratar o problema de classificação como um problema de classificação multiclasse, com uma classe para cada um dos cinco níveis de relevância identificados no conjunto de treinamento? Descobrimos que isso deu melhores resultados sobre o LambdaRank (especialmente um sabor chamado classificação multiclasse ordinal). As árvores potenciadas têm ainda a vantagem de poderem lidar facilmente com características categóricas e outros tipos de características discretas, que são menos adequadas às redes neurais. Acreditávamos que estes resultados se deviam à melhor adequação desta classe de modelos aos nossos dados e, portanto, a questão natural era: podemos combinar modelos de árvores impulsionadas, com a ideia do LambdaRank, para obter o melhor de ambos os mundos? O treinamento de um modelo em árvore impulsionado também pode ser visto como uma forma de SGD, e assim a resposta foi Sim, na forma de um modelo que chamamos de LambdaMART. O LambdaMART tinha uma vantagem adicional: o treinamento de modelos de conjuntos de árvores pode ser muito significativamente acelerado sobre o equivalente da rede neural (este trabalho, liderado por O. Dekel, ainda não está publicado). Isso nos permite treinar com conjuntos de dados muito maiores, o que mais uma vez nos dá uma melhor precisão de classificação.

Como nossos classificadores se comparam com outros na indústria? Em 2010, o Yahoo! organizou um desafio de aprender a classificar, um dos quais foi desenhado para ver quem tinha o melhor algoritmo de ranking de busca na web. 1.055 equipes inscritas para o desafio. Nossa equipe venceu o desafio, usando um conjunto de modelos LambdaMART.

Looking back over the last decade, talvez a lição técnica mais saliente seja a importância da velocidade de treinamento. Um treino mais rápido permite tanto uma maior experimentação como a utilização de conjuntos de dados maiores. Acredito que estes dois factores são no final mais importantes do que os algoritmos subjacentes utilizados, desde que estes últimos sejam modelos suficientemente expressivos para a tarefa em questão. A outra “lição de vida” que retiro desta experiência é a importância de ser persistente, mas acima de tudo, a importância do dom de poder trabalhar com colegas maravilhosos, nos grupos de produtos, na Microsoft Research e na academia.

Chris Burges é Pesquisador Principal e Gerente de Pesquisa na Microsoft Research, onde está desde 2000. Antes disso ele trabalhou na AT&T Bell Labs, na qual ele se juntou em 1986. Antes disso, foi pós-doutorando no Departamento de Física Teórica do MIT, ao qual ingressou após obter seu doutorado em Física pela Brandeis, depois de se formar com Honra de Primeira Classe em Física e Matemática, em Oxford. Seus interesses abrangem a engenharia de sistemas de grandes redes de comunicação (AT&T ainda usa seus algoritmos para rotear várias redes chave), redes neurais para reconhecimento de escrita à mão e impressão de máquinas (ele trabalhou em um sistema agora usado para ler milhões de cheques diariamente, e de fato sua longa descida no aprendizado de máquinas foi desencadeada por uma demonstração particularmente legal de uma rede neural reconhecendo dígitos escritos à mão no início dos anos 90), suporte a máquinas vetoriais (ele teve a sorte de trabalhar com Vladimir Vapnik, co-criador da SVM, no início, e escreveu um tutorial que algumas pessoas gostaram), impressão digital de áudio (seu trabalho é atualmente usado no Xbox e no Windows Media Player para identificar músicas), verificação de alto-falantes, recuperação de informações e ranking (seu algoritmo de ranking é atualmente usado pelo Bing para pesquisa na web). A paixão atual de Chris é desenvolver novas abordagens para a compreensão escalável e acionável do texto, que embora reconhecidamente ambiciosa, ainda é provável que nos ensine algo, a menos que deixemos de tentar. Chris foi Co-Presidente do Programa de Sistemas de Processamento de Informação Neural 2012 e Co-Presidente Geral do NIPS 2013.

Para mais notícias de pesquisa em ciência da computação, visite ResearchNews.com.