Bagaimana Apple menemukan tanggal, waktu, dan alamat dalam email?

128

Di klien email iOS, ketika email berisi tanggal, waktu atau lokasi, teks menjadi hyperlink dan dimungkinkan untuk membuat janji temu atau melihat peta hanya dengan mengetuk tautan. Ini tidak hanya berfungsi untuk email dalam bahasa Inggris, tetapi juga dalam bahasa lain. Saya suka fitur ini dan ingin memahami bagaimana mereka melakukannya.

Cara naif untuk melakukan ini adalah memiliki banyak ekspresi reguler dan menjalankan semuanya. Namun saya ini tidak akan skala dengan sangat baik dan akan bekerja hanya untuk bahasa tertentu atau format tanggal, dll. Saya pikir Apple harus menggunakan beberapa konsep pembelajaran mesin untuk mengekstraksi entitas (20:00, 20:00, 20:00, 0800, 20:00, 20j, 20j00, 2000 dll.)

Adakah ide bagaimana Apple dapat mengekstraksi entitas dengan sangat cepat di klien emailnya? Algoritma pembelajaran mesin apa yang akan Anda terapkan untuk menyelesaikan tugas tersebut?

machine-learning nlp information-extraction named-entity-recognition Martin
sumber
5
Saya juga memikirkan hal ini, terutama trik regex. Saya tahu mereka mematenkannya, jadi mungkin Anda dapat mencoba mencarinya. Namun, saya akan sangat tertarik juga. +1
Thomas Jungblut
15
Sebenarnya trik regexp mungkin akan menangkap 99% kasus dengan tingkat kesalahan yang sangat rendah. Dan sangat cepat, ketika Anda mengoptimalkan ekspresi reguler dengan baik. Jadi saya tidak akan terkejut jika itu memang hanya seperangkat ekspresi reguler.
Memiliki QUIT - Anony-Mousse

Jawaban:

153

Mereka kemungkinan menggunakan Ekstraksi Informasi teknik untuk ini.

Berikut ini adalah demo alat SUTime milik Stanford:

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

Anda akan mengekstrak atribut tentang n-gram (kata-kata berurutan) dalam dokumen:

  • numberOfLetters
  • numberOfSymbols
  • panjangnya
  • kata kunci sebelumnya
  • kata berikutnya
  • nextWordNumberOfSymbols
    ...

Dan kemudian gunakan algoritma klasifikasi, dan berikan contoh positif dan negatif:

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

Anda mungkin lolos dengan 50 contoh masing-masing, tetapi lebih banyak lebih meriah. Kemudian, algoritma belajar berdasarkan contoh-contoh itu, dan dapat berlaku untuk contoh di masa depan yang belum pernah dilihat sebelumnya.

Mungkin mempelajari aturan seperti

  • jika kata sebelumnya hanya karakter dan mungkin titik ...
  • dan kata saat ini dalam "februari", "mar.", "the" ...
  • dan kata berikutnya adalah "twelfth", any_number ...
  • lalu tanggal

Berikut adalah video yang layak oleh seorang insinyur Google tentang masalah ini

Neil McGuigan
sumber
4
Menarik! Saya tidak pernah berpikir seperti itu. Terima kasih, el chief.
Martin
2
el chief, menurut Anda, model seperti apa yang terbaik untuk itu? Bayesian?
Martin
5
Saya cukup yakin pendekatan semacam itu tidak akan melakukan lebih baik daripada, katakanlah, f-ukuran kira-kira. 0,9. (Catatan, ini hanya perasaan, saya mungkin salah). Di sisi lain saya akan kecuali pendekatan naif pengkodean semua format umum untuk melakukan jauh lebih baik (mungkin 0,99+ mengingat bahwa format yang paling sering tidak akan pernah terlewatkan) dan lebih cepat untuk menerapkan + saat runtime.
b.buchhold
@ b.buchhold, mungkin, tapi kemudian Anda harus melakukan jumlah pekerjaan yang sama untuk bahasa berikutnya, dan bahasa berikutnya, sedangkan solusi saya bersifat umum.
Neil McGuigan
@Neil McGuigan, benar. Tetapi Anda harus memberikan banyak data pelatihan untuk semua format / bahasa yang lebih banyak pekerjaan.
b.buchhold
110

Itu adalah teknologi yang sebenarnya dikembangkan Apple sejak dulu Apple Data Detectors . Anda dapat membaca lebih lanjut tentang ini di sini:

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

Pada dasarnya itu mem-parsing teks dan mendeteksi pola yang mewakili potongan data tertentu, kemudian menerapkan tindakan kontekstual OS untuk itu. Itu rapi.

jeffehobbs
sumber
24
Ini jawaban yang benar. Jawaban lain mungkin memberi tahu Anda bagaimana Anda bisa melakukannya, tetapi jawaban ini memberi tahu Anda bagaimana Apple melakukannya .
LaC
2
dapatkah kita memiliki sedikit lebih detail dalam penulisan tho? entri tautan tunggal tidak menambahkan sebanyak
shigeta
14
Ah, jadi INI adalah asal semua hit di situs web saya :) FWIW, saya adalah pimpinan proyek pada Detektor Data Apple pada zaman ATG; apa yang dapat saya tambahkan di sini adalah bahwa ini adalah teknologi OS 8 dan 9 saja - tidak pernah membuat lompatan ke OS X. Jelas ada beberapa hal serupa terjadi di OS X dan IOS, dan, sementara saya tidak di Apple lagi dan jadi tidak bisa mengatakan, saya tidak akan terkejut jika arsitekturnya sedikit berbeda. Namun demikian, saya berharap semacam tata bahasa / sistem pengurai masih di jantungnya. Komputer cepat akhir-akhir ini, dan tata bahasa sederhana cukup murah.
Jim Miller
5

Salah satu bagian dari teka-teki itu adalah NSDataDetectorkelas. Ini digunakan untuk mengenali beberapa tipe standar seperti nomor telepon.

hburde
sumber
2
Tampaknya NSDataDetectorkelas adalah hasil upaya Apple untuk menerapkan ini. Pertanyaannya adalah bagaimana cara kerja kelas secara internal?
Ole Begemann
3
itu dalam NSRegularExpression.h, jadi sepertinya sangat mungkin, seperti yang ditunjukkan, hanya satu set ekspresi reguler.
riffraff
2

Saya pernah menulis parser untuk melakukan ini, menggunakan pyparsing. Ini benar-benar sangat sederhana, Anda hanya perlu melakukan semua cara yang berbeda dengan benar, tetapi jumlahnya tidak banyak. Hanya butuh beberapa jam dan cukup cepat.

Stavros Korokithakis
sumber
Ekstrak dari Miramontes "Tidak sulit untuk membuat hardcode sebuah pengenal untuk struktur atom seperti URL, tetapi pekerjaan yang substansial diperlukan untuk membuat arsitektur yang membuka proses pembuatan struktur kompleks."
Remy