BRPI0708074A2

BRPI0708074A2 - propagação de releváncia de documentos rotulados para documentos não rotulados

Info

Publication number: BRPI0708074A2
Application number: BRPI0708074-3A
Authority: BR
Inventors: Wang Jue; Li Mingjing; Ma Wei-Ying; Li Zhiwei
Original assignee: Microsoft Corporation
Priority date: 2006-02-27
Filing date: 2007-02-27
Publication date: 2011-05-17
Also published as: US8019763B2; US20070203940A1; RU2008134886A; AU2007221017A1; CA2640244A1; WO2007100848A3; JP2009528628A; EP1999654A2; KR20080106192A; NO20083313L; EP1999654A4; WO2007100848A2

Abstract

PROPAGAçãO DE RELEVáNCIA DE DOCUMENTOS ROTULADOS PARA DOCUMENTOS NãO ROTULADOS. São fornecidos um método e sistema para propagar a relevância de documentos rotulados em relação a uma consulta até documentos não rotulados. O sistema de propagação fornece dados de treinamento que incluem consultas, documentos rotulados com suas relevâncias em relação às consultas, e documentos não rotulados. Então, o sistema de propagação calcula a similaridade entre pares de documentos nos dados de treinamento. Então, o sistema de propagação propaga a relevância dos documentos rotulados em documentos similares, mas não rotulados. O sistema de propagação pode propagar iterativamente rótulos dos documentos até que os rótulos convirjam em uma solução. Então, os dados de treinamento com as relevâncias propagadas podem ser usados para treinar uma função de classificação.

Description

"PROPAGAÇÃO DE RELEVÂNCIA DE DOCUMENTOS ROTULADOS PARADOCUMENTOS NÃO ROTULADOS"

ANTECEDENTES DA INVENÇÃO

Muitos serviços de motor de busca, tais como Google e Overture, fornecem buscade informação que é acessível por meio da Internet. Estes serviços de motor de busca per-mitem que usuários busquem páginas de exibição, tais como páginas da Internet, que po-dem ser de interesse dos usuários. Depois que um usuário submete uma solicitação de bus-ca (isto é, uma consulta) que inclui termos de busca, o serviço de motor de busca identificapáginas da Internet que podem estar relacionadas àqueles termos da busca. Para identificarrapidamente páginas da Internet relacionadas, os serviços de motor de busca podem manterum mapeamento de palavras-chaves para as páginas da Internet. Este mapeamento podeser gerado pelo "esquadrinhamento" da Internet (isto é, a rede mundial de computadores)para identificar as palavras-chaves de cada página da Internet. Para esquadrinhar a Internet,um serviço de motor de busca pode usar uma lista de páginas raízes da Internet para identi-ficar todas as páginas da Internet que são acessíveis por meio de daquelas páginas raízesda Internet. As palavras-chaves de qualquer página da Internet em particular podem ser i-dentificadas usando várias técnicas de recuperação de informação bem conhecidas, taiscomo identificação das palavras de um cabeçalho, as palavras supridas nos metadados dapágina da Internet, as palavras que estão destacadas, e assim por diante. O serviço de mo-tor de busca identifica páginas da Internet que podem ser relacionadas à solicitação de bus-ca com base em quão bem as palavras-chaves de uma página da Internet casam com aspalavras da consulta. Então, o serviço de motor de busca exibe ao usuário ligações para aspáginas da Internet identificadas em uma ordem que é baseada em uma classificação quepode ser determinada por suas relevâncias em relação à consulta, à popularidade, à impor-tância e/ou a alguma outra medida.

Estas técnicas bem conhecidas para classificar páginas da Internet são PageRank,HITS ("Busca de Tópico Induzida por Hiperligação"), e DirectHIT. PageRank é baseada noprincípio de que páginas da Internet terão ligações para (isto é, "ligações de saída") impor-tantes páginas da Internet. Assim, a importância da página da Internet é baseada no númeroe na importância de outras páginas da Internet que se ligam àquela página da Internet (istoé, "ligações de entrada"). De uma forma simples, as ligações entre as páginas da Internetpodem ser representadas pela matriz de adjacência A, em que Aij representa o número deligações de saída da página da Internet /' até a página da Internet / A contagem de impor-tância Wj para a página da Internet j pode ser representada pela seguinte equação:

Wj = rLlAijWl

Esta equação pode ser resolvida por cálculos iterativos com base na seguinte e-quação:A^tW = W

em que wéo vetor de contagens de importância para as páginas da Internet e é oprincipal autovetor de At.

Esta técnica HITS é adicionalmente baseada no princípio de que uma própria pági-na da Internet que tem muitas ligações a outras importantes páginas da Internet pode serimportante. Assim, HITS divide "importância" das páginas da Internet em dois atributos rela-cionados, "concentrador" e "autoridade". "Concentrador" é medido pela contagem de "autori-dade" das páginas da Internet em que uma página da Internet se liga, e "autoridade" é me-dida pela contagem do "concentrador" das páginas da Internet que se ligam à página daInternet. Ao contrário da PageRank1 que calcula a importância das páginas da Internet inde-pendentemente da consulta, HITS calcula a importância com base nas páginas da Internetdo resultado é das páginas da Internet que são relacionadas às páginas da Internet do resul-tado seguindo as ligações de entrada e de saída. HITS submete uma consulta a um serviçode motor de busca e usa as páginas da Internet do resultado como o conjunto inicial de pá-ginas da Internet. HITS adiciona no conjunto aquelas páginas da Internet que são destinosdas ligações de entrada e aquelas páginas da Internet que são as fontes das ligações desaída das páginas da Internet do resultado. Então, HITS calcula a classificação da autorida-de e do concentrador de cada página da Internet usando um algoritmo iterativo. As conta-gens da autoridade e do concentrador podem ser representadas pelas seguintes equações:

<formula>formula see original document page 3</formula>

em que a(p) representa a contagem da autoridade para a página da Internet ρ eh(p) representa a contagem do concentrador para a página da Internet p. HITS usa umamatriz de adjacência A para representar as ligações. A matriz de adjacência é representadapela seguinte equação:

<formula>formula see original document page 3</formula>

Os vetores a e h correspondem às contagens da autoridade e do concentrador,respectivamente, de todas as páginas da Internet no conjunto e podem ser representadospelas seguintes equações:

A = ATh e h = Aa

Assim, a e h são autovetores das matrizes AtA e AAT. HITS também pode ser modi-ficado para o fator na popularidade de uma página da Internet medida pelo número de visi-tas. Com base na análise dos dados através de cliques, bq da matriz de adjacência podeaumentar toda vez que um usuário navega da página da Internet i até a página da Internet/DirectHIT classifica páginas da Internet com base no histórico passado do usuáriocom resultados de consultas similares. Por exemplo, se usuários que submetem consultassimilares selecionam primeiro, tipicamente, a terceira página da Internet do resultado, então,o histórico deste usuário será uma indicação de que a terceira página da Internet deve terclassificação mais alta. Como um outro exemplo, se usuários que submetem consultas simi-lares gastam, tipicamente, a maior parte do tempo visualizando a quarta página da Internetdo resultado, então, o histórico deste usuário será uma indicação de que a quarta página daInternet deve ter classificação mais alta. DirectHIT deriva os históricos do usuário da análisedos dados através do clique.

Algumas técnicas de classificação usam algoritmos de aprendizado de máquina pa-ra aprender uma função de classificação dos dados de treinamento que incluem consultas,vetores de recurso que representam páginas e, para cada consulta, uma classificação paracada página. Uma função de classificação serve como um mapeamento dos recursos deuma página para sua classificação para uma dada consulta. O aprendizado de uma funçãode classificação foi considerado, em parte, como um problema de regressão para aprendero mapeamento de um vetor de recurso até um elemento de um conjunto ordenado de classi-ficações numéricas. Algumas técnicas com base em regressão tentam fornecer uma conta-gem de relevância absoluta que pode ser usada para classificar páginas. Entretanto, umafunção de classificação não precisa fornecer uma contagem de relevância absoluta, mas,em vez disto, precisa fornecer somente uma classificação relativa das páginas. Assim, estastécnicas com base em regressão resolvem um problema que é mais difícil do que o neces-sário.

Algoritmos de aprendizagem de máquina para uma função de classificação usamconsultas, vetores de recurso e classificações de relevância rotuladas pelo usuário comodados de treinamento. Para gerar os dados de treinamento, consultas podem ser submeti-das a um motor de busca que gera as páginas do resultado da busca. Então, os algoritmosgeram os vetores de recurso para as páginas e inserem, a partir de um usuário, as conta-gens de relevância para cada página. Uma dificuldade com uma abordagem como esta éque um motor de busca pode retornar centenas de páginas como seu resultado de busca.Pode ser bastante oneroso ter um rótulo de usuário em todas as páginas de um resultado debusca. Além do mais, pode ser difícil para um usuário avaliar precisamente a relevância deum grande número de páginas como este. Embora um usuário possa rotular somente umapequena parte das páginas, o aprendizado com base em uma pequena parte como estapode não fornecer uma função de classificação precisa.

SUMÁRIO DA INVENÇÃO

São fornecidos um método e sistema para propagar a relevância dos documentosrotulados a uma consulta para a relevância dos documentos não rotulados. Este sistema depropagação fornece dados de treinamento que incluem consultas, documentos rotuladoscom suas relevâncias em relação às consultas e documentos não rotulados. Então, o siste-ma de propagação calcula a similaridade entre pares de documentos nos dados de treina-mento. Então, o sistema de propagação propaga a relevância dos documentos rotulados adocumentos similares, mas não rotulados. O sistema de propagação pode propagar iterati-vãmente rótulos dos documentos até que os rótulos convirjam em uma solução. Então, osdados de treinamento com as relevâncias propagadas podem ser usados para treinar umafunção de classificação.

Este Sumário é fornecido para introduzir uma seleção de conceitos de uma formasimplificada que é adicionalmente descrita a seguir na Descrição Detalhada. Não pretende-se que este Sumário identifique recursos chaves ou recursos essenciais do assunto emquestão reivindicado, nem pretende-se que seja usado como um auxílio na determinação doescopo do assunto em questão reivindicado.

DESCRIÇÃO RESUMIDA DOS DESENHOS

A figura 1 é um diagrama que ilustra uma parte de um gráfico dos documentos.

a figura 2 é um diagrama de blocos que ilustra componentes do sistema de propa-gação em uma modalidade.

A figura 3 é um fluxograma que ilustra o processamento do componente da funçãode criar classificação do sistema de propagação em uma modalidade.

A figura 4 é um fluxograma que ilustra o processamento do componente de propa-gar relevância do sistema de propagação em uma modalidade.

A figura 5 é um fluxograma que ilustra o processamento do componente de constru-ir gráfico do sistema de propagação em uma modalidade.

A figura 6 é um fluxograma que ilustra o processamento do componente de gerarponderações para gráfico do sistema de propagação em uma modalidade.

A figura 7 é um fluxograma que ilustra o processamento do componente de norma-lizar ponderações do gráfico do sistema de propagação em uma modalidade.

A figura 8 é um fluxograma que ilustra o processamento do componente de propa-gar relevância com base em gráfico do sistema de propagação em uma modalidade.

DESCRIÇÃO DETALHADA

São fornecidos um método e sistema para propagar regressão estatística de docu-mentos rotulados a uma consulta para documentos não rotulados. Em uma modalidade, osistema de propagação fornece dados de treinamento que incluem consultas, documentos(representados por vetores de recurso) rotulados com suas relevâncias em relação às con-sultas, e documentos não rotulados. Por exemplo, o sistema de propagação pode submeteruma consulta a um motor de busca e usar o resultado da busca como os documentos (porexemplo, páginas da Internet). Então, o sistema de propagação pode solicitar que um usuá-rio rotule parte dos documentos do resultado da busca com base em suas relevâncias emrelação à consulta. Então, o sistema de propagação calcula a similaridade entre pares dedocumentos nos dados de treinamento. Por exemplo, o sistema de propagação pode repre-sentar cada documento por um vetor de recurso e pode calcular a similaridade entre docu-mentos com base na distância Euclidiana no espaço do recurso ou com base em uma métri-ca de similaridade co-seno. Então, o sistema de propagação propaga a relevância dos do-cumentos rotulados para documentos similares, mas não rotulados. O sistema de propaga-ção pode propagar iterativamente rótulos dos documentos até que os rótulos convirjam emuma solução. Então, os dados de treinamento com as relevâncias propagadas podem serusados para treinar uma função de classificação. Desta maneira, o sistema de propagaçãopode aumentar automaticamente os dados de treinamento com dados de treinamento adi-cionais com base nas similaridades entre documentos.

Em uma modalidade, o sistema de propagação representa os documentos usandoum gráfico de documento com cada nó representando um documento e cada seta represen-tando a similaridade entre os documentos representados pelos nós conectados. O sistemade propagação pode representar o gráfico como uma matriz quadrática com uma linha ecoluna para cada documento na qual cada valor não zero indica uma seta entre o nó da li-nha e o nó da coluna. O sistema de propagação pode definir setas para o gráfico usandovárias técnicas. Por exemplo, o sistema de propagação pode considerar que o gráfico estácompletamente conectado, em cujo caso cada nó tem uma seta para cada outro nó. Comoum outro exemplo, o sistema de propagação pode considerar que os nós estão conectadospor meio de uma árvore de abrangência mínima. Em uma modalidade, o sistema de propa-gação considera que os nós estão conectados usando um algoritmo do vizinho k mais pró-ximo. Em particular, o sistema de propagação identifica os k vizinhos mais próximos paracada nó e adiciona uma seta de cada nó até cada um dos seus k vizinhos mais próximos.Então, o sistema de propagação calcula ponderações para as setas com base na similarida-de entre os documentos representados pelas setas conectadas. O sistema de propagaçãopode usar várias técnicas para determinar a similaridade entre os documentos. Em umamodalidade, o sistema de propagação usa uma métrica de distância Euclidiana com base narepresentação do vetor de recurso dos documentos em um espaço do recurso. O sistema depropagação armazena a similaridade como os valores da matriz quadrática resultante emuma matriz de similaridade ou de afinidade. O sistema de propagação também pode norma-lizar a matriz de similaridade. O sistema de propagação também pode ajustar os valoresdiagonais em 0 ou impedir auto-reforço durante a propagação da relevância.

Depois de gerar a matriz de similaridade, o sistema de propagação propaga a rele-vância dos documentos rotulados até os documentos não rotulados usando um algoritmo depropagação com base em classificação de cópias. Um algoritmo com base em classificaçãode cópias é descrito em He, J., Li, M., Zhang, H.J., et al., "Manifold-Ranking Based ImageRetrieval", Proc. of the 12* Annual ACM International Conf. On Multimedia, 2004. Inicialmen-te, o sistema de propagação ajusta a regressão estatística dos documentos rotulados dacontagem de relevância fornecida pelo usuário e a relevância dos documentos não rotuladosem 0. Então, o sistema de propagação difunde a relevância dos documentos rotulados aseus documentos não rotulados conectados fatorando na similaridade como indicado pelamatriz de similaridade. O sistema de propagação difunde iterativamente a contagem de rele-vância até que as contagens de relevância convirjam em uma solução. As contagens derelevância resultantes dos documentos não rotulados estarão em proporção com a probabi-lidade de que eles sejam relevantes à mesma consulta que os documentos rotulados. As-sim, um documento não rotulado que é muito similar a muitos documentos rotulados comaltas contagens de relevância terão uma alta contagem de relevância. Inversamente, umdocumento não rotulado que não é muito similar a nenhum documento rotulado terá umabaixa contagem de relevância.

O sistema de propagação pode representar similaridade usando um núcleo de La-place, que pode ser representado pela seguinte equação:(copiar fórmula pg 7)(1)

em que x„ e x,, representam a I6sima dimensão de x, e de Xjl respectivamente, t repre-senta a dimensionalidade do espaço do recurso, e p, representa um parâmetro positivo quereflete as ponderações das diferentes dimensões no cálculo da similaridade. Assim, o siste-ma de propagação representa a ponderação das setas pela seguinte equação:(copiar fórmula pg 7)(2)

em que Wij representa a similaridade entre os documentos /' e j. O sistema de pro-pagação pode omitir o coeficiente constante 1/2p, desde que seu efeito na matriz de simila-ridade W seja neutralizado pela normalização da matriz. O sistema de propagação normali-za a matriz de similaridade como representado pela equação:S = D"1/2WD"1/2(3)

em que S representa a matriz de similaridade normalizada e D representa uma ma-triz diagonal em que (/,/) é igual à soma da i-ésima linha da matriz de similaridade W. A nor-malização normaliza as similaridades para ser relativa à similaridade dos documentos co-nectados.

O sistema de propagação pode representar cada documento como um vetor de re-curso χ da dimensão t que forma um ponto no espaço Euclidiano. Para uma consulta, o sis-tema de propagação recebe o conjunto de resultado dos documentos (copiar fórmula pg 8).Os primeiros m pontos (no espaço de recurso) representam documentos rotulados pelo u-suário, e os últimos η pontos (no espaço de recurso) representam documentos não rotula-dos. O sistema de propagação também recebe um vetor de rótulo correspondente (copiarfórmula pg 8). Os últimos η rótulos têm o valor de 0 para representar documentos não rotu-lados. O sistema de propagação também pode permitir a especificação dos rótulos negati-vos, em vez de somente rótulos positivos, para representar exemplos negativos de relevân-cia. O sistema de propagação representa distância entre documentos no espaço de recursocomo d: χ χ χ -> □, que atribui a cada par de pontos χί e χ/, uma distância d(xi, xj), e repre-senta uma função de classificação dos documentos como /: χ que atribui a cada pontoχ/', uma contagem de classificação //'. O problema do aprendizado da função de classifica-ção é aprender /: χ □ de um conjunto de consultas com os recursos X = {χ,} e os rótulosy = {Yq}. o sistema de propagação representa o limite da propagação da relevância pelaseguinte equação:

f° = (1-a)(I-aS)V(4)

em que f° representa o limite da relevância, y representa os rótulos iniciais e a re-presenta um fator de decadência. Em virtude de ser computacionalmente difícil de calcular oinverso da matriz de similaridade normalizada S, o sistema de propagação aproxima f° u-sando uma expansão da série Taylor. O sistema de propagação pode representar a expan-são da série Taylor pela seguinte equação:

f°= (I - ffS)~1y

= (I + aS + Ct2S2 + ...)y( 5)

= y+ ffSy +CTS(CTSy) + ...

O sistema de propagação resolve iterativamente f° até que ela convirja em uma so-lução ou por um número fixo de iterações.

Uma vez que as relevâncias são propagadas, o sistema de propagação rotuladapode usar os conjuntos de dados de treinamento (vetores de recurso de consulta e rotula-dos) para treinar uma função de classificação. Uma função de classificação pode ser imple-mentada como um motor do vetor de suporte, como um classificador de regulação adaptati-va, como um classificador de rede neural, e assim por diante. Um motor vetorial de suporteopera encontrando uma hipersuperfície no espaço de possíveis entradas. A hipersuperfícietenta dividir os exemplos positivos dos exemplos negativos pela maximização da distânciaentre os mais próximos exemplos positivos e negativos em relação à hipersuperfície. Istopermite a correta classificação dos dados que são similares, mas não idênticos, aos dadosde treinamento. Várias técnicas podem ser usadas para treinar um motor vetorial de suporte.Uma técnica usa um algoritmo de otimização mínima seqüencial que decompõe o grandeproblema de programação quadrática em uma série de pequenos problemas de programa-ção quadrática que podem ser analiticamente resolvidos (Veja Seqüencial Minimal Optimiza-tion, em http://research.microsoft.com/~iplatt/smo.html).

Regulação adaptativa é um processo iterativo que executa múltiplos testes em umacoleção de dados de treinamento. A regulação adaptativa transforma um fraco algoritmo deaprendizado (um algoritmo que desempenha em um nível somente um pouco melhor do queo acaso) em um forte algoritmo de aprendizado (um algoritmo que exibe uma baixa taxa deerro). O fraco algoritmo de aprendizado é executado em diferentes subconjuntos de dadosde treinamento. O algoritmo concentra cada vez mais nestes exemplos nos quais seus pre-decessores tendiam a mostrar erros. O algoritmo corrige os erros feitos pelos fracos apren-dedores anteriores. O algoritmo é adaptativo em virtude de ele ajustar as taxas de erro dosseus predecessores. A regulação adaptativa combina regras grosseiras e moderadamenteimprecisas de manuseio para criar um algoritmo de alto desempenho. A regulação adaptati-va combina os resultados de cada teste separadamente executado em um único classifica-dor muito preciso.

Um modelo de rede neural tem três componentes principais: arquitetura, função decusto e algoritmo de busca. A arquitetura define a forma funcional relacionando as entradasàs saídas (em termos de topologia de rede, conectividade da unidade e funções de ativa-ção). A busca em espaço de ponderação para um conjunto de ponderações que minimiza afunção objetiva é um processo de treinamento. Um modelo de rede neural pode usar umarede de função de base radial ("RBF") e uma descida de gradiente padrão como sua técnicade busca.

A figura 1 é um diagrama que ilustra um gráfico dos documentos retornados como oresultado da busca de uma consulta. Neste exemplo, o subgráfico 100 representa uma partedos documentos retornados no resultado da busca. Os nós 101-112 representam 12 docu-mentos do resultado da busca. Os nós 101 e 108 representam documentos rotulados. Odocumento representado pelo nó 101 foi rotulado com a contagem de relevância de 0,75, eo documento representado pelo nó 106 foi rotulado com a contagem de relevância de 0,6. Osistema de propagação gerou as setas entre os nós usando um algoritmo de vizinho maispróximo. Neste exemplo, os nós 102, 103 e 104 são, cada qual, um dos vizinhos k mais pró-ximos em relação ao nó 101, mas os nós 105-112 não são um dos vizinhos k mais próxi-mos. Então, o sistema de propagação calculou a similaridade entre os nós conectados u-sando um algoritmo de classificação de similaridade. Por exemplo, o nó 101 está conectadono nó 102 com uma seta com a ponderação de 0,8, que indica a similaridade entre os nósconectados.

A figura 2 é um diagrama de blocos que ilustra componentes do sistema de propa-gação em uma modalidade. O sistema de propagação 230 é conectado em armazenamen-tos de documento 210 (por exemplo, locais da Internet) por meio da ligação de comunica-ções 220 (por exemplo, Internet). O sistema de propagação inclui um componente de coletade dados de treinamento 231, um armazenamento de dados de treinamento 232 e um índicede documento 233. O índice de documento contém um índice dos documentos (por exem-plo, páginas da Internet) nos armazenamentos de documento. O índice de documento podeser gerado por um esquadrinhador da Internet. O índice de documento pode incluir um vetorde recurso para cada documento que for usado para treinar uma função de classificação. Osvetores de recurso podem representar muitos diferentes tipos de recursos dos documentos,tais como freqüência de documento invertida, palavras-chaves, tamanho da fonte, e assimpor diante. O componente de coleta de dados de treinamento submete consultas a um motorde busca (não mostrado) e recebe documentos que casam com as consultas. O motor debusca pode ser independente do sistema de propagação. Em um caso como este, o sistemade propagação pode gerar vetores de recurso dinamicamente a partir dos resultados dabusca. O componente de coleta de dados de treinamento pode solicitar que um usuário rotu-le a relevância de alguns dos documentos que casam com as consultas. O componente decoleta de dados de treinamento armazena as consultas, os resultados da busca (por exem-plo, vetores de recurso) e rótulos no armazenamento de dados de treinamento. O sistemade propagação também inclui um componente de propagação de relevância 235, um com-ponente de construção de gráfico 236, um componente de geração de ponderações paragráfico 237, um componente de normalização de ponderações de gráfico 238 e um compo-nente de propagação com base no gráfico 239. O componente de propagação de relevânciapropaga a relevância dos documentos rotulados até os documentos não rotulados que estãoarmazenados no armazenamento dos dados de treinamento. O componente de propagaçãode relevância invoca o componente de construção de gráfico para construir um gráfico queinclui setas que representam os documentos de um resultado de busca. Então, o componen-te de propagação de relevância invoca o componente de geração de ponderações para grá-fico para gerar as ponderações iniciais para as setas do gráfico. O componente de propaga-ção de relevância invoca o componente de normalização de ponderações do gráfico paranormalizar as ponderações geradas. Então, o componente de propagação de relevânciainvoca o componente de propagação de relevância com base em gráfico para realizar a pro-pagação de relevância real dos documentos rotulados até os documentos não rotulados. Osistema de propagação também inclui um componente de criação de função de classificação241 e uma função de classificação 242. A criação da função de classificação usa os dadosde treinamento com a relevância propagada para criar uma função de classificação.

O dispositivo de computação no qual o sistema de propagação pode ser implemen-tado pode incluir uma unidade central de processamento, memória, dispositivos de entrada(por exemplo, teclado e dispositivo de apontamento), dispositivos de saída, (por exemplo,dispositivo de exibição) e dispositivo de armazenamento (por exemplo, unidades de disco).A memória e o dispositivo de armazenamento são mídias legíveis por computador que po-dem conter instruções que implementam o sistema de propagação. Além do mais, as estru-turas de dados e estruturas de mensagem podem ser armazenadas ou transmitidas pormeio de uma mídia de transmissão de dados, tais como um sinal em uma ligação de comu-nicações. Várias ligações de comunicações podem ser usadas, tais como a Internet, umarede de área local, uma rede de área ampla e uma conexão discada ponto a ponto.

O sistema de propagação pode fornecer serviços a vários sistemas ou dispositivoscomputacionais, incluindo computadores pessoais, computadores servidores, dispositivos demão ou portáteis, sistemas multiprocessadores, sistemas com base em microprocessador,dispositivos eletrônicos programáveis pelo cliente, PCs em rede, minicomputadores, compu-tadores de grande porte, ambientes de computação distribuída que incluem qualquer umdos sistemas ou dispositivos expostos, e congêneres.

O sistema de propagação pode ser descrito no contexto geral das instruções execu-táveis por computador, tais como módulos de programa, executadas por um ou mais compu-tadores ou outros dispositivos. No geral, os módulos de programa incluem rotinas, progra-mas, objetos, componentes, estrutura de dados e assim por diante, que realizam tarefas emparticular ou implementam tipos de dados abstratos em particular. Tipicamente, a funcionali-dade dos módulos de programa pode ser combinada ou distribuída como desejado em vá-rias modalidades.

A figura 3 é um fluxograma que ilustra o processamento do componente de criaçãode função de classificação do sistema de propagação em uma modalidade. O componentede criação de função de classificação coleta dados de treinamento, propaga a relevânciados documentos rotulados até os documentos não rotulados e, então, treina uma função declassificação. No bloco 301, o componente coleta os dados de treinamento. No bloco 302, ocomponente insere rótulos para um subconjunto de dados de treinamento. No bloco 303, ocomponente invoca rótulos para um subconjunto dos dados de treinamento. No bloco 303, ocomponente invoca o componente de propagação de relevância para propagar a relevânciados documentos rotulados até os documentos não rotulados. No bloco 304, o componentetreina a função de classificação usando as relevâncias propagadas.

A figura 4 é um fluxograma que ilustra o processamento do componente de propa-gação de relevância do sistema de propagação em uma modalidade. Ao componente é for-necido dados de treinamento e ele propaga a relevância dos documentos rotulados até osdocumentos não rotulados. No bloco 401, o componente invoca o componente de constru-ção de gráfico para construir o gráfico inicial que inclui setas. No bloco 402, o componenteinvoca o componente de geração de ponderações para gráfico para gerar ponderações queindicam a similaridade entre documentos representada pelos nós conectados. No bloco 403,o componente invoca o componente de normalização de ponderações do gráfico para nor-malizar as ponderações do gráfico. No bloco 404, o componente invoca o componente depropagação de relevância com base em gráfico para realizar a propagação de relevância.

Então, o componente retorna.

A figura 8 é um fluxograma que ilustra o processamento do componente de cons-trução de gráfico do sistema de propagação em uma modalidade. O componente cria umamatriz quadrática com cada linha e coluna representando um documento. Então, o compo-nente identifica e adiciona uma conexão entre cada nó e seus vizinhos k mais próximos (porexemplo, k = 10). No bloco 501, o componente seleciona o próximo documento i. No blocode decisão 502, se todos os documentos /'já foram selecionados, então, o componente re-torna, caso contrário, o componente continua no bloco 503. No bloco 503, o componenteseleciona o próximo documento j. No bloco de decisão 504, se todos os documentos; para odocumento selecionado i já foram selecionados, então, o componente continua no bloco506, caso contrário, o componente continua no bloco 505. No bloco 505, o componente cal-cula a distância entre o documento selecionado /' e o documento selecionado j e, então, re-torna ao bloco 503 para selecionar o próximo documento / No bloco 506, o componenteseleciona os 10 documentos j com a menor distância para um documento /' (isto é, os vizi-nhos mais próximos) e, então, retorna ao bloco 501 para selecionar o próximo documento /.

A figura 6 é um fluxograma que ilustra o processamento do componente de geraçãode ponderações para gráfico do sistema de propagação em uma modalidade. O componen-te calcula a similaridade entre documentos conectados com base em uma métrica Manhat-tan. No bloco 601, o componente seleciona o próximo documento /'. No bloco de decisão602, se todos os documentos /' já foram selecionados, então, o componente retorna, casocontrário, o componente continua no bloco 603. No bloco 603, o componente inicializa asimilaridade do documento para si próprio em 0. No bloco 604, o componente seleciona opróximo documento mais próximo j (isto é, o documento conectado) em relação o documen-to selecionado /'. No bloco de decisão 605, se todos os documentos mais próximos j em re-lação ao documento selecionado i já foram selecionados, então, o componente retorna aobloco 601 para selecionar o próximo documento /', caso contrário, o componente continua nobloco 606. No bloco 606, o componente inicializa a similaridade entre o documento selecio-nado i e o documento selecionado j em 1. Nos blocos 607-609, o componente retorna calcu-lando a métrica da distância. No bloco 607, o componente seleciona a próxima dimensão /do vetor de recurso. No bloco de decisão 608, se todas as dimensões já foram seleciona-das, então, o componente retorna ao bloco 604 para selecionar o próximo documento maispróximo j, caso contrário, o componente continua no bloco 609. No bloco 609, o componenteajusta a similaridade entre o documento selecionado ie o documento selecionado)em suassimilaridades atuais multiplicado por uma função da distância entre os recursos seleciona-dos / do documento selecionado /' e do documento selecionado y, de acordo com a Equação2. Então, o componente retorna ao bloco 607 para selecionar a próxima dimensão.

A figura 7 é um fluxograma que ilustra o processamento do componente de norma-lização de ponderações do gráfico do sistema de propagação em uma modalidade. O com-ponente normaliza as ponderações da matriz de similaridade. No bloco 701, o componenteseleciona a próxima linha /' da matriz de similaridade. No bloco de decisão 702, se todas aslinhas já foram selecionadas, então, o componente continua no bloco 706, caso contrário, ocomponente continua no bloco 703. Nos blocos 703-705, o componente calcula o valor damatriz diagonal D para a linha selecionada. No bloco 703, o componente seleciona a próxi-ma coluna j da matriz de similaridade. No bloco de decisão 704, se todas as colunas já fo-ram selecionadas, então, o componente retorna ao bloco 701 para selecionar a nova linha,caso contrário, o componente continua no bloco 705. No bloco 705, o componente adicionaas ponderações da linha / selecionada e da coluna j selecionada no elemento diagonal paraa linha / selecionada. Então, o componente retorna ao bloco 703 para selecionar a próximacoluna j para a linha /' selecionada. No bloco 706, o componente normaliza a matriz de simi-laridade de acordo com a Equação 3.

A figura 8 é um fluxograma que ilustra o processamento do componente de propa-gação de relevância com base no gráfico do sistema de propagação em uma modalidade. Ocomponente calcula iterativamente a expansão da série Taylor da Equação 5 até ela convir-ja em uma solução. No bloco 801, o componente inicializa o índice /'em zero. No bloco 802,o componente inicializa o vetor de solução em 0. Nos blocos 803-805, o componente retornaaté que ele convirja em uma solução. No bloco 803, o componente calcula o valor para apróxima iteração com base em um valor da iteração anterior mais o próximo fator da expan-são da série Taylor. No bloco dè decisão 804, se os valores convergirem em uma solução,então, o componente retorna, caso contrário, o componente continua no bloco 805. No bloco805, o componente incrementa o índice na próxima iteração e retorna ao bloco 803 pararealizar a próxima iteração.

Embora o assunto em questão tenha sido descrito em linguagem específica pararecursos estruturais e/ou atos metodológicos, entende-se que o assunto em questão defini-do nas reivindicações anexas não é necessariamente limitado em relação aos recursos ouatos específicos supradescritos. Em vez disto, os recursos e atos específicos supradescritossão divulgados como formas de exemplo da implementação das reivindicações. O sistemade propagação pode ser usado para aumentar os resultados da busca. Por exemplo, ummotor de busca pode gerar um resultado da busca com base em certos arquivos de docu-mentos. Então, a relevância do documento do resultado da busca pode ser propagada paradocumentos de um arquivo diferente usando o sistema de propagação. Então, os documen-tos de diferentes arquivos com a relevância mais alta podem ser adicionados no resultadoda busca. O sistema de propagação pode ser usado para propagar a relevância de docu-mentos rotulados com suas relevâncias em relação a uma única consulta até documentosnão rotulados (propagação intraconsulta) ou de documentos rotulados com suas relevânciasem relação a múltiplas consultas até documentos não rotulados (propagação interconsulta).O componente de propagação treina o componente de treinamento separadamente paracada consulta com propagação intra-consulta e, simultaneamente, para múltiplas consultascom propagação interconsulta. Dessa maneira, a invenção não é limitada, exceto como pe-las reivindicações anexas.

Claims

1. Sistema para propagar relevância de documentos rotulados até documentos nãorotulados, CARACTERIZADO pelo fato de que compreende:um armazenamento de documento (232) que contém representações de documen-tos, alguns dos documentos sendo rotulados com relevância em relação a uma consulta eoutros dos documentos não sendo rotulados em relação à consulta;um componente gráfico (236) que cria um gráfico dos documentos com os docu-mentos representados como nós sendo conectados por setas que representam similaridadeentre os documentos; eum componente de propagação de relevância (239) que propaga a relevância dosdocumentos rotulados até os documentos não rotulados com base na similaridade entre osdocumentos indicada pela similaridade representada pelas setas no gráfico.

2. Sistema, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que ocomponente de gráfico inclui:um componente de construção de gráfico que constrói um gráfico no qual nós querepresentam documentos similares são conectados por meio de setas;um componente de geração de ponderações que gera ponderações para as setascom base na similaridade dos documentos representada pelos nós conectados; eum componente de normalização de ponderação que normaliza as ponderações dográfico.

3. Sistema, de acordo com a reivindicação 2, CARACTERIZADO pelo fato de que ocomponente de construção de gráfico estabelece setas entre nós usando um algoritmo devizinho mais próximo.

4. Sistema, de acordo com a reivindicação 3, CARACTERIZADO pelo fato de que oalgoritmo de vizinho mais próximo usa uma métrica de distância Euclidiana.

5. Sistema, de acordo com a reivindicação 3, CARACTERIZADO pelo fato de que ocomponente de construção de gráfico conecta um nó em seus 10 vizinhos mais próximos.

6. Sistema, de acordo com a reivindicação 2, CARACTERIZADO pelo fato de que ocomponente de construção de gráfico estabelece setas entre cada par de nós.

7. Sistema, de acordo com a reivindicação 2, CARACTERIZADO pelo fato de que ocomponente de construção de gráfico estabelece setas entre nós para criar uma árvore deabrangência mínima.

8. Sistema, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que arelevância dos documentos rotulados é gerada pela busca de documentos relacionados àconsulta em um arquivo de documentos, e os documentos não rotulados não são incluídosno arquivo de documentos.

9. Sistema, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que ocomponente de propagação de relevância propaga a relevância usando um algoritmo combase em classificação de cópias.

10. Sistema, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de queo componente de propagação de relevância propaga relevância de acordo com a seguinteequação:f° = (1-a)(l-aS)~1 yem que f representa um vetor de relevância propagado, S é uma matriz de simila-ridade, y representa um vetor de relevância inicial e a representa uma taxa de decadência.

11. Sistema, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de queo componente de propagação de relevância propaga a relevância de acordo com a seguinteequação:f ° = (I + aS + O2S2+ ...+(Z1Sn)Yem que f representa um vetor de relevância propagada, S é uma matriz de simila-ridade, y representa um vetor de relevância inicial e a representa uma taxa de decadência, eem que η representa um expoente para qual f° converge em uma solução.

12. Sistema para propagar relevância de páginas rotuladas em relação a uma con-sulta até páginas não rotuladas em relação à consulta, CARACTERIZADO pelo fato de quecompreende:um armazenamento de página (232) que contém representações das páginas, al-gumas das páginas sendo rotuladas com relevância em relação a uma consulta e outras daspáginas não sendo rotuladas com relevância em relação à consulta;um componente gráfico que cria um gráfico das páginas com as páginas represen-tadas como nós conectados por setas que representam similaridade entre as páginas, inclu-indo: um componente de construção de gráfico (236) que constrói um gráfico no qual nósque representam páginas similares são conectados por meio de setas; eum componente de geração de ponderações (237) que gera ponderações para assetas com base na similaridade das páginas representada pelos nós conectados; eum componente de propagação de relevância (239) que propaga a relevância daspáginas rotuladas até as páginas não rotuladas com base na similaridade entre as páginasindicada pela similaridade representada pelas setas do gráfico e com base em um algoritmode classificação de cópias.

13. Sistema, de acordo com a reivindicação 12, CARACTERIZADO pelo fato deque o componente de construção de gráfico estabelece setas entre nós usando um algorit-mo de vizinho mais próximo.

14. Sistema, de acordo com a reivindicação 13, CARACTERIZADO pelo fato deque o algoritmo de vizinho mais próximo usa uma métrica de distância Euclidiana.

15. Sistema, de acordo com a reivindicação 13, CARACTERIZADO pelo fato deque o componente de construção de gráfico conecta um nó aos seus 10 vizinhos mais pró-ximos.

16. Sistema, de acordo com a reivindicação 12, CARACTERIZADO pelo fato deque o componente de geração de ponderações usa uma métrica de distância Manhattanpara representar a similaridade entre as páginas.

17. Sistema, de acordo com a reivindicação 12, CARACTERIZADO pelo fato deque cada página é representada por um vetor de recurso e a similaridade entre as páginas érepresentada pela distância no espaço do vetor de recurso.

18. Mídia legível por computador, CARACTERIZADA pelo fato de que contém ins-truções para controlar um sistema de computador para propagar relevância dos documentosem relação a uma consulta até outros documentos por um método que compreende:criar (236) um gráfico dos documentos representado como nós conectados por se-tas com ponderações que representam similaridade entre documentos; epropagar (239) a relevância dos documentos rotulados até os documentos não rotu-lados com base nas ponderações das setas entre os nós usando um algoritmo com base emclassificação de cópias.

19. Mídia legível por computador, de acordo com a reivindicação 18,CARACTERIZADA pelo fato de que a propagação de relevância dos documentos rotuladosinclui usar uma expansão Taylor para resolver iterativamente a seguinte equação:f = (1-a)(l-aS)'1y

20. Mídia legível por computador, de acordo com a reivindicação 18,CARACTERIZADA pelo fato de que a criação do gráfico inclui conectar setas usando umalgoritmo de vizinho mais próximo e estabelecer a ponderação de uma seta com base nadistância entre os documentos representara pelos nós conectados pela seta.