К машинно-интерпретируемому пониманию места

Уличные адреса являются одними из наиболее причудливых артефактов человеческого языка, но они имеют решающее значение для растущего числа приложений, связанных с картами и местоположением.

В прошлом году я сотрудничал с Mapzen с целью создания более умных и международных геокодеров с использованием огромного количества местных знаний в открытых наборах географических данных.

В результате получился libpostal: многоязычная библиотека для разбора / нормализации почтовых адресов, написанная на C, которая может обрабатывать адреса по всему миру.

Libpostal использует машинное обучение и получает информацию из десятков миллионов реальных адресов из OpenStreetMap. Весь конвейер для обучения моделей имеет открытый исходный код.

Поскольку OSM - это динамический набор данных с тысячами участников, а модели периодически переобучаются, их улучшение может быть таким же простым, как внесение адресов в OSM.

Система адресации каждой страны имеет свой набор условностей и особенностей, и libpostal разработан для решения практически всех из них.

В настоящее время он поддерживает нормализацию на 60 языках и может анализировать адреса в более чем 100 странах. Геокодирование с использованием libpostal в качестве этапа предварительной обработки становится значительно проще и согласованнее на международном уровне.

Основная библиотека написана на чистом C, а это означает, что, помимо небольшого углеродного следа, libpostal можно использовать практически из любого стека или языка программирования. В настоящее время существуют привязки, написанные для Python, Go, Ruby, Java и NodeJS с другими популярными языками, которые скоро появятся.

Но давайте на минутку перемотаем назад.

Почему нам важны адреса

Адреса - это уникальные идентификаторы, которые люди используют для описания мест, и они лежат в основе практически всех аспектов современной жизни, подключенной к Интернету: поиск по карте, маршруты / направления, доставка, транспортировка по запросу, услуги доставки, путешествия и проживание, продажа билетов на мероприятия, рейтинги / обзоры мест проведения мероприятий и т. д. Почти в каждой из этих категорий есть компания стоимостью 1 млрд долларов.

Основная проблема получения информации при работе с адресами известна как геокодирование. Мы хотим преобразовать адреса на естественном языке, которые люди используют для описания мест, в координаты широты и долготы, которые использует все наше замечательное программное обеспечение для картографии и маршрутизации.

Геокодирование - это не обычный поиск по документам. Адреса обычно состоят из очень коротких строк, очень неоднозначны и переполнены аббревиатурами и местным контекстом.

Обычно есть только один правильный ответ на запрос с точки зрения пользователя (за исключением более широкого поиска, такого как «рестораны в Форт-Грин, Бруклин»). В некоторых случаях у нас может вообще не быть роскоши пользовательского ввода, например пакетное геокодирование группы адресов, полученных из файла CSV, Интернета или стороннего API.

Несмотря на эти особенности, мы, как правило, используем те же системы полнотекстового поиска для адресов, что и для запросов к традиционным текстовым документам. Говорят, что "из коробки" поисковые системы ужасно плохо индексируют адреса. Легко увидеть, как наивная реализация могла вывести адреса на St Marks Ave, когда запрос был St Marks Pl (оба слова Ave и Pl имеют низкую обратную частоту документов и не влияют на рейтинг. много). Автозаполнение может дать адреса в 300-м квартале Мэйн-стрит по запросу 30 Мэйн-стрит. Сокращения, такие как Saint и St, которые не являются простыми перекрытиями префиксов, могут не совпадать в большинстве средств проверки орфографии, поскольку их расстояние редактирования больше 2.

Обычно мы используем всевозможные эвристики, чтобы помочь с сопоставлением адресов: списки синонимов, специальные токенизаторы, анализаторы, регулярные выражения, простые синтаксические анализаторы и т. Д. Большинство этих методов требуют изменения конфигурации поисковой системы и делают ориентированный на США / английский язык чрезмерно упрощенным. предположения.

Даже использование полнотекстовой поисковой системы в целом не поможет в случае серверного пакетного геокодирования, если мы не будем полностью уверены в том, что первый результат правильный.

Геокодирование в 2016 году

Libpostal исходил из идеи, что геокодирование больше похоже на проблему привязки записей, чем на текстовый поиск.

Вопрос, на который мы хотим ответить, звучит так: «Два адреса относятся к одному и тому же месту?» Сделав это, мы можем одновременно принимать автоматические решения в пакетной настройке и возвращать более релевантные результаты в геокодерах, доступных пользователю.

Это разбивается на две подзадачи:

  1. Нормализация: самый простой способ справиться со всеми сокращенными вариациями и двусмысленностями в адресах - создать канонические строки, подходящие для машинного сравнения, т.е. сделать «30 W 26th St» равным «Thirty West Twenty-Sixth Street». , и сделать это на всех языках.
  2. Анализ: некоторые компоненты адреса более важны, чем другие, например номера домов, названия мест, названия улиц и почтовые индексы. Помимо этого, адреса сильно структурированы, и существует несколько избыточных способов их указания / квалификации. «Лондон, Англия» и «Лондон, Соединенное Королевство» указывают одно и то же местоположение, если анализируются как город / администратор1 и город / страна соответственно. Если бы мы уже знали Лондон, не было бы смысла возвращать адреса в Манчестере просто потому, что он также находится в Великобритании.

Как только у нас есть канонические адресные строки, сегментированные на компоненты, геокодирование становится гораздо более простой проблемой сопоставления строк, с которой хорошо справляются полнотекстовые поисковые системы и даже реляционные / нереляционные базы данных.

При небольшом изяществе можно было бы геокодировать ничего, кроме libpostal и хеш-таблицы.

Чтобы увидеть, как это возможно, в следующих двух разделах подробно описывается, как libpostal решает (в значительной степени каламбур) проблемы нормализации и синтаксического анализа соответственно.

Нормализация многоязычного адреса

Нормализация - это процесс преобразования строк адресов произвольной формы, встречающихся в дикой природе, в чистые нормализованные формы, подходящие для машинного сравнения. Это в первую очередь детерминированный / основанный на правилах.

Чтобы нормализация работала на стольких разных языках, необходимо выполнить несколько шагов. Назову самые примечательные.

Многоязычная токенизация

Токенизация - это процесс сегментации текста на слова и символы. Это первый шаг в большинстве приложений НЛП, и здесь много нюансов. Токенизатор в libpostal на самом деле является лексером, реализующим спецификацию TR-29 Консорциума Unicode для сегментации слов Unicode. Этот метод обрабатывает каждый сценарий / алфавит, включая идеограммы (используемые в языках, не разделенных пробелами, например, китайском, японском, корейском), которые читаются по одному символу за раз.

Создание токенизатора вдохновлено подходом Стэнфордского CoreNLP, т.е. записать кучу регулярных выражений и скомпилировать их в быстрый DFA. Мы используем re2c, легкий сканер-генератор, который часто производит C с такой же скоростью, как рукописный эквивалент. Действительно, токенизация происходит довольно быстро, вырабатывая ›2 миллиона токенов в секунду.

Расширение аббревиатуры

Почти на всех языках Земли в адресах используются сокращения. Исторически это было связано с ограничениями по ширине таких вещей, как уличные знаки или почтовые конверты. Цифровые адреса сталкиваются с аналогичными ограничениями, а именно: они с большей вероятностью, чем другие типы текста, будут просматриваться на мобильном устройстве.

Сокращения создают двусмысленность, поскольку существует несколько способов написания одного и того же адреса с разной степенью многословности: «W St Johns St», «W Saint Johns St», «W St Johns Street» и «West Saint Johns Street» - все это эквивалент. Подобные шаблоны есть в большинстве языков.

Для расширения аббревиатур до их канонических форм libpostal содержит ряд языковых словарей, которые представляют собой простые текстовые файлы, отображающие Rd на Road на 60 языках. Каждое слово / аббревиатура может иметь одну или несколько канонических форм (St может расширяться до Street или Saint на английском языке), а также один или несколько типов словарей: направления, суффиксы улиц, почетные знаки, типы мест и т. Д.

Типы словарей позволяют контролировать, какие расширения используются, например, если входной адрес уже разделен на отдельные поля, или если с тем же эффектом используется анализатор адресов libpostal. С типами словарей можно применять только соответствующие расширения к каждому компоненту. Например, в английском адресе "St." всегда означает «Святой», когда используется в названии города или страны, например «Св. Луи »или« Св. Lucia »и будет двусмысленным только при использовании в названии улицы или места проведения / здания.

Словари компилируются в структуру данных trie, в которой используется алгоритм быстрого поиска для сканирования строки и извлечения совпадающих фраз, даже если они охватывают несколько слов (например, State Route). Этот тип поиска также позволяет нам обрабатывать фразы из нескольких слов как отдельные токены во время синтаксического анализа адреса.

Идеографические языки, такие как японский и корейский, обрабатываются правильно, даже если извлеченные фразы не окружены пробелами. То же самое и в германских языках, где суффиксы улиц часто добавляются в конце названия улицы, но при желании могут быть отделены друг от друга (Rosenstraße и Rosen Straße эквивалентны). Все сокращения, перечисленные в OSM Name Finder wiki, реализованы на момент написания этой статьи, а также многие другие.

На данный момент libpostal не пытается устранить двусмысленность адресов и часто производит несколько потенциальных расширений. Некоторые из них могут быть бессмысленными («Main St» расширяется до «Main Street» и «Main Saint»), но правильная форма будет среди них. Выходные данные expand_address libpostal можно рассматривать как набор, а сопоставление адресов можно рассматривать как выполнение пересечения наборов или как JOIN на языке SQL. В настройках поиска следует проиндексировать все полученные строки и использовать один и тот же код для нормализации пользовательских запросов перед их отправкой на поисковый сервер / базу данных.

В будущих итерациях expand_address, вероятно, будет использоваться OpenStreetMap (где сокращение не рекомендуется) для построения классификаторов для неоднозначных расширений и будет включена опция ранжирования выходных данных по вероятности. Это должно помочь людям, которым нужно «единственное лучшее» расширение, например при отображении результатов на карте.

Классификация языка адресов

Аббревиатуры зависят от языка. Рассмотрите возможность расширения токена «St.». по адресу неизвестного языка. Канонической формой будет «Sankt» по-немецки, «Saint» по-французски, «Santo» по-португальски и так далее.

На самом деле мы не хотим перечислять все эти перестановки. В большинстве геокодеров, ориентированных на пользователя, мы, вероятно, заранее знаем язык (например, по заголовкам HTTP или текущему местоположению пользователя). Однако при пакетном геокодировании мы не знаем языка ни одного из наших входных адресов, поэтому нам понадобится классификатор для автоматического прогнозирования языков, используя только входной текст.

Обнаружение языка - хорошо изученная проблема, и существует несколько существующих реализаций (таких как Компактный детектор языка Chromium), которые обеспечивают очень хорошие результаты для более длинных текстовых документов, таких как статьи Википедии или веб-страницы. К сожалению, из-за некоторых из вышеупомянутых различий между адресами и другими формами текста, пакеты, такие как CLD, которые обучаются на веб-страницах, обычно ожидают больше / длиннее слов, чем у нас в сокращенном адресе, и часто ошибаются на языке или не могут производить результат на всех.

Поэтому нам нужно будет создать собственный классификатор языков и обучить его специально для адресных данных. Это проблема контролируемого обучения, что означает, что нам понадобится набор входных данных, связанных с адресами, с пометкой языка, например:

lang  address
  de  Graf-Folke-Bernadotte-Straße
  sv  Tollare Träskväg
  nl  Johannes Vermeerstraat Akersloot
  it  Strada Provinciale Ca' La Cisterna
  da  Østervang  Vissenbjerg
  nb  Lyngtangen Egersund
  en  Wood Point Road
  ru  улица Солунина
  ar  جادة صائب سلام
  fr  Rue De Longpré
  he  השלום
  ms  Jalan Sri Perkasa
  cs  Jeřabinová  Rokycany
  ja  山口秋穂線
  ca  Avinguda Catalunya
  es  calle Camilo Flammarión
  eu  Mungialde etorbidea
  pt  Rua Pedro Muler Faria

Звучит здорово, но где мы собираемся найти такой набор данных? В libpostal ответ на этот вопрос почти всегда: используйте OpenStreetMap.

У OSM отличная система, когда дело касается языков. По умолчанию название места является официальным названием на местном языке, а не английским / латинизированным названием. Например, имя Пекин по умолчанию - 北京市, а не Пекин или Пекин.

Некоторые адреса в OSM явно помечены языком, особенно в странах с несколькими официальными языками уличных указателей, таких как Гонконг, Бельгия, Алжир, Израиль и т. Д. В случаях, когда используется одно имя, мы строим многоугольный индекс R-дерево который может ответить на вопрос: какой официальный и / или региональный язык (и) я должен ожидать для данного лата / долга? В Германии мы ожидаем, что адреса будут на немецком языке. В некоторых регионах Испании каталонский, баскский или галисийский будет возвращен в качестве основного языка, который мы ожидаем увидеть на уличных знаках, тогда как (кастильский) испанский используется в качестве вторичной альтернативы. В случаях, когда существует вероятность появления языков, языковые словари в libpostal используются для устранения неоднозначности. Наконец, уличные указатели всегда пишутся на языках, на которых говорит большинство людей, что является следствием лингвистического империализма, и языковой индекс также учитывает это.

Все сказано и сделано, в результате этого процесса получается около 80 миллионов адресных строк с языковыми метками. Оттуда мы извлекаем особенности (информативные атрибуты ввода, которые помогают предсказать результат), аналогичные тем, которые используются в Chromium и литературе по определению языка: последовательности из 4 букв или 1 идеограммы, целые токены для слов короче 4 символов и ярлык для отображения сценариев юникода на один язык, например греческий или иврит. Специально для нашего случая использования мы также включаем целые фразы, соответствующие определенным языковым словарям из libpostal.

Затем мы обучаем модель полиномиальной логистической регрессии (также известной как регрессия softmax), используя стохастический градиентный спуск и несколько трюков с разреженными данными, чтобы время обучения оставалось достаточно быстрым. Логистическая регрессия широко используется в НЛП, потому что, в отличие от наивного Байеса, она не предполагает, что входные функции независимы, что нереально на языке.

Еще одним приятным свойством логистической регрессии является то, что ее результат представляет собой хорошо откалиброванное распределение вероятностей по меткам, а не просто нормализованные оценки, которые выглядят как вероятности, если вы «закроете один глаз и прищуритесь другим». С реальными вероятностями мы можем реализовать значимые границы принятия решений. Например, если верхний язык, возвращаемый классификатором, имеет вероятность 0,99, мы можем спокойно игнорировать словари других языков, тогда как, если он делает менее надежный прогноз, такой как 0,62 французского и 0,33 голландского, мы можем захотеть добавить оба словаря. Хотя последний тип вывода не следует интерпретировать как распределение языков в самом адресе (как в классификаторе с несколькими метками), результаты с несколькими языками с высокой вероятностью чаще всего возвращаются в таких случаях, как Брюссель, где адреса фактически написаны на двух языках.

Анализ числового выражения

Во многих адресах, особенно в Верхнем Ист-Сайде Манхэттена, кажется, числа написаны как слова, например Восемьдесят шестая улица вместо 86-я улица. Libpostal использует упрощенную форму Числового формата на основе правил (RBNF) в CLDR, в котором излагаются грамматические правила для разбора / написания чисел на различных языках.

Вместо того, чтобы пытаться исчерпывающе перечислить все числа и порядковые номера, которые могут использоваться в адресе, мы предлагаем несколько правил, которые затем система может использовать для анализа произвольных чисел.

В английском языке, когда мы видим слово «сотня», мы умножаем его на любое число меньше 100 слева и добавляем любое число меньше 100 справа. Там есть рекурсивная структура. Если мы знаем правило для разряда сотен и знаем, как анализировать все числа меньше 100, то мы можем «считать» до 1000.

Числовое написание на других языках может быть достаточно сложным. Например, во французском языке используются некоторые числа в кельтском стиле, которые переключаются на основание 20, поэтому quatre-vingt-douze («четыре двадцатых года») = 92. Итальянские числа редко содержат пробелы, поэтому milleottocentodue = 1802. В русском языке - порядковые числа. может иметь 3 пола. Libpostal анализирует их все, в настоящее время поддерживая числовые выражения более чем на 30 языках.

Римские цифры могут быть опционально распознаны на любом языке (так что «IX» нормализуется до 9), хотя они чаще всего встречаются в Европе в титулах пап, монархов и т. Д. В большинстве случаев римские цифры являются канонической формой и могут быть неоднозначным с другими токенами (одиночный «I» или «V» также может быть средним инициалом человека), поэтому также добавляется версия строки с ненормализованными римскими цифрами.

Транслитерация

Многие адреса по всему миру написаны нелатинскими шрифтами, такими как греческий, иврит, кириллица, хань и т. Д. В этих случаях адреса могут быть написаны местным алфавитом или транслитерированы, то есть преобразованы в эквивалент латинского алфавита. Поскольку целевой сценарий обычно латинский, транслитерацию также иногда называют романизацией.

Например, «Тверская улица» в Москве транслитерируется как «Тверская улица». Веб-сайт ресторана, вероятно, будет использовать первый для своего русского сайта, а второй - для своего международного сайта. Уличные знаки во многих странах (особенно в тех, где когда-то проходил чемпионат мира) обычно содержат обе версии, по крайней мере, в крупных городах.

Libpostal использует все транслитераторы, доступные в Common Locale Data Repository (CLDR) Консорциума Unicode, снова компилируя их в дерево для повышения производительности во время выполнения. Реализация легче, чем необходимость использования ICU, что является огромной зависимостью и может конфликтовать с версиями системы.

Каждый сценарий или комбинация сценария / языка может использовать один или несколько разных транслитераторов. Например, существует несколько различных стандартов транслитерации греческого или иврита, и libpostal испробует их все.

Существует также более простой транслитератор, преобразование Latin to ASCII, которое преобразует œ в oe и т. Д. Это дополнение к стандартной нормализации Unicode, которая разлагает ç на c и COMBINING. CEDILLA (U + 0327) »и при желании удалить диакритический знак, чтобы он оставался просто c . Удаление акцента - это своего рода нормализация невежественного американца, которая может изменить произношение или значение слов. Тем не менее, иногда адреса должны быть записаны в приближении ASCII (из-за клавиатуры), особенно при поиске, связанном с путешествиями, поэтому мы удаляем акцентные знаки по умолчанию с дополнительным флагом, чтобы предотвратить это.

Некоторые страны фактически переводят адреса на английский язык (что-то вроде «Тверская улица»), что создает дополнительную неоднозначность. За счет возможного добавления нескольких фиктивных нормализаций libpostal может обрабатывать такие переводы, просто добавляя английские словари в качестве варианта второго языка для определенных стран / языков / сценариев.

Разбор международного адреса

Синтаксический анализ - это процесс сегментирования адреса на такие компоненты, как номер дома, название улицы, город и т. Д. Хотя многие анализаторы адресов были написаны на протяжении многих лет, большинство из них основаны на правилах и предназначены только для обработки адресов в США. В libpostal мы разрабатываем первый анализатор адресов на основе NLP, который хорошо работает во всем мире.

Подход НЛП к синтаксическому анализу адресов

Синтаксический анализ международного адреса - это то, что мы никогда не могли бы надеяться решить детерминированно с помощью чего-то вроде регулярного выражения. Это может работать достаточно хорошо для одной страны, поскольку адреса, как правило, сильно структурированы, но существует слишком много вариаций и двусмысленностей, чтобы заставить его работать на разных языках. Именно в таких проблемах машинное обучение, особенно в форме структурированного обучения, действительно проявляет себя.

Большинство курсов / руководств / библиотек по НЛП сосредоточены на моделях и алгоритмах, но приложений с реальными наборами данных не так много. Libpostal предоставляет пример того, как выглядит приложение NLP непрерывного производственного качества. Я подробно расскажу о соответствующих этапах конвейера ниже, все они имеют открытый исходный код и опубликованы на Github как часть репозитория.

Создание помеченных данных из OSM

Адреса OpenStreetMap уже разделены на компоненты. Вот пример тегов OSM в формате JSON:

{
    "addr:housenumber": "30",
    "addr:postcode": "11217",
    "addr:street": "Lafayette Avenue",
    "name": "Brooklyn Academy of Music"
}

Именно такой вывод мы хотим, чтобы наш синтаксический анализатор выдавал. Эти адреса написаны вручную людьми, и их очень много, по последним подсчетам, более 50 миллионов.

Мы хотим создать контролируемый теггер, то есть мы пометили текст во время обучения, но только немаркированный текст (ввод геокодера) во время выполнения. Входными данными для модели последовательности является список помеченных токенов. Вот пример для указанного выше адреса:

Brooklyn/HOUSE Academy/HOUSE of/HOUSE Music/HOUSE 30/HOUSE_NUMBER Lafayette/ROAD Avenue/ROAD Brooklyn/CITY NY/STATE 11217/POSTCODE

Во время выполнения мы ожидаем увидеть только «Brooklyn Academy of Music, 30 Lafayette Avenue, Brooklyn, NY 11217», возможно, без запятых. Проявив немного творчества, мы можем реконструировать ввод произвольного текста и пометить каждый токен, чтобы получить приведенный выше обучающий пример.

Обратите внимание, что исходный адрес OSM не имеет структуры / порядка, поэтому нам нужно где-то его закодировать. Для этого мы можем использовать репозиторий OpenCage форматирование адресов, который определяет шаблоны адресов почти для каждой страны мира, причем охват со временем неуклонно растет. В США номер дома ставится перед названием улицы (123 Main Street), тогда как в Германии или Испании - наоборот (Calle Ruiz, 3). Шаблоны адресов предназначены для форматирования тегов OSM в удобочитаемые адреса в каждой стране. Это хорошее приближение того, как мы ожидаем, что входные данные геокодера будут выглядеть в этих странах, что означает, что у нас есть входные строки. Я лично внес вклад в репо для нескольких десятков стран, и его охват все время улучшается.

Также обратите внимание, что в адресе OSM отсутствуют город, штат и страна. Мы можем заполнить пробелы, проверив, содержится ли широта / долгота адреса в определенных административных многоугольниках. Чтобы нам не приходилось смотреть на каждый многоугольник на Земле для каждой широты / долготы, мы строим R-дерево, чтобы быстро проверить наличие ограничивающего прямоугольника, а затем проводим более медленный и тщательный тест точки в многоугольнике на ограничивающая рамка совпадает. Полигоны, которые мы используем, представляют собой смесь OSM-отношений, местностей Quattroshapes / GeoNames и Zetashapes для окрестностей.

Делаем синтаксический анализатор надежным

Поскольку геокодеры получают самые разные запросы, мы затем изменяем адрес несколькими способами, поэтому модель должна обучаться на множестве различных типов входных данных. С определенными случайными вероятностями мы используем:

  • Альтернативные имена: для некоторых административных многоугольников (например, «Нью-Йорк», «Нью-Йорк», «Нью-Йорк»), чтобы модель отображала как можно больше форм.
  • Названия на других языках. OSM отлично справляется с обработкой языка в адресах. По умолчанию предполагается, что такой тег, как «имя», написан на местном официальном языке или переносится через дефис, если языков несколько. Что-то вроде «name: en» будет английской версией. В странах с несколькими официальными языками, например в Гонконге, адреса почти всегда имеют языковые теги. Мы используем их, когда это возможно.
  • Нестандартные многоугольники: районы, округа, районы, кварталы и т. д., которые иногда можно увидеть в адресах.
  • Коды ISO и аббревиатуры штатов: чтобы синтаксический анализатор мог распознавать такие вещи, как «Берлин, Германия» и «Балтимор, Мэриленд».
  • Исключение компонентов: мы обычно создаем 2–3 разных версии адреса, при этом различные компоненты удаляются случайным образом. Таким образом, модель также должна научиться анализировать простые запросы типа «город, штат» вместе с адресами места проведения, чтобы она не стала слишком самоуверенной, например, что первый токен в адресе всегда является названием места проведения.

Структурированное обучение

В структурированном обучении мы обычно используем линейную модель, чтобы предсказать наиболее вероятный тег для конкретного слова с учетом некоторых локальных и контекстных атрибутов или функций. Что отличает структурированное обучение от других типов машинного обучения, так это то, что при структурированном обучении предсказание модели для предыдущего слова может использоваться для предсказания текущего слова. В аналогичных задачах, таких как тегирование части речи или распознавание именованных сущностей, мы обычно разрабатываем «функции функций», которые принимают следующие параметры:

  1. Вся последовательность слов
  2. Текущий индекс в этой последовательности
  3. Предсказанные теги для двух предыдущих слов

Затем функция возвращает набор функций, обычно двоичных, которые могут помочь предсказать лучший тег для данного слова.

История тегов - это то, что отличает последовательное обучение от других типов машинного обучения. Без истории тегов мы могли бы придумать функции для каждого слова (даже если они используют окружающие слова) и использовать что-то вроде логистической регрессии. В модели последовательности мы можем создавать функции, которые используют предсказанный тег предыдущего слова.

Рассмотрим использование слова «Бруклин». По отдельности мы могли бы предположить, что это означает город, но это может быть много других вещей, например Brooklyn Avenue, The Brooklyn Museum и т. Д. Если мы увидим слово "Brooklyn", а последним тегом был HOUSE_NUMBER, это, скорее всего, означает название улицы Brooklyn. Точно так же, если последним тегом был HOUSE (наш ярлык для названия места / здания), вполне вероятно, что мы находимся внутри названия места, например «Бруклинский музей».

Функции

Самым простым и наиболее предсказуемым признаком обычно является само текущее слово, но наличие всей последовательности означает, что могут быть особенности биграммы / триграммы и т.д. »Может устранить неоднозначность слов, используемых вне их нормального контекста, или помочь определить, что редкое слово является названием улицы. В адресе на французском языке знание того, что предыдущее слово было «авеню», столь же полезно, как и в случае «авеню Елисейских полей».

Обучение модели для нескольких языков влечет за собой еще несколько двусмысленностей. Возьмите слово «де». В испанском это предлог. Если мы вводим данные обучения в нижнем регистре по пути, это также может быть аббревиатура от Delaware («Wilmington de») или Deutschland («berlin de»). Опять же, очень полезно знать контекстные слова / теги.

В libpostal мы активно используем многоязычные словари адресов, которые использовались выше при нормализации, а также словари географических названий (также известные как географические справочники), скомпилированные из GeoNames и OSM. Мы группируем известные многословные фразы вместе, например, «Нью-Йорк» будет рассматриваться как единый жетон. Для каждой фразы мы сохраняем набор тегов, к которым она может относиться («Нью-Йорк» может быть городом или штатом), и какой из них, скорее всего, присутствует в обучающих данных. Контекстные особенности по-прежнему необходимы, поскольку многие улицы получили свое название от надлежащего места, например, «Пенсильвания-авеню», «Калле Уругвай» или «Виа Фиренце».

Мы также используем общий прием, чтобы фиксировать закономерности в числах. Вместо того, чтобы рассматривать каждое число как отдельное слово или токен, мы нормализуем все цифры до заглавной буквы «D» (поскольку мы используем нижний регистр, это не противоречит букве «d»). Это позволяет нам фиксировать полезные закономерности в цифрах и давать им возможность поделиться статистической силой. Некоторыми примерами могут быть «DDDDD» или «DDDDD-DDDD», которые, скорее всего, являются почтовыми индексами США. Таким образом, нам не нужно много обучающих примеров «90210», мы просто знаем, что это пятизначное число. GeoNames содержит набор данных о мировом почтовом индексе, который также используется для определения потенциальных действительных почтовых индексов. В некоторых странах, например в Южной Африке, используются 4-значные почтовые индексы, которые можно спутать с номерами домов, а почтовые индексы GeoNames помогают устранить неоднозначность.

Алгоритм обучения

Мы используем усредненный перцептрон, популяризированный Майклом Коллинзом из Колумбийского университета, который обеспечивает точность, близкую к современной, но при этом гораздо быстрее обучается, чем более изощренные модели, такие как условные случайные поля. На небольших тренировочных наборах дополнительная точность может стоить более медленного обучения. На ›50 млн примеров скорость обучения не подлежит обсуждению.

Базовый алгоритм персептрона использует простую процедуру обучения, основанную на ошибках, то есть, если текущие веса предсказывают правильный ответ, они не изменяются. Если предположение неверно, то для каждой характеристики добавляется один вес к весу правильного класса и один вычитается из веса предсказанного / неверного класса. Обучение осуществляется онлайн, по одному примеру за раз. Поскольку обновления веса очень редки и происходят только тогда, когда модель совершает ошибку, обучение происходит очень быстро.

В усредненном персептроне окончательные веса затем усредняются по всем итерациям. Без усреднения базовый перцептрон может тратить так много времени на изменение весов, чтобы приспособиться к нескольким примерам, которые он ошибается, что он производит необоснованный набор весов, который плохо переносится на новые примеры (также известный как переобучение). Таким образом, усреднение имеет аналогичный эффект регуляризации в других линейных моделях. Как и в случае стохастического градиентного спуска, обучающие примеры случайным образом перемешиваются перед каждым проходом, и мы делаем несколько проходов по всему обучающему набору.

Несмотря на свою простоту, этот метод на удивление конкурентоспособен в тегировании части речи, существующей задаче НЛП, которая ближе всего к синтаксическому анализу адресов и имеет лучшее соотношение скорость / точность из всех.

Оценка

В тегах части речи простая точность для каждого токена является наиболее интуитивно понятным показателем для оценки тегеров и используется в большей части литературы. Для синтаксического анализа адресов, поскольку мы хотим использовать результаты синтаксического анализа ниже по потоку в качестве полей при нормализации и поиске, одна ошибка изменяет JSON, который мы будем создавать на основе синтаксического анализа. Рассмотрим следующую ошибку:

Brooklyn/HOUSE Academy/HOUSE of/ROAD Music/HOUSE 30/HOUSE_NUMBER Lafayette/ROAD Avenue/ROAD Brooklyn/CITY NY/STATE 11217/POSTCODE

В системе полнотекстового поиска, такой как Elasticsearch, она может по-прежнему работать для поиска в поле имени с помощью [«Brooklyn Academy», «Music»] плюс другие поля и по-прежнему получать правильный результат, но если мы хотим создать структурированную базу данных анализируя или хэшируя поля и выполняя простой поиск, этот синтаксический анализ оказывается практически бесполезным.

Используемая нами метрика оценки - точность полного разбора, то есть доля адресов, на которых модель правильно маркирует каждый токен.

На задержанных данных (адреса не видны во время обучения) анализатор адресов libpostal в настоящее время получает 98,9% полных синтаксических анализов правильно. Это единая модель для всех языков, вариаций и комбинаций полей, которые есть в обучающем наборе OSM.

Будущие улучшения

Проницательный читатель заметит, что здесь все еще остается открытым вопрос: насколько хорошо синтезированная обучающая выборка соответствует реальным входным данным геокодера? Хотя это сложно измерить напрямую, большинство решений при построении обучающего набора до сих пор принималось путем изучения шаблонов в реальных адресах, извлеченных из Common Crawl, а также запросов пользователей, внесенных в проект с помощью производственного геокодера. .

Конечно, еще есть возможности для улучшения. Не все страны представлены в шаблонах форматирования адресов (хотя охват продолжает улучшаться с течением времени). В частности, страны, использующие восточноазиатскую систему адресации, такие как Китай, Япония и Южная Корея, трудны, потому что формат адреса зависит от того, какой язык / сценарий используется, что требует некоторых структурных изменений в репозитории форматирования адресов. В OSM эти адреса не всегда разделяются на компоненты, возможно, находящиеся в теге «addr: full». Однако, поскольку каждый язык использует определенные символы для разграничения компонентов адреса, должна быть возможность детерминированно анализировать полные адреса и использовать их в качестве обучающих примеров.

Парсер libpostal также еще не поддерживает номера квартир / квартир, поскольку они не включены в большинство адресов OSM (или шаблонов формата адресов, если на то пошло). Парсер обычно помечает их как часть поля номера дома или улицы. Для геокодеров номера квартир вряд ли будут часто появляться, поскольку люди склонны искать на уровне номера дома / здания, но они могут быть неизбежны при пакетном геокодировании. Поддержать их было бы относительно просто, добавляя номера квартир или этажей к некоторым обучающим примерам наугад (независимо от того, существуют ли эти квартиры на самом деле в конкретном здании или нет), или путем анализа ключа addr: flats. в OSM. Контекстные фразы, такие как Apt. или Flat можно произвольно выбирать из любого языка в libpostal с помощью словаря unit_types.

Выводы

Я надеюсь, что libpostal станет основой для многих замечательных геокодеров и приложений в ближайшие годы. Имея это в виду, он был разработан, чтобы:

  1. Международный / многоязычный
  2. Независимость от технологии и стека
  3. На основе открытых наборов данных и полностью с открытым исходным кодом

Международный по дизайну, а не второстепенный

Почти каждый геокодер использует различные близорукие предположения, например что адреса есть только в США, английский, латиница, глобальный север, буржуазия и т. д.

Полный охват L10N / I18N (локализация / интернационализация) означает, что нет оправдания для исключения людей на основе языков, на которых они говорят, или стран, в которых они живут. Требуется дополнительная степень строгости в распознавании и устранении наших собственных культурных предубеждений.

Конечно, всегда есть ограничения по времени и вниманию, поэтому libpostal отдает приоритет языкам простым, надеюсь, демократичным способом. Языки добавляются в порядке приоритета по количеству мировых адресов, которые они охватывают, приблизительно по OpenStreetMap.

Возможность использования на любой платформе

Libpostal написан на C в основном из соображений переносимости. Почти любой мыслимый язык программирования может вызывать код C. Уже существуют привязки libpostal для Python и NodeJS, и довольно легко написать привязки для других языков.

Полностью информирован на основе открытых данных

Libpostal использует несколько отличных наборов открытых данных для создания обучающих примеров для парсера адресов и классификатора языков:

  • OpenStreetMap широко используется libpostal для создания миллионов обучающих примеров анализируемых адресов и языковых классификаций.
  • GeoNames используется парсером адресов как справочник географических названий и почтовых индексов, а также будет использоваться для устранения неоднозначности географических названий в следующем выпуске.
  • Полигоны Quattroshapes и Zetashapes используются в различных местах для добавления дополнительных административных и локальных имен границ в обучающий набор парсера. Полигоны окрестностей Zetashapes были особенно полезны, поскольку окрестности - это простые точки в OSM.

Весь код предварительной обработки имеет открытый исходный код, поэтому исследователи, желающие построить свои собственные модели на основе открытых наборов геоданных, могут использовать его любым способом (каламбуры становятся все лучше) по своему выбору.

Прелесть использования этих живых, открытых, совместно редактируемых наборов данных заключается в том, что модели в libpostal можно обновлять и улучшать по мере улучшения наборов данных. Это также является отличным стимулом для пользователей библиотеки поддерживать открытые данные и вносить в них свой вклад.

Плавник

Ты сделал это! Единственное, что осталось сделать, если вы еще этого не сделали, это проверить libpostal на Github: https://github.com/openvenue/libpostal.

Если вы хотите внести свой вклад и помочь улучшить libpostal, вам не обязательно знать C или какой-либо другой язык программирования, если на то пошло.

Для нетехнических специалистов самый простой способ внести свой вклад - это проверить наши языковые словари, которые представляют собой простые текстовые файлы, содержащие все сокращения и фразы, которые распознает libpostal. Они влияют как на нормализацию, так и на парсер.

Найдите любой язык, на котором вы говорите (или добавьте каталог, если его нет в списке), и отредактируйте его. Ваша работа будет автоматически включена в следующую сборку.

Уже запланировано включение Libpostal как минимум в 3 приложения для геокодирования, написанных на таком же количестве языков. Если вы его используете или рассматриваете для своего проекта / компании, сообщите нам об этом.

Удачного геокодирования!

Присоединяйтесь к 30 000+ людям, которые читают еженедельную рассылку Машинное обучение, чтобы понять, как ИИ повлияет на их работу и жизнь.