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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.