Данная работа является пересказом статьи M. Hulsebos et al. 2019. Sherlock: A Deep Learning Approach to Semantic Data Type Detection. KDD ’19, 1500–

https://doi.org/10.1145/3292500.3330993

Введение

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

Существуют специализированные системы подготовки и анализа данных. Большинство из них отлично справляется с определением атомарного типа колонки, такого как string, integer, boolean. Однако, с задачей определения семантического типа — собственно, того, что лежит в колонке (имя человека, название организации, город и прочее), не всё так гладко. При этом, успешное определение семантического типа может дать гораздо больше, чем простое знание атомарного типа. Имея на руках семантические типы колонок, можно скорее разобраться в незнакомой базе данных, и, например, быстро выделить все колонки, относящиеся к одной сущности реального мира.

Пример такой задачи из практики - это ситуация, когда один банк поглотил другой, и теперь надо “объединить” имеющиеся данные по вкладам. То есть, исходно у нас будет две схемы данных, касающихся одной и той же предметной области. При этом, названия таблиц и колонок скорее всего будут отличаться. Далее, возможно, что данные об одних и тех же сущностях могут оказаться разбросаны по разным таблицам. Например, во второй схеме номер телефона клиента может быть не в таблице Depositors, а в отдельной таблице Contacts. Понимание того, что находится в каждой колонке, может сильно упростить “объединение” данных.

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

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

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

Выбор признаков и препроцессинг

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

1. Глобальные статистики (27 признаков),

2. Аггрегированные распределения символов (960 признаков),

3. Предобученные эмбеддинги слов (200 признаков),

4. Самообученные векторы параграфов (400 признаков).

Глобальные статистики описывают высокоуровневые статистические свойства колонок. Например, “энтропия” описывает насколько равномерно распределены значения в колонке. Этот признак позволит алгоритму машинного обучения лучше отличать типы, которые содержат много повторяющихся значений (таких как, например, пол) от типов, которые в свою очередь содержат много уникальных значений (как, например, имя). Другие типы, как, например, вес и продажи могут содержать много численных значений, и для них используется статистика “медиана числа цифр в значениях колонки”. Полный список статистик приведен в статье.

Распределения символов. Авторы утверждают, что предварительный анализ продемонстрировал высокую предсказательную силу простых статистических признаков наподобие “доля значений в колонке содержащих цифры”.

Поэтому они решили добавить признаки, связанные с распределением символов в колонке. Были взяты все 96 видимых ASCII символов (цифры, буквы, знаки пунктуации, но без пробела) и для всей колонки были подсчитаны 10 статистических функций (среднее, медиана, минимум, максимум, сумма и прочее). В результате получилось еще 960 признаков.

Эмбеддинги слов. Некоторые семантические типы колонки содержат в себе часто встречающиеся слова. Например, тип “город” может содержать в себе значения наподобие New York City, Paris, London. Для описания семантического контента этих значений используются эмбеддинги слов, которые отображают эти слова во многомерное пространство численных векторов постоянной длины.

Авторы используют предобученный GloVe [1] словарь, где 400 000 английских слов представлены в виде векторов размерностью 50. Если значение в ячейке является отдельным словом, то ищется эмбеддинг в словаре, а если там несколько слов, то ищутся все и берется среднее. Затем, по всем ячейкам колонки подсчитывается среднее, мода, медиана и дисперсия компонентов.

Векторы параграфов. Чтобы представить каждую колонку в виде числового вектора используется Distributed Bag of Words version of Paragraph Vector (PV-DBOW) [2]. Векторы параграфов исходно были разработаны, чтобы представлять тему у фрагментов текста, однако потом оказалось, что подход эффективен и для других задач, таких как поиск подобных документов [3]. Авторы Sherlock используют этот подход следующим образом: каждая колонка - это “параграф”, в котором значения в ячейках являются “словами”. Вся колонка и ее значения закодированы one-hot векторами (https: //en.wikipedia.org/wiki/One-hot#Machine_learning_and_statistics).

Далее, собираются все колонки из всех классов и начинается процедура обучения, которая работает с каждой колонкой по отдельности. В данном случае обучающий набор состоит из ровно тех же 60% данных, которые используются для обучении модели в целом (раздел 5).

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

Используя библиотеку Gensim [4], авторы тренировали эту модель в течение 20 итераций. Модель отображала каждую колонку в 400-мерный вектор параграфа. Такой размер был обусловлен балансом между предсказательной способностью и скоростью.

Наконец, авторы были вынуждены проводить препроцессинг данных. Дело в том, что в датасете на котором проводились эксперименты, некоторые типы встречались чаще чем другие. Например, “description” и “city” встречаются чаще чем “collection” и “continent”.

Поэтому авторы разработали специальную процедуру которая будет бороться с такой неравномерностью. Они решили брать не более чем 15 000 колонок на каждый класс и исключить 10% типов, которые содержали менее 1 000 колонок.

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

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

В итоге, такая фильтрация дала 686,765 колонок соответствующих 78 семантическим типам.

Архитектура сети

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

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

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

Далее выход подсетей конкатенируется, добавляются глобальные статистики и подаются на вход основной сети. Каждая сеть (включая основную) является двухуровневой сетью с ReLU активацией.

Эксперименты с размером внутренних уровней показали, что 300, 200, и 400 являются лучшим выбором для подсетей, работающих с распределениями символов, эмбеддингами и векторами параграфов, соответственно. Для борьбы с переобучением использовали дроп-аут слои (drop out layers) и сокращение веса (weight decay).

В конце авторы поставили softmax слой, который и генерирует предсказание семантического типа. Реализация была выполнена с помощью TensorFlow.

Эксперименты

Для обучения Sherlock были взяты столбцы из корпуса VizNet [5], состоящего из данных открытых хранилищ и онлайн-платформ визуализации. Таблицы VizNet имеют сопоставление с семантическими типами из DBpedia [6]. Было выбрано 78 семантических типов (рисунок 4).

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

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

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

Регулярные выражения. Выучиваются регулярные выражения для каждого типа, используя эволюционную процедуру Bartoli [7]. Для выучивания регулярных выражений выбираются 50 случайных записей одного типа, в качестве положительных значений, и 50 записей других типов, в качестве отрицательных. Как и в случае словаря, во время тестирования выбираются 1000 случайных значений из столбца и проверяются регулярными выражениям для каждого типа, после чего столбец классифицируется, как наиболее часто совпадающий тип.

Краудсорсинговые аннотации. Был проведён краудсорсинговый эксперимент на платформе Mechanical Turk. Участники выполнили три теста из десяти вопросов. Каждый вопрос предоставлял список из 10 значений данных одного столбца и просил выбрать один из 78 типов. В эксперименте участвовали 390 участников, которые были носителями английского языка и имели рейтинг одобрения больше 95. В итоге было получено 11700 аннотаций. Для каждого образца выбирался наиболее часто аннотированный тип.

Результаты

При тестировании использовалось 60/20/20 разбиение на обучающую, валидирующую и тестирующую части, соответственно. В качестве основной метрики бралась F1 взвешенная на количество колонок в классе в тестовом множестве. Кроме того, замерялась вычислительная трудоемкость и объем занимаемого пространства.

 Результаты представлены на рисунке 5. Авторы предполагают, что плохие показатели краудсорсинговых аннотаций вызваны тяжестью выбора из 78 типов, поэтому есть вероятность, что результаты улучшаться, если типов-кандидатов будет меньше. Другое объяснение — это то, что участники краудсорсинга имеют трудности при различении типов, которые им неизвестны или содержат много численных данных. Кроме того, авторы считают, что качество улучшится, если будет выделено больше времени на обучение участников краудсорсинга и улучшен контроль качества.

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

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

Далее, на рисунке 6 приведены типы, показавшие лучшие и худшие результаты. В таблице Support обозначено количество колонок для данного класса в тестовом множестве.  Sherlock показывает хорошие результаты на типах, которые содержат конечное множество значений, такие как оценки (grades). Другие “хорошие” типы имеют четко заданный символьный паттерн (ISBN, дата рождения, итд). При этом, метод дает плохие результаты на колонках, в которых находятся только численные значения или же на колонках, в которых значения появляются в нескольких классах.

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

Итог

Разобранная статья была первой, предложившей использовать современные методы машинного обучения для данной задачи. За ней последовали и другие [8-14], некоторые из которых мы, возможно, разберем позже.

Список литературы 

[1] Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1532–1543, Doha, Qatar, October 2014. Association for Computational Linguistics.

 [2] Quoc Le and Tomas Mikolov. Distributed representations of sentences and documents. In Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32, ICML’14, page II–1188–II–1196. JMLR.org, 2014.

 [3] Andrew M. Dai, Christopher Olah, and Quoc V. Le. Document embedding with paragraph vectors. CoRR, abs/1507.07998, 2015.

 [4] Radim Řehůřek and Petr Sojka. Software Framework for Topic Modelling with Large Corpora. In Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks, pages 45–50. ELRA, May 2010. http://is.muni.cz/publication/884893/en.

[5] Kevin Hu, Snehalkumar ’Neil’ S. Gaikwad, Madelon Hulsebos, Michiel A. Bakker, Emanuel Zgraggen, César Hidalgo, Tim Kraska, Guoliang Li, Arvind Satyanarayan, and Çağatay Demiralp. VizNet: Towards A Large-Scale Visualization Learning and Benchmarking Repository, page 1–12. Association for Computing Machinery, New York, NY, USA, 2019.

 [6] Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. Dbpedia: A nucleus for a web of open data. In Karl Aberer, Key-Sun Choi, Natasha Noy, Dean Allemang, Kyung-Il Lee, Lyndon Nixon, Jennifer Golbeck, Peter Mika, Diana Maynard, Riichiro Mizoguchi, Guus Schreiber, and Philippe Cudré-Mauroux, editors, The Semantic Web, pages 722–735, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.

 [7] Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, and Fabiano Tarlao. Inference of regular expressions for text extraction from examples. IEEE Transactions on Knowledge and Data Engineering, 28(5):1217–1230, 2016.

 [8] Dan Zhang, Madelon Hulsebos, Yoshihiko Suhara, Çağatay Demiralp, Jinfeng Li, and Wang-Chiew Tan. Sato: contextual semantic type detection in tables. Proceedings of the VLDB Endowment, 13(12):1835–1848, July 2020.

 [9] Xiang Deng, Huan Sun, Alyssa Lees, You Wu, and Cong Yu. TURL: table understanding through representation learning. Proceedings of the VLDB Endowment, 14(3):307–319, November 2020.

 [10] Sara Bonfitto, Luca Cappelletti, Fabrizio Trovato, Giorgio Valentini, and Marco Mesiti. Semi-automatic Column Type Inference for CSV Table Understanding. In Tomáš Bureš, Riccardo Dondi, Johann Gamper, Giovanna Guerrini, Tomasz Jurdziński, Claus Pahl, Florian Sikora, and Prudence W.H. Wong, editors, SOFSEM 2021: Theory and Practice of Computer Science, Lecture Notes in Computer Science, pages 535–549, Cham, 2021. Springer International Publishing.

 [11] Daheng Wang, Prashant Shiralkar, Colin Lockard, Binxuan Huang, Xin Luna Dong, and Meng Jiang. TCN: Table Convolutional Network for Web Table Interpretation. arXiv:2102.09460 [cs], February 2021. arXiv: 2102.09460.

 [12] Zhiruo Wang, Haoyu Dong, Ran Jia, Jia Li, Zhiyi Fu, Shi Han, and Dongmei Zhang. Structure-aware Pre-training for Table Understanding with Tree-based Transformers. arXiv:2010.12537 [cs], November 2020. arXiv: 2010.12537.

 [13] Tong Guo, Derong Shen, Tiezheng Nie, and Yue Kou. Web Table Column Type Detection Using Deep Learning and Probability Graph Model. In Guojun Wang, Xuemin Lin, James Hendler, Wei Song, Zhuoming Xu, and Genggeng Liu, editors, Web Information Systems and Applications, Lecture Notes in Computer Science, pages 401–414, Cham, 2020. Springer International Publishing.

 [14] Sven Langenecker, Christoph Sturm, Christian Schalles, and Carsten Binnig. Towards Learned Metadata Extraction for Data Lakes. Gesellschaft für Informatik, Bonn, 2021. Accepted: 2021-03-16T07:57:10Z ISSN: 1617-5468.

Подготовили: Платон Федоров, Георгий Чернышев