Create your blog and photo album with postbit
Create your blog and photo album

Create new post

Content:

Upload a picture:
Tags (keywords separated by comma)

Save Cancel
Rodrigo Siqueira rsiqueira:   Followers: 32 ; Following: 31

Explore Rodrigo Siqueira's photo albums:
Chateau de Chambord (4)
Pomar (10)
Florence - Firenze (42)
Pousada Azul Maria - Praia da Baleia (41)
Stonehenge (25)
Família (1)

Matemática no Google


Matemática e algorítmos do Google

O artigo "Mathematics at Google" explica alguns métodos matemáticos e algorítmos usados pelo Google.

IMAGENS SIMILARES - Como o Google encontra imagens similares?

A busca por imagens similares é um exemplo de recuperação de informação baseado em conteúdo (usando cores, formas, texturas, etc.). Explicado no artigo "Content-based Multimedia Information Retrieval: State of the Art and Challenges".
O conceito principal é medir a similaridade entre imagens. Por exemplo, a diferença entre histogramas de cores e a diferença entre vetores característicos das imagens. Artigos:
"(Image search) Web-scale Image annotation" e "Tour the World: building a web-scale landmark recognition engine"

RECONHECIMENTO DE VOZ - Como funciona reconhecimento de voz e busca por voz feita pelo Google?

O reconhecimento automático de fala (Automated Speech Recognition - ASR) é feito em duas etapas:
1) Primeiro o sinal é quebrado em partes menores e processado, aplicando a Transformada de Fourier e extraindo os coeficientes mais significantes.
2) Em seguida, a fala é modelada usando um modelo oculto de Markov (hidden Markov model). Neste modelo, os estados são letras da mensagem e a sequencia de eventos é o sinal sonoro. O "algorítmo de Viterbi" pode ser usado para obter a sequencia de estados de máxima semelhança.
Artigo recomendado com o estudo de caso: "Google Search by Voice: A case study".

RECONHECIMENTO DE CARACTERES (OCR)

O Google utiliza o "Tesseract OCR" para realizar reconhecimento automático das letras em textos, usado pelo Google Books.

PROCESSAMENTO DE IMAGENS

O Google utiliza processamento de imagens no aplicativo "Picasa".
Cada imagem é considerada como um conjunto de 3 matrizes, uma para cada cor primária (R, G, B).
Aplicar um filtro na imagem consiste em realizar uma operação de convolução nestas matrizes.
O reconhecimento automático de rostos é um problema de processamento de imagens e de aprendizagem de máquina (machine learning). Artigos: "Handbook of Face Recognition" e "Large-Scale Manifold Learning".

TRADUÇÃO AUTOMÁTICA DE IDIOMAS
O Google Translate utiliza diversas técnicas para traduzir automaticamente. Uma delas poderia ser transformar o texto em uma representação abstrata e então transformar esta representação na linguagem (idioma) destino. Mas esta técnica requer conhecimento sobre a estrutura da linguagem.
O método usado pelo Google na verdade é baseado em uma quantidade imensa de dados para construir um modelo estatístico da tradução. Artigo: "Large Language Models in Machine Translation".

AdWords
O AdWords utiliza algorítmo de lançes de leilão. Cada anunciante dá seu lançe para mostrar seu inventário de anúncios. Artigo: "Hal Varian. Online Ad Auctions"
A teoria dos leilões estuda diferentes estratégias de lançes e a eficácia de cada. É um ramo aplicado da Teoria dos Jogos.
Em particular AdWords utiliza o princípio generalizado do segundo prêmio. Artigo: "Generalized second-price auction" e "Adwords, An Algorithmic Perspective"

MAPAS
O Google Maps utiliza vários algorítmos da Teoria dos Grafos. Por exemplo, encontrar o caminho mais curtos entre dois pontos no gráfo (Dijkstra), para dar as coordenadas de direção.
São milhões de pontos (nós) no gráfo e o algorítmo precisa encontrar a menor distância em milisegundos. Uma técnica para melhor a performance é a de hierarquias de grafos.

SISTEMA DE BUSCA
Algorítmos de sistema de busca (como o PageRank) utilizam muita matemática. E também a criação de índices (tabelas invertidas) contendo a ocorrência de cada palavra em cada documento, apontando para qual documento contém cada palavra.

EMAIL E DETECÇÃO DE SPAM
A detecção de spam é um exemplo clássico de aprendizado por máquina.
O aprendizado por máquina consiste em duas fases:
1) Fase da construção do sistema de classificação. Envolve a extração das características das instâncias de dados. Pode usar exemplos de dados previamente classificados (supervised learning). Cada característica de uma instância pode ser considerado como um elemento de um vetor n-dimensional. Por exemplo, o tamanho da mensagem de email é uma característica. O número de letras escritas com letras maiúsculas é outra característica. Se o remetente está no livro de endereços é outra. Etc.
2) Fase da classificação, usando o modelo criado acima para classificar novas instâncias.

PREVISÃO DE TENDÊNCIAS
Sistemas como o Google Trends utiliza processamento de séries temporais, que é um dos usos mais comuns da matemática aplicada. Entre as técnicas usadas para isso estão regressão, análise de Fourier, modelos ocultos de Markov e auto-correlação.
Isso é usado para prever o número de buscas em um determinado dia, quantidade de usuários, receita, etc.
Artigo: "Large-Scale Parallel Statistical Forecasting Computations in R"

Outros usos de matemática no Google são nos sistemas:
Google Earth: Utiliza geometria, topografia, fotogrametria, fusão de imagens em 2D e 3D, etc.
Sistemas Distribuídos: Utiliza técnicas estatísticas usadas para modelar a disponibilidade de recursos computacionais. É similar à técnicas de controle de qualidade em outras indústrias. Por exemplo modelos ocultos de Markov, Teoria das Filas, modelo de rede como grafo com nós que podem falhar com alguma probabilidade, estudo de topologia de grafos, tolerância à falhas, latência (diâmetro do grafo), largura de banda (conectividade), menor custo (menor número de links). Outros tópicos aplicados em Teoria dos Grafos são os conceitos de "Grafos de Ramanujan".

Fonte: Artigo "Mathematics at Google" (Matemática no Google), de Javier Tordable (engenheiro de software no Google).

Site com publicações científicas do Google:
http://research.google.com/pubs/papers.html

Post by Rodrigo Siqueira (2012-09-26 14:46)

Post your comment:

Name: Email: Site:




| Explore users | New posts | Create your blog | Create your photo album |
| About Postbit | Our blog | Terms of use | Contact Postbit |


Copyright © 2017 - postbit.com