Como a Apple encontra datas, horários e endereços nos e-mails?

128

No cliente de email do iOS, quando um email contém uma data, hora ou local, o texto se torna um hiperlink e é possível criar um compromisso ou visualizar um mapa simplesmente tocando no link. Não funciona apenas para e-mails em inglês, mas também em outros idiomas. Eu amo esse recurso e gostaria de entender como eles fazem isso.

A maneira ingênua de fazer isso seria ter muitas expressões regulares e executá-las todas. No entanto, isso não vai escalar muito bem e funcionará apenas em um idioma ou formato de data específico etc. Acho que a Apple deve estar usando algum conceito de aprendizado de máquina para extrair entidades (20:00, 20:00, 20:00, 0800, 20:00, 20h, 20h00, 2000 etc.).

Alguma idéia de como a Apple é capaz de extrair entidades tão rapidamente em seu cliente de email? Qual algoritmo de aprendizado de máquina você aplicaria para realizar essa tarefa?

machine-learning nlp information-extraction named-entity-recognition Martin
fonte
5
Eu também pensei sobre isso, especialmente o truque regex. Eu sei que eles têm uma patente, então talvez você possa tentar pesquisá-lo. No entanto, eu estaria muito interessado nisso também. 1
Thomas Jungblut
15
Na verdade, o truque regexp provavelmente captura 99% dos casos com uma taxa de erro muito baixa. E é super rápido, quando você otimiza bem as expressões regulares. Então, eu não ficaria surpreso se fosse apenas um conjunto de expressões regulares.
QuIT - Anony-Mousse 16/02

Respostas:

153

Eles provavelmente usam técnicas de extração de informações para isso.

Aqui está uma demonstração da ferramenta SUTime de Stanford:

http://nlp.stanford.edu:8080/sutime/process

Você extrairia atributos sobre n-gramas (palavras consecutivas) em um documento:

  • numberOfLetters
  • numberOfSymbols
  • comprimento
  • previousWord
  • nextWord
  • nextWordNumberOfSymbols
    ...

E, em seguida, use um algoritmo de classificação e alimente exemplos positivos e negativos:

Observation  nLetters  nSymbols  length  prevWord  nextWord isPartOfDate  
"Feb."       3         1         4       "Wed"     "29th"   TRUE  
"DEC"        3         0         3       "company" "went"   FALSE  
...

Você pode se dar bem com 50 exemplos de cada um, mas quanto mais, melhor. Em seguida, o algoritmo aprende com base nesses exemplos e pode aplicar-se a exemplos futuros que não foram vistos antes.

Pode aprender regras como

  • se a palavra anterior tiver apenas caracteres e talvez pontos ...
  • e a palavra atual está em "fevereiro", "mar.", "o" ...
  • e a próxima palavra está em "décimo segundo", any_number ...
  • então é data

Aqui está um vídeo decente de um engenheiro do Google sobre o assunto

Neil McGuigan
fonte
4
Interessante! Nunca pensei nisso dessa maneira. Obrigado, chefe.
Martin
2
el chefe, na sua opinião, que tipo de modelo seria melhor para isso? Bayesiano?
Martin Martin
5
Tenho certeza de que essa abordagem não funcionará melhor do que, digamos, f-measure de aprox. 0,9. (Observe, isso é apenas um sentimento, posso estar errado). Por outro lado, exceto pela abordagem ingênua de codificar todos os formatos comuns para ter um desempenho melhor (possivelmente 0,99+, pois os formatos mais frequentes nunca serão perdidos) e ser mais rápido para implementar o + em tempo de execução.
b.buchhold
@ b.buchhold, talvez, mas você teria que fazer a mesma quantidade de trabalho para o próximo idioma e para o próximo idioma, enquanto minha solução é geral.
Neil McGuigan
@ Neil McGuigan, é verdade. Mas você teria que fornecer muitos dados de treinamento para todos esses formatos / idiomas, o que é muito mais trabalhoso.
b.buchhold
110

Essa é uma tecnologia que a Apple realmente desenvolveu há muito tempo, chamada Apple Data Detectors . Você pode ler mais sobre isso aqui:

http://www.miramontes.com/writing/add-cacm/

Essencialmente, ele analisa o texto e detecta padrões que representam partes específicas de dados e depois aplica ações contextuais do SO. Está arrumado.

jeffehobbs
fonte
24
Essa é a resposta correta. Outras respostas podem lhe dizer como você pode fazer isso, mas esta mostra como a Apple faz isso.
LaC
2
poderíamos ter um pouco mais de detalhes na redação? entradas de link único não adicionam tanto #
shigeta
14
Ah, então é daí que vieram todos os hits do meu site :) FWIW, eu era o líder do projeto nos Apple Data Detectors na época da ATG; o que posso acrescentar aqui é que essa era apenas uma tecnologia OS 8 e 9 - ela nunca pulou para o OS X. Obviamente, há coisas semelhantes acontecendo no OS X e no IOS e, embora eu não esteja mais na Apple e, portanto, não posso dizer, não ficaria surpreso se a arquitetura fosse um pouco diferente. No entanto, espero que algum tipo de sistema de gramática / analisador ainda esteja no centro dele. Atualmente, os computadores são rápidos e gramáticas simples são bem baratas.
26612 Jim Miller
5

Uma parte do quebra-cabeça poderia ser a NSDataDetectorclasse. É usado para reconhecer alguns tipos padrão, como números de telefone.

hburde
fonte
2
Parece que a NSDataDetectoraula é o resultado do esforço que a Apple fez para implementar isso. A questão é como a classe trabalha internamente?
25812 Ole Begemann
3
está em NSRegularExpression.h, então parece bem possível que seja, como apontado, apenas um conjunto de expressões regulares.
Riffraff
2

Certa vez, escrevi um analisador para fazer isso, usando pyparsing. É realmente muito simples, você só precisa acertar todas as maneiras diferentes, mas não há muitas. Demorou apenas algumas horas e foi bem rápido.

Stavros Korokithakis
fonte
Extrato de Miramontes "Não é difícil codificar um reconhecedor para uma estrutura atômica como uma URL, mas é necessário um trabalho substancial para criar uma arquitetura que abra o processo de criação de estruturas complexas".
Remy