W jaki sposób Apple znajduje daty, godziny i adresy w wiadomościach e-mail?

131

W kliencie poczty e-mail na iOS, gdy wiadomość e-mail zawiera datę, godzinę lub lokalizację, tekst staje się hiperłączem i można utworzyć spotkanie lub spojrzeć na mapę, po prostu dotykając łącza. Działa nie tylko w przypadku wiadomości e-mail w języku angielskim, ale także w innych językach. Uwielbiam tę funkcję i chciałbym zrozumieć, jak to robią.

Naiwnym sposobem byłoby posiadanie wielu wyrażeń regularnych i uruchamianie ich wszystkich. Jednak nie będzie to zbyt dobrze skalowane i będzie działać tylko dla określonego języka lub formatu daty itp. Myślę, że Apple musi używać jakiejś koncepcji uczenia maszynowego do wyodrębniania jednostek (20:00, 20:00, 8:00, 0800, 20:00, 20h, 20:00, 2000 itd.).

Masz jakiś pomysł, w jaki sposób Apple jest w stanie tak szybko wyodrębnić jednostki w swoim kliencie poczty e-mail? Jaki algorytm uczenia maszynowego zastosowałbyś, aby wykonać takie zadanie?

machine-learning nlp information-extraction named-entity-recognition Jaskółka oknówka
źródło
5
Też o tym myślałem, zwłaszcza trik regex. Wiem, że mają na to patent, więc może spróbuj go poszukać. Byłbym jednak tym bardzo zainteresowany. +1
Thomas Jungblut,
15
W rzeczywistości sztuczka regexp prawdopodobnie wyłapie 99% przypadków z bardzo niskim poziomem błędów. I jest super szybki, jeśli dobrze zoptymalizujesz wyrażenia regularne. Nie zdziwiłbym się więc, gdyby rzeczywiście był to zbiór wyrażeń regularnych.
ZAKOŃCZYŁO - Anony-Mousse

Odpowiedzi:

154

Prawdopodobnie używają do tego technik ekstrakcji informacji .

Oto demonstracja narzędzia SUTime Stanforda:

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

Wyodrębniłbyś atrybuty dotyczące n-gramów (kolejnych słów) w dokumencie:

  • numberOfLetters
  • numberOfSymbols
  • długość
  • previousWord
  • nextWord
  • nextWordNumberOfSymbols
    ...

Następnie użyj algorytmu klasyfikacji i podaj pozytywne i negatywne przykłady:

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

Możesz uciec z 50 przykładami każdego z nich, ale im więcej, tym weselej. Następnie algorytm uczy się na podstawie tych przykładów i może zastosować do przyszłych przykładów, których wcześniej nie widział.

Może nauczyć się takich zasad jak

  • jeśli poprzednie słowo składa się tylko ze znaków i może kropek ...
  • a aktualne słowo to „luty”, „marzec”, „…”
  • a następne słowo jest w „dwunastej”, dowolna_numer ...
  • wtedy jest data

Oto przyzwoity film napisany przez inżyniera Google na ten temat

Neil McGuigan
źródło
2
el szefie, twoim zdaniem, jaki model byłby do tego najlepszy? Bayesian?
Martin,
6
Jestem prawie pewien, że takie podejście nie sprawdzi się lepiej niż, powiedzmy, f-miara ok. 0.9. (Uwaga, to tylko uczucie, mogę się mylić). Z drugiej strony pomijałbym naiwne podejście do kodowania wszystkich popularnych formatów, aby działały znacznie lepiej (prawdopodobnie 0,99+, biorąc pod uwagę, że najczęstsze formaty nigdy nie zostaną pominięte) i szybsze wdrożenie + w czasie wykonywania.
b.buchhold
@ b.buchhold, być może, ale wtedy musiałbyś wykonać taką samą ilość pracy dla następnego języka i dla następnego języka, podczas gdy moje rozwiązanie jest ogólne.
Neil McGuigan,
@Neil McGuigan, prawda. Ale musiałbyś dostarczyć dużo danych szkoleniowych dla wszystkich tych formatów / języków, co wymaga znacznie więcej pracy.
b.buchhold
@NeilMcGuigan bardzo dziękuję za tę odpowiedź. Zrobiłem to, o czym wspomniałeś powyżej, ale nie mogłem dowiedzieć się, jak wytrenować te dane i użyć jakiego algorytmu. Nie mogę używać drzewa decyzyjnego, ponieważ atrybuty nie są tego samego typu
przeszywa
113

To technologia, którą Apple opracował bardzo dawno temu Apple Data Detectors. Więcej na ten temat przeczytasz tutaj:

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

Zasadniczo analizuje tekst i wykrywa wzorce, które reprezentują określone fragmenty danych, a następnie stosuje do nich działania kontekstowe systemu operacyjnego. Jest fajnie.

jeffehobbs
źródło
25
To jest poprawna odpowiedź. Inne odpowiedzi mogą podpowiedzieć, jak możesz to zrobić, ale ta mówi, jak robi to Apple .
LaC,
2
czy moglibyśmy mieć trochę więcej szczegółów w tym artykule? pojedyncze linki nie dodają tyle
shigeta,
15
Ach, więc TO skąd wzięły się wszystkie hity na mojej stronie :) FWIW, byłem kierownikiem projektu w Apple Data Detectors w czasach ATG; mogę tutaj dodać, że była to tylko technologia OS 8 i 9 - nigdy nie przeskoczyła na OS X. Oczywiście podobne rzeczy dzieją się w OS X i IOS, i chociaż nie jestem już w Apple nie mogę więc powiedzieć, że nie zdziwiłbym się, gdyby architektura była trochę inna. Niemniej jednak, spodziewam się, że jego sercem jest jakiś system gramatyki / parsera. Komputery są obecnie szybkie, a proste gramatyki są dość tanie.
Jim Miller,
6

Jedną z części układanki może być NSDataDetectorklasa. Służy do rozpoznawania niektórych standardowych typów, takich jak numery telefonów.

hburde
źródło
2
Wygląda na NSDataDetectorto, że ta klasa jest wynikiem wysiłku, jaki Apple włożył w jej wdrożenie. Pytanie brzmi, jak klasa działa wewnętrznie?
Ole Begemann
4
jest w NSRegularExpression.h, więc wydaje się całkiem możliwe, że jest to tylko zestaw wyrażeń regularnych.
riffraff
3

Kiedyś napisałem parser, aby to zrobić, używając pyparsing. To naprawdę bardzo proste, wystarczy, że dobrze zrozumiesz wszystkie różne sposoby, ale nie ma ich zbyt wiele. Zajęło to tylko kilka godzin i było dość szybkie.

Stavros Korokithakis
źródło
Fragment z Miramontes „Nie jest trudno zakodować na stałe program rozpoznający strukturę atomową, taką jak adres URL, ale stworzenie architektury, która otwiera proces tworzenia złożonych struktur, wymaga znacznej pracy”.
Remy