Название статьи «SecureBoost: платформа федеративного обучения без потерь» описывает модель XGBoost в рамках вертикального федеративного обучения. Добро пожаловать в общедоступную учетную запись «Дифференциальная конфиденциальность» для лучшего чтения.

Кратко разберемся в общем контексте данной статьи.Структура диссертации разделена на 9 глав, а именно:

• 0 резюме
• 1. Введение
• 2 Базовые знания и связанная с этим работа
• 3 постановка задачи
• 4 Федеративное обучение в рамках SecureBoost
• 5 Федеративных рассуждений
• 6 Теоретический анализ
• 7 Обсуждение безопасности
• 8 Экспериментальный анализ
• 9 Резюме

Резюме

Защита конфиденциальности пользователей является важным вопросом машинного обучения, о чем свидетельствует введение Общего регламента по защите данных (GDPR) в Европейском союзе (ЕС) в мае 2018 года. GDPR стремится предоставить пользователям больший контроль над личными данными, что побуждает нас исследовать системы машинного обучения, сохраняющие конфиденциальность, для обмена данными. Для достижения этой цели в этой статье предлагается новая древовидная система с сохранением конфиденциальности без потерь, называемая SecureBoost в контексте федеративного обучения. SecureBoost сначала выполняет выравнивание объектов в соответствии с протоколом сохранения конфиденциальности, а затем строит повышающее дерево для нескольких сторон с помощью стратегии шифрования. Эта федеративная система обучения позволяет нескольким сторонам выполнять процесс обучения совместно с общими пользовательскими примерами, но с разными наборами функций (вертикальное федеративное обучение). Преимущество SecureBoost заключается в том, что он обеспечивает ту же точность, что и методы без сохранения конфиденциальности, но не раскрывает информацию о каждом поставщике частных данных. В этом документе показано, что инфраструктура SecureBoost так же точна, как и другие алгоритмы повышения несовместного градиентного дерева, требующие централизованных данных, и, следовательно, обладает высокой масштабируемостью и практичностью для таких приложений, как анализ кредитных рисков. Между тем, в этой статье обсуждается утечка информации во время выполнения протокола и предлагаются методы доказуемого ее уменьшения.

вводить

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

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

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

Недавно Google представила структуру федеративного обучения (FL) и развернула ее в облаке Android. Основная идея состоит в том, чтобы разрешить отдельным клиентам обновлять модели только на центральном сервере, который собирает модели, а не загружать необработанные данные. Google также представил протокол безопасного агрегирования, чтобы гарантировать, что параметры модели не будут передавать информацию о пользователях на сервер. Эта структура также известна как горизонтальная федерация = или федерация разделов данных, где каждый раздел соответствует подмножеству выборок данных, собранных от одного или нескольких пользователей.

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

Данные разных сторон обладают следующими свойствами:

• Большая таблица данных вертикально разделена или разделена на функции;
• Информация о метках есть только у поставщика данных;
• Есть некоторые пользователи, которыми совместно владеют все вовлеченные стороны.

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

Повышение дерева — это эффективный и широко используемый метод машинного обучения, который хорошо работает во многих задачах машинного обучения благодаря своей высокой эффективности и хорошей интерпретируемости. Например, XGBoost широко используется в различных приложениях, включая анализ кредитных рисков и исследование поведения пользователей. В этой статье мы предлагаем новую сквозную структуру усиленного алгоритма дерева с сохранением конфиденциальности, называемую SecureBoost, для обеспечения машинного обучения в федеративной среде. Secureboost был реализован в проекте с открытым исходным кодом FATE для поддержки промышленных приложений. Наша федеративная структура обучения работает в два этапа. Во-первых, мы находим общих пользователей между сторонами при соблюдении ограничений конфиденциальности. Затем мы совместно изучаем общие модели классификации или регрессии, не раскрывая друг другу никакой пользовательской информации. Основные вклады этой статьи резюмируются следующим образом:

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

Фоновые знания и связанная с этим работа

Чтобы защитить конфиденциальность данных при обучении модели, в статье [18] было предложено использовать дифференциальную конфиденциальность (DP) для изучения моделей глубокого обучения. Недавно Google представила федеративную структуру обучения для предотвращения передачи данных путем обучения модели на каждом мобильном терминале. Основная идея заключается в том, что каждый локальный мобильный терминал использует локальные данные для обучения локальной модели. Глобальную модель можно обновить, просто усредняя все локальные модели. Следуя той же идее, различные модели машинного обучения также реализуются в федеративной среде, включая деревья решений, линейную/логистическую регрессию и нейронные сети.

Все вышеперечисленные методы предназначены для горизонтально секционированных данных. В отличие от вертикального FL, горизонтальный FL требует более сложного механизма для декомпозиции функции потерь каждой стороны. Концепция продольного FL впервые предложила соответствующие протоколы на линейных моделях и нейронных сетях. Есть также некоторые методы по вертикали, такие как деревья решений. Однако эти методы должны раскрывать распределение классов для данного атрибута, что приводит к потенциальным рискам безопасности. Кроме того, они могут обрабатывать только дискретные данные, что не очень удобно для реальных сценариев. Напротив, метод, предложенный в этой статье, гарантирует защиту данных и может быть легко применен к видам непрерывных данных. Другая работа, представленная в [29], аппроксимирует нелинейные логистические потери с помощью разложения Тейлора для совместного выполнения логистической регрессии на зашифрованных продольных данных, что неизбежно ухудшит производительность модели. По сравнению с этими схемами метод, предложенный в данной статье, по своей сути не имеет потерь.

постановка задачи

Пусть \left{\mathbf{X}^{k} \in \mathbb{R}^{n_{k} \times d_{k}}\right}{k=1}^{m} представляет данные объектов, распределенных по m продольным делениям, где каждая строка \mathbf{X}{i *}^{k} \in \mathbb{R}^{1 \times d_{k}} представляет часть данных. Мы используем \mathcal{F}^{k}=\left{f_{1}, \ldots, f_{d_{k}}\right} для представления набора признаков, соответствующего матрице данных \mathbf{X}^{ к} . Любые две партии p и q имеют разные наборы признаков, т. е. \mathcal{F}^{p} \cap \mathcal{F}^{q}=\varnothing, \forall p \neq q \in{1 \ldots m } . У разных сторон также могут быть разные наборы пользователей, что допускает некоторую степень перекрытия. Только одна сторона имеет метку \mathbf{y}.

Active Party: мы определяем активную сторону как поставщика данных, который имеет как матрицу данных, так и метки классов. Поскольку информация о метках класса необходима для контролируемого обучения, активная сторона, естественно, берет на себя ответственность доминирующего сервера в федеративном обучении.

Passive Party: мы определяем поставщика данных только с матрицей данных как пассивную сторону. Пассивная сторона играет роль клиента в федеративной среде обучения.

Процесс машинного обучения (вертикальной федерации) защиты конфиденциальности при продольных данных может быть выражен как:данныйДанные продольной сегментации \left{\mathbf{X}^{k}\right}_{k=1}^{m}, распределенные по m участникам, и данные метки \mathbf{y} активной стороны,учитьсяМодель машинного обучения M, которая не допускает утечки данных ни от одной из сторон, где M_i — это карта данных на стороне i, а входные данные для M_i — это X_i. В то же время естьбезубыточный лимит, то есть, если защита конфиденциальности не рассматривается, модель, обученная путем сбора данных, представляет собой M', и мы требуем, чтобы потери M и M' были одинаковыми.

Федеративное обучение в рамках SecureBoost

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

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

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

Следуя общей схеме федеративного обучения, мы видим, что для разработки поддерживающей конфиденциальность структуры повышения дерева в условиях федеративного обучения нам, по сути, необходимо ответить на следующие три вопроса: (1) Каждый клиент (т. е. пассивная сторона) не получает Как вычислить обновленную модель на основе локальных данных в случае меток? (2) Как сервер (т.е. активная сторона) объединяет все обновленные модели, чтобы получить новую глобальную модель? (3) Как можно поделиться обновленной глобальной моделью между сторонами без раскрытия какой-либо информации? Чтобы ответить на эти три вопроса, мы сначала рассмотрим XGBoost в несовместных условиях.

Учитывая набор данных \mathbf{X} \in \mathbb{R}^{n \times d}, представляющий n выборок и d функций, XGBoost использует K деревьев регрессии для прогнозирования результатов:

\

Чтобы изучить вышеуказанное f_k, в t-м раунде XGBoost изучает модель f_t жадным способом, сводя к минимуму следующую цель:

\

где: \Omega\left(f_{t}\right)=\gamma T+\frac{1}{2} \lambda|w|^{2}, g_{i}=\partial_{\hat{y}^ {(t-1)}} l\left(y_{i}, \hat{y}^{(t-1)}\right) и h_{i}=\partial_{\hat{u}^{ (t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right).

Во время t-го раунда построения дерева решений модель разделяется на узлы с нулевой глубиной, пока не достигнет максимальной глубины. Оптимальный узел разделения задается следующим уравнением (где I_L, I_R представляют данные левого и правого узлов после разделения):

\

После построения оптимальной древовидной структуры (результата разбиения) вес w_j^* листового узла j можно рассчитать по следующей формуле, где I_j — данные о j-м листе:

\

Из вышеописанного процесса у нас есть следующие наблюдения:

• (1) Кандидаты на сегментацию и вычисление оптимальных весов листа зависят только от g и h, что упрощает адаптацию к системе федеративного обучения.
• (2) метка может быть выведена из g_i и h_i, например, при использовании квадрата ошибки мы имеем g_i = \hat{y}{i}^{(t-1)}-y{i}, так что будьте защищены.

Основываясь на приведенных выше наблюдениях, мы теперь представляем наш алгоритм интегрированного градиентного дерева. Из наблюдения (1) мы видим, что пассивные стороны могут использовать только свои локальные данные и g_i, h_i для определения своего локально оптимального разделения, что побуждает нас следовать этому подходу для декомпозиции задачи обучения каждой стороны. Однако, согласно наблюдению (2), g_i, h_i следует рассматривать как конфиденциальные данные, поскольку они могут раскрыть информацию о метке класса пассивным сторонам. Следовательно, чтобы сохранить g_i и h_i в секрете, активная сторона должна зашифровать g_i и h_i перед отправкой на пассивную сторону. Оставшаяся проблема заключается в том, как определить локальную оптимальную сегментацию для каждой пассивной стороны в MiQ.

По формуле расчета оптимального разделения (\mathcal{L}{s p}), если g вычисляется для каждого возможного разделения{l}=\sum_{i \in I_{L}} g_{i}, h_{l}=\sum_{i \in I_{L}} h_{i}, то вы можете найти наилучшее разделение. Поэтому далее мы покажем, как получить g_l и h_l, используя зашифрованные g_i и h_i, используя аддитивную гомоморфную схему шифрования. В этой статье используется схема Пайе.

В Пайе, предполагая, что зашифрованный текст данных u соответствует \langle u\rangle, тогда система Пайе имеет следующие свойства: \langle u\rangle\cdot \langle v\rangle = \langle u + v \rangle. Таким образом: \left\langle h_{l}\right\rangle=\prod_{i \in I_{L}}\left\langle h_{i}\right\rangle, \left\langle g_{l}\right \ rangle=\prod_{i \in I_{L}}\left\langle g_{i}\right\rangle. Поэтому оптимальное разбиение можно найти следующим образом: пассивная сторона локально вычисляет все возможные разбиения, вычисляет \langle g_l\rangle, \langle h_l\rangle и отправляет их активной стороне. Затем активная сторона расшифровывает и вычисляет наилучший узел разделения в соответствии с формулой наилучшего разделения.В этой статье используется метод аппроксимации из статьи [31], так что определенная оптимизация может быть выполнена без исчерпания всех возможных значений. Подробный поток показан в Алгоритме 1.

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

Пассивная сторона должна вести справочную таблицу, как показано на рисунке 3. Он содержит [идентификатор функции k, пороговое значение v] и уникальный идентификатор r для записи, чтобы можно было выполнить разделение. В то же время, поскольку активная сторона не имеет характеристик пассивной стороны, чтобы активная сторона знала, какой пассивной стороне передавать данные, и чтобы указать пассивной стороне, какое условие разделения использовать во время вывода, он связывает каждый узел дерева с парой (идентификатор стороны i, идентификатор записи r). Конкретные сведения об алгоритме разделенного поиска SecureBoost показаны в алгоритме 2.

Остается задача вычислить оптимальные веса листьев. Согласно весовой формуле w_j^* оптимальный вес листа j зависит только от \sum_{i \in I_{i}} g_{i} и \sum_{i \in I_{i}} h_{i}. Следовательно, он следует той же процедуре, что и процесс расщепления. При достижении конечного узла пассивная сторона отправляет \langle \sum_{i \in I_{i}} g_{i} \rangle и \langle \sum_{i \in I_{i}} g_{i} \rangle на Затем активная сторона расшифровывает его с помощью формулы расчета веса, чтобы вычислить соответствующий вес.

федеративное рассуждение

В этом разделе описывается, как изученная модель (распределенная между сторонами) может использоваться для классификации новых экземпляров, даже если характеристики экземпляра, который нужно классифицировать, являются частными и распределяются между сторонами. Поскольку каждая сторона знает свои характеристики, но ничего не знает о других, нам нужен безопасный протокол распределенного вывода для управления передачей от одной стороны к другой на основе принятых решений. Чтобы проиллюстрировать процесс вывода, мы рассмотрим систему с тремя сторонами, как показано на рисунке 3. В частности, первая сторона является активной стороной, и собираемая ею информация включает в себя ежемесячные платежи пользователя по счетам, образование и теги, независимо от того, производил ли пользователь X своевременные платежи. Сторона B и Сторона C являются пассивными сторонами и обладают такими характеристиками, как возраст, пол, семейное положение и кредитная линия соответственно. Предположим, мы хотим предсказать, заплатит ли пользователь X_6 вовремя, тогда все стороны должны сотрудничать, чтобы сделать прогноз. Весь процесс координируется активной стороной. Начиная с корня, обращаясь к записи [идентификатор стороны: 1, идентификатор записи: 1], активная сторона знает, что сторона 1 владеет корневым узлом, и, таким образом, просит сторону 1 извлечь соответствующий атрибут «Оплата счета» из своей таблицы поиска на основе по идентификатору записи 1. Поскольку категориальным атрибутом является оплата счета, и сторона 1 знает, что оплата счета пользователя X_6 составляет 4367, что меньше порогового значения 5000, она решает, что она должна перейти к своему левому дочернему узлу узел 1. Затем активная сторона ссылается на узел 1 связанная запись [идентификатор стороны: 3, идентификатор записи: 1] и требует, чтобы 3 стороны выполнили одну и ту же операцию. Этот процесс продолжается до тех пор, пока лист не будет достигнут.

теоретический анализ

Теорема 1. SecureBoost работает без потерь, то есть при тех же данных модель Federated Learning SecureBoost M точно такая же, как модель XGBoost M' в наборе данных (при тех же начальных условиях).

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

Обсуждение безопасности

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

Активная сторона находится в хорошем положении в Secure-Boost, потому что она понимает пространство экземпляров каждого разделения и какая сторона несет ответственность за решения каждого узла. Кроме того, он изучает все возможные значения g_l,g_r и h_l,h_r в процессе обучения. В этом случае первое кажется неизбежным, если только вы не готовы значительно увеличить накладные расходы на этапе логического вывода. Однако последнего можно избежать, используя безопасные методы многосторонних вычислений для сравнения зашифрованных значений (например, [33], [34]). Таким образом, активная сторона узнает только оптимальные g_l, g_r, h_l, h_r для каждой стороны, что, конечно же, существенно повлияет на эффективность в процессе обучения.

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

Теорема 2, учитывая изученную модель SecureBoost, чистоту листьев первого дерева можно вывести из веса листьев.

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

\

Согласно этому проигрышу, в первом раунде построения дерева решений имеем: g_{i}=\hat{y}{i}^{(0)}-y{i} и g_{i}=\шляпа{y}{i}^{(0)}\left(1-\hat{y}{i}^{(0)}\right), где \hat{y}{i}^{(0)} представляет начальное значение. Предположим, что все наши начальные значения определены как a, где (0 {i}^{(1)} = S\left(w_{j}^{*}\right)=S\left(-\frac{\sum_{i \in I_{j}} g_{i}} {\sum_{i \in I_{j}} h_{i}+\lambda}\right), где S(x) представляет сигмовидную функцию. Предполагая, что количество данных, связанных с листом j, равно n_j, тогда доля положительных выборок равна \theta_J, где n_j относительно велико, мы можем игнорировать -\frac{\sum_{i \in I_{j}} g_{i }} \lambda в знаменателе {\sum_{i \in I_{j}} h_{i}+\lambda} и переписать вычисление веса как:

\

То есть имеем \theta_j = a - a(a-1)w_j^, где a — параметр инициализации. так что w_j^является ключом к выводу \theta_j. Тогда \theta_j можно использовать для представления чистоты листа j, так как чистота может быть записана как \max(\theta_j, 1-\theta_j). Таким образом, учитывая первое дерево, можно сделать вывод о чистоте листовых узлов. Доказательство завершено.

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

Теорема 3, по мере уменьшения чистоты первого дерева остаточная информация будет уменьшаться.

Доказательство: как показано выше, для задачи бинарной классификации имеем g_{i}=\hat{y}{i}^{(t-1)}-y{i}, h_{i}=\hat{y}{i}^{(t-1)} *\left(1-\hat{y}{i}^{(t-1)}\right), где g_i \in [-1,1]. Поэтому существуют:

\

Когда мы строим дерево решений с k-м листом в t-й итерации, чтобы соответствовать остаткам предыдущего дерева, мы по существу делим данные на k кластеров, чтобы минимизировать следующие потери:

\

В то же время мы знаем, что \hat{y}{i}^{(t-1)} \in[0,1], g{i}=\hat{y}{i}^{(t-1)}-y{i}, поэтому у нас есть g_i \in [-1,0] для положительных образцов и g_i\in[0,1] для отрицательных образцов. Учитывая диапазон значений g_i, приведенное выше уравнение можно записать как:

\

где I_j ^ N и I_j ^ P представляют собой набор положительных и отрицательных выборок на листовом узле j соответственно. Затем мы предполагаем, что ожидания положительных и отрицательных выборок |g_i| равны \mu_p и \mu_n соответственно, тогда, когда размер выборки достаточно велик, приведенную выше формулу можно грубо записать как:

\

где n_j^n, n_j^p представляют количество положительных и отрицательных выборок на узле j. Поскольку u_n, u_p\in [0,1], числитель приведенной выше формулы должен быть положительным числом, а знаменатель — отрицательным числом. Таким образом, минимизация приведенного выше уравнения эквивалентна максимизации числителя и минимизации знаменателя. Обратите внимание, что числитель имеет вид \sum x^2, а знаменатель - (\sum x)^2, где в [0,1] приведенная выше формула в основном определяется числителем, поэтому минимизация приведенной выше формулы может быть эквивалентна максимальному изменению \left(n_{j}^{n} \mu_{n}-n_{j}^{p} \mu_{p}\right)^{2}. В идеале мы хотим, чтобы количество положительных и отрицательных выборок было сбалансировано, то есть n_j^n = n_j^p. Для отрицательных образцов \left|g_{i}\right|=\left|\hat{y}{i}^{(t-1)}-y{i}\right|=\hat{y}{i}^{(t-1)}, а положительные образцы имеют \left|g{i}\right|=\left|\hat{y}{i}^{(t-1)}-y{i}\right|=1-\hat{y}{i}^{(t-1)}, значит, \mu{n}=\frac{1}{N_{n}} \sum_{j=1}^{k}\left(1-\theta_{j}\right) n_{j} \hat{y}{i}^{(t-1)},\mu{p}=\frac{1}{N_{n}} \sum_{j=1}^{k} \theta_{j} n_{j}\left(1-\hat{y}_{i}^ {(t-1)}\right), поэтому |u_n-u_p| можно рассчитать как:

\

Когда положительные и отрицательные образцы сбалансированы, мы имеем:

\

Из приведенной выше формулы видно, что при S\left(\frac{a-\theta_{j}}{a(a-1)}\right)=a достигается минимальное значение, поэтому оптимальное значение \theta_j равно \theta_j^* = \left.a\left(1+(1-a) \ln \left(\frac{a}{1-a}\right)\right)\right). Чтобы добиться большего u_n-u_p, мы хотим, чтобы отклонение от \theta_j до \theta_j^* было как можно больше. Когда наша инициализация лучше, например \alpha = 0.5, \theta_j^=0,5, в это время максимизировать |\theta_j = \theta_j^| эквивалентно максимизации \max(\theta_j, 1-\theta_j), что и является чистотой. Следовательно, высокая чистота листовых узлов приведет к большой разнице между u_p и u_n, что в конечном итоге приведет к меньшей утечке конфиденциальности. Доказательство завершено

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

С учетом теоремы 3 эта статья доказывает, что RL-SecureBoost безопасен, пока его первое дерево получает достаточно информации, чтобы замаскировать фактические метки остатками. Кроме того, как мы позже продемонстрируем экспериментально, RL-SecureBoost работает так же, как и SecureBoost, с точки зрения точности предсказания.

анализ эксперимента

В этой статье используются следующие два общедоступных набора данных:

• Credit 1: Категориальный набор данных, показывающий, страдает ли каждый человек от серьезных экономических трудностей, содержит 10 атрибутов из 150 000 образцов.
• Credit 2: также является набором данных кредитного рейтинга, связанным с задачей прогнозирования того, будет ли пользователь платить вовремя. Всего он содержит 30000 данных и 25 свойств.

Эксперименты используют 2/3 данных для обучения, а остальные — для тестирования. В экспериментальном процессе использовались двухсторонние тесты, то есть вертикальное федеративное обучение двух сторон. Для объективного сравнения различных методов максимальная глубина дерева была установлена ​​равной 3, доля выборок, используемых для подбора одного дерева регрессии, составляла 0,8, а скорость обучения составляла 0,3 для всех методов. Схема шифрования использует Пайе с размером ключа 512 бит. Экспериментальная среда — 8 ГБ ОЗУ и процессор Intel Core i5-7200u.

Scalability

Эффективность SecureBoost может отражаться скоростью сходимости и временем выполнения, на которые могут влиять (1) максимальная глубина одного дерева регрессии и (2) размер набора данных. В этом подразделе мы проводим анализ сходимости и исследуем влияние всех переменных на время выполнения обучения. Все эксперименты проводятся на наборе данных Credit2.

Во-первых, нас интересует скорость сходимости. Мы сравниваем поведение сходимости SecureBoost с нефедеративными алгоритмами, включая GBDT и XGBoost. Как видно из рисунка 4, кривая обучения SecureBoost аналогична другим неинтегрированным методам в обучающем наборе данных и даже немного превосходит другие методы в тестовом наборе данных. Кроме того, сходимость потерь при обучении и тестировании SecureBoost очень похожа на поведение GBDT и XGBoost. (не понял, думаю скорость сходимости должна быть такой же как у XGBoost)

Затем, чтобы исследовать, как максимальная глубина одного дерева влияет на время обучения, мы варьируем максимальную глубину одного дерева между {3, 4, 5, 6, 7, 8} и записываем время выполнения. Как показано на рис. 5(а), время выполнения увеличивается почти линейно с максимальной глубиной одного дерева, что указывает на то, что мы можем обучать глубокие деревья с относительно небольшим дополнительным временем, что на практике очень привлекательно, особенно когда данные в больших сценах .

Наконец, мы исследуем влияние размера данных на время выполнения предлагаемой нами системы. Мы увеличиваем функции, взяв скалярный продукт. Мы установили максимальную глубину одного дерева регрессии на 3 и изменили количество признаков в {50, 500, 1000, 5000} и количество выборок в {5000, 10000, 30000}. Мы сравнили время выполнения, чтобы выяснить, как каждый вариант влияет на эффективность алгоритма. Мы делаем аналогичные наблюдения для рисунков 5(b) и 5(c), подразумевая, что количество выборок и количество признаков в равной степени влияют на время выполнения. Кроме того, мы видим, что предлагаемая нами структура хорошо масштабируется даже при относительно больших объемах данных.

Performance of RL-SecureBoost

Чтобы исследовать производительность RL-SecureBoost с точки зрения безопасности и точности прогнозирования, мы стремимся ответить на следующие вопросы: (1) Получает ли первое дерево достаточно информации, чтобы уменьшить утечку информации только на основе функций, имеющихся у активной стороны? (2) Есть ли потеря точности в RL-SecureBoost по сравнению с SecureBoost?

Во-первых, мы изучаем производительность RL-SecureBoost в области безопасности. Согласно первому теоретическому анализу мы оцениваем утечку информации на основе чистоты листа. Кроме того, мы знаем, что по мере увеличения чистоты листьев в первом дереве количество утечек информации уменьшается. Поэтому для проверки безопасности RL-SecureBoost мы должны показать, что производительность первого дерева RL-SecureBoost достаточна для уменьшения утечки информации из второго дерева. Как показано в таблице 1, мы сравнили среднюю чистоту листьев первого и второго деревьев. В частности, средняя чистота листьев представляет собой средневзвешенное значение, рассчитанное как \sum_{i=0}^{k} \frac{n_{i}}{n} p_{i} . Здесь k и n представляют количество листьев и общее количество выборок. p_i и n_i определяются как чистота листа и количество образцов, связанных с листом i. Согласно таблице 1, средняя чистота листа значительно снижается от первого дерева ко второму дереву в обоих наборах данных, что отражает значительно уменьшенную утечку информации. Кроме того, средняя чистота листьев второго дерева составляет чуть более 0,6 в обоих наборах данных, что достаточно для обеспечения безопасного протокола.

Затем, чтобы исследовать производительность прогнозирования RL-SecureBoost, мы сравниваем RL-SecureBoost с SecureBoost с точки зрения производительности первого дерева и общей производительности. Мы рассматриваем часто используемые показатели, включая точность, площадь под ROC-кривой (AUC) и показатель f1. Результаты представлены в таблице 2. Как видно, по сравнению с SecureBoost, RL-SecureBoost также работает почти во всех случаях. Мы также проводим попарный тест Вилкоксона со знаком ранга между RL-SecureBoost и SecureBoost. Результаты сравнения показывают, что RL-SecureBoost так же точен, как и SecureBoost, с уровнем значимости 0,05. Безубыточная природа RL-SecureBoost по-прежнему гарантируется.

Суммировать

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

публика

Добро пожаловать в «Дифференциальную конфиденциальность»