Сколько стоят мои данные?

Сколько стоят мои данные?

Мы предоставляем компаниям личные данные каждый день, но сколько они стоят на самом деле?

Серия Oasis Tech посвящена новым захватывающим передовым технологиям, частично разработанным членами Oasis. На этой неделе мы представляем вам Сколько стоят мои данные?, Статью Руокси Цзя, в которой обсуждаются методы, предложенные в наших недавних статьях AISTATS и VLDB, которые пытаются ответить на этот вопрос в контексте машинного обучения. Это совместная работа с Дэвидом Дао, Боксином Вангом, Фрэнсис Энн Хубис, Незихе Мерве Гурель, Ником Хайнсом, Бо Ли, Се Чжан, Костасом Дж. Спаносом и Дон Сонг, а также совместная работа Калифорнийского университета в Беркли, ETH Zurich, и UIUC. Более подробную информацию о работе в нашей группе можно найти здесь.

Люди ежедневно передают компаниям огромные объемы своих личных данных, и эти данные используются для создания огромных бизнес-ценностей. Некоторые экономисты и политики утверждают, что людям нужно платить за их взносы, но вопрос на миллион долларов заключается в следующем: насколько?

Какие существуют подходы к оценке данных?

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

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

Однако существующие схемы оценки данных не принимают во внимание следующие важные пожелания:

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

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

Каково было бы хорошее представление о ценности данных?

Из-за того, что значение данных зависит от конкретной задачи, оно должно зависеть от полезности модели машинного обучения, обученной на данных. Предположим, что модель машинного обучения приносит определенную прибыль. Затем мы можем свести проблему оценки данных к проблеме распределения прибыли, которая разделяет общую полезность модели машинного обучения между различными источниками данных. Действительно, справедливое распределение прибыли, созданной коллективными усилиями, является хорошо изученной проблемой в теории кооперативных игр. Самая известная схема распределения прибыли - это значение Шепли. Значение Шепли присваивает каждому игроку в игре действительное число, чтобы указать относительную важность их вклада. В частности, для N игроков значение Шепли игрока i (i∈I = 1,…, N) определяется как

где U (S) - функция полезности, которая оценивает ценность подмножества игроков S. В приведенном выше определении разница в скобках измеряет, насколько увеличивается выигрыш, когда игрок i добавляется к определенному подмножеству S; таким образом, значение Шепли измеряет средний вклад игрока i в каждую возможную группу других игроков в игре.

Связывая эти теоретико-игровые концепции с проблемой оценки данных, можно рассматривать игроков как источники обучающих данных и, соответственно, функцию полезности U (S) как меру производительности модели, обученной на подмножестве S обучающих данных. Таким образом, значение Шепли можно использовать для определения значения каждого источника данных. Значение Шепли привлекательно, потому что это схема распределения единственной прибыли, которая удовлетворяет следующим свойствам:

• Групповая рациональность: общая полезность модели машинного обучения полностью распределяется между разными источниками данных, то есть ∑ sᵢ = U (I). Это естественное требование, поскольку авторы данных ожидают, что общая выгода будет полностью распределена.
• Справедливость: два источника данных, которые имеют одинаковый вклад в полезность модели, должны иметь одинаковое значение; более того, источники данных с нулевым вкладом во все подмножества набора данных не должны получать никакой выгоды.
• Аддитивность: значения для нескольких утилит складываются в значение для утилиты, которое является суммой всех этих утилит. Это свойство обобщает оценку данных для одной задачи на несколько задач. В частности, если каждая задача связана с функцией полезности в качестве меры производительности, со свойством аддитивности, мы можем вычислить значение данных для нескольких задач, просто вычислив значение Шепли относительно агрегированной функции полезности.

Поскольку значение Шепли однозначно удовлетворяет вышеупомянутым свойствам и, естественно, приводит к схеме выплаты, зависящей от основной задачи, мы используем значение Шепли как понятие значения данных. Хотя изложенная концепция кажется правдоподобной, у нее есть несколько фундаментальных проблем: вычисление значения Шепли, как правило, требует вычисления функции полезности экспоненциальное количество раз; Хуже того, оценка функции полезности означает повторное обучение модели в контексте машинного обучения. Это явно непреодолимо даже для небольшого набора данных. Интересно, что если сосредоточиться на контексте машинного обучения, возникают некоторые возможности для решения проблемы масштабируемости. Затем мы покажем, что для классификации K-ближайших соседей (KNN) можно избавиться от необходимости повторно обучать модели и вычислять значение Шепли за квазилинейное время - экспоненциальное улучшение вычислительной эффективности!

Эффективные алгоритмы для KNN

Чтобы понять, почему KNN поддается эффективной оценке данных, мы рассматриваем K = 1 и исследуем следующую простую функцию полезности, определенную для 1NN: U (S) = 1, если метка контрольной точки правильно предсказана ее ближайшим соседом в S и 0 в противном случае. Для данной контрольной точки полезность набора полностью определяется ближайшим соседом в этом наборе к контрольной точке. Таким образом, вклад точки i в подмножество S равен нулю, если ближайший сосед в S находится ближе к контрольной точке, чем i. Когда мы повторно исследуем значение Шепли, мы видим, что для многих S U (S∪i) −U (S) = 0. На рисунке 1 показан пример такого S. Этот простой пример показывает, что вычислительные требования для значения Шепли могут быть значительно уменьшены для KNN.

Для данной контрольной точки (x test, y test) мы позволяем αk (S) обозначать k-го ближайшего соседа в S к контрольной точке. Рассмотрим следующую функцию полезности, которая измеряет вероятность предсказания правильной метки конкретной контрольной точки для KNN:

Теперь предположим, что данные обучения отсортированы по их сходству с контрольной точкой. Мы разрабатываем простой рекурсивный алгоритм для вычисления значения Шепли всех обучающих точек от самого дальнего соседа тестовой точки до ближайшего. Пусть I [⋅] представляет индикаторную функцию. Затем алгоритм работает следующим образом:

Этот алгоритм может быть расширен до случая, когда полезность определяется как вероятность предсказания правильных меток для нескольких контрольных точек. Благодаря свойству аддитивности значение Шепли для нескольких тестовых точек представляет собой сумму значений Шепли для каждой тестовой точки. Вычислительная сложность составляет O (N log NN test) для N обучающих точек и N контрольных точек - это просто сложность сортировки алгоритм!

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

Повышение эффективности для других моделей машинного обучения

Значение Шепли для KNN является эффективным из-за особой структуры местоположения KNN. Для общих моделей машинного обучения точное вычисление значения Шепли неизбежно происходит медленнее. Для решения этой проблемы в предшествующей работе часто используются алгоритмы аппроксимации на основе Монте-Карло. Основная идея этих алгоритмов аппроксимации состоит в том, чтобы рассматривать значение Шепли обучающей точки как ожидаемый вклад в случайное подмножество и использовать среднее значение выборки для аппроксимации математического ожидания. По определению значения Шепли, случайный набор имеет размер от 0 до N-1 с равной вероятностью (соответствует коэффициенту 1 / N), а также с равной вероятностью может быть любым подмножеством данного размера (соответствующего 1 / ( N − 1 выбрать | S |) фактор). На практике можно реализовать эквивалентный сэмплер, нарисовав случайную перестановку обучающего набора. Затем алгоритм приближения переходит к вычислению предельной полезности точки по отношению к точкам, предшествующим ей, и усреднению предельной полезности по различным перестановкам. Это был современный метод оценки значения Шепли для общих функций полезности (далее называемый базовым приближением). Чтобы оценить производительность алгоритма аппроксимации, мы можем посмотреть на количество оценок полезности, необходимых для достижения некоторых гарантий ошибки аппроксимации. Используя границу Хёффдинга, можно доказать, что описанный выше алгоритм аппроксимации базовой линии требует O (N ²log N) оценок полезности, чтобы квадрат ошибки между оценкой и основной истинностью Шепли значение ограничено с большой вероятностью. Можем ли мы уменьшить количество оценок полезности при сохранении той же гарантии ошибки аппроксимации?

Мы разработали алгоритм аппроксимации, который требует только сублинейных оценок полезности O (N (log N) ²), используя обмен информацией между различными случайными выборками. Ключевая идея заключается в том, что если точка данных имеет высокое значение, она имеет тенденцию повышать полезность всех подмножеств, содержащих ее. Это вдохновляет нас нарисовать несколько случайных подмножеств и записать наличие каждой обучающей точки в этих случайно выбранных подмножествах. Обозначение появления i-го и j-го обучающих данных через βi и βj. Мы можем грамотно спроектировать распределение случайных подмножеств так, чтобы ожидание

равно si − sj. Мы можем выбрать точку привязки, скажем, s1, и использовать выборочное среднее значение

для всех i = 2,…, N, чтобы оценить разницу значений Шепли от всех других тренировочных точек до s1. Затем мы можем просто выполнить еще несколько оценок полезности для оценки s1, что позволяет нам восстановить значение Шепли для всех других точек. Подробнее об этом алгоритме можно прочитать в нашей статье. Поскольку этот алгоритм вычисляет значение Шепли, просто исследуя полезность групп данных, в дальнейшем мы будем называть этот алгоритм приближением на основе группового тестирования. В нашей статье также обсуждаются даже более эффективные способы оценки значения Шепли, когда могут быть сделаны новые предположения, такие как разреженность значений Шепли и стабильность базового алгоритма обучения.

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

Во-первых, мы демонстрируем эффективность предложенного метода для вычисления точного значения Шепли для KNN. Мы тестируем время выполнения с использованием процессора Intel Core i7 с тактовой частотой 2,6 ГГц и сравниваем точный алгоритм с базовым приближением Монте-Карло. На рисунке 2 (а) показано, что оценка Монте-Карло значения Шепли для каждой обучающей точки сходится к результату точного алгоритма с достаточным количеством симуляций, что указывает на правильность нашего точного алгоритма. Что еще более важно, точный алгоритм на несколько порядков быстрее, чем базовое приближение, как показано на рисунке 2 (b).

С помощью предложенного алгоритма мы впервые можем вычислить значения данных для практически большой базы данных. На рисунке 3 показан результат крупномасштабного эксперимента с использованием значения KNN Shapley. Мы берем 1,5 миллиона изображений с предварительно рассчитанными характеристиками и ярлыками из набора данных Yahoo Flickr Creative Commons 100 Million (YFCC100m). Мы заметили, что значение KNN Shapley интуитивно понятно - изображения с наивысшими значениями семантически коррелируют с соответствующим тестовым изображением. Этот эксперимент занимает всего несколько секунд на тестовое изображение на одном процессоре и может быть распараллелен для большого набора тестов.

Аналогичным образом, рисунок 4 (a) демонстрирует точность предлагаемой нами аппроксимации на основе группового тестирования, а рисунок 4 (b) показывает, что приближение на основе группового тестирования превосходит базовое приближение на несколько порядков для большого количества точек данных.

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

Значение Шепли также можно использовать для понимания состязательного обучения, которое является эффективным методом повышения устойчивости модели к состязательности путем введения состязательных примеров в набор обучающих данных. На практике мы измеряем надежность с точки зрения точности теста на наборе данных, содержащем состязательные примеры. Мы ожидаем, что состязательные примеры в наборе обучающих данных станут более ценными по мере того, как в набор тестовых данных будет добавлено больше состязательных примеров. На основе MNIST мы создаем обучающий набор данных, который содержит как благоприятные, так и состязательные примеры, и синтезируем тестовые наборы данных с различными соотношениями смешивания состязательных и благоприятных условий. Два популярных алгоритма атаки, а именно метод быстрого градиента знака (FGSM) и итеративная атака (CW), используются для генерации состязательных примеров. На рис. 6 (a) и (b) сравнивается среднее значение Шепли для состязательных примеров и для безобидных примеров в наборе обучающих данных. Отрицательный тестовый проигрыш для логистической регрессии используется в качестве функции полезности. Мы видим, что ценность состязательных примеров для Шепли возрастает по мере того, как тестовые данные становятся более состязательными; напротив, ценность доброкачественных примеров Шепли снижается. Кроме того, состязательные примеры в обучающем наборе более ценны, если они созданы на основе одного и того же алгоритма атаки во время тестирования.

Заключение

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