Модель дерева федеративного обучения и безопасности Дерево решений SecureBoost

искусственный интеллект
Модель дерева федеративного обучения и безопасности Дерево решений SecureBoost

Модель дерева федеративного обучения и безопасности Дерево решений SecureBoost

@[toc]

1 Федеральное образование

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

Сегодня, при высоком развитии ИИ, многомерные и качественные данные являются узким местом, сдерживающим его дальнейшее развитие. Поскольку организации уделяют все больше и больше внимания данным, сотрудничество с данными между организациями и между различными отделами внутри организации будет становиться все более и более осторожным, что приведет к тому, что большой объем данных будет существовать в виде изолированных островков.在这里插入图片描述

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

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

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

Поскольку древовидная модель является относительно информативной, невозможно решить чистый SecureBoost за один шаг, поэтому эта статья разделена на следующие темы.Основной контекст: дерево решений -> метод ансамбля Бэгинг и бустинг -> GBDT -> XGBoost -> Безопасное дерево повышения. Я надеюсь, что благодаря этой серии статей читатели смогут получить всестороннее и всестороннее представление о методе федеративного обучения SecureBoost.

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

2 Decision Tree

2.1 Определение дерева решений

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

Возьмем рабочее место в качестве примера.В настоящее время вся компания имеет сложную отраслевую технологическую область, которую нужно сломать.В это время многие коллеги на рабочем месте, которые не лгут, надеются, что они смогут решить эту проблему, но поскольку это отраслевая технологическая проблема, не все могут быть решены. Исходя из этого, в первую очередь нужно подумать, хватит ли у вас мужества сделать это, а затем подумать, есть ли у вас возможность это сделать.Если у вас нет возможности это сделать, можете ли вы работать с талантливыми людьми делать это дело?Если ты талантлив,то можешь сделать это сам.,тогда с ним ничего не вышло.在这里插入图片描述

Следующий автор вводит знания, связанные с деревьями решений.

2.2 Основа дерева решений

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

2.2.1 Энтропия

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

P(X=xi)=pi,i=1,2,...,nP(X=x_i) = p_i, i=1,2,...,n

Тогда энтропия случайной величины X определяется как:

H(X)=−∑inpilogpiH(X) = -\sum_i^np_ilogp_i

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

在这里插入图片描述

2.2.2 Условная энтропия

Предполагая случайные величины (X, Y), их совместное распределение выглядит следующим образом:

P(X=xi,Y=yj)=pij,i=1,2,...,n;j=1,2,...,mP(X=x_i, Y=y_j)=p_{ij}, i = 1,2,...,n; \quad j=1,2,...,m

Затем мы определяем условную энтропию H(Y|X) как представление неопределенности случайной величины Y при условии известной случайной величины X, то есть энтропию условного распределения вероятностей Y при заданных условиях of X - это математика X, ожидающая:

H(Y∣X)=∑inpiH(Y∣X=xi)H(Y|X)=\sum_i^np_iH(Y|X=x_i)

2.2.3 Получение информации

Прирост информации g(D, A) признака A к обучающему набору данных D, тогда прирост информации определяется как сумма эмпирической энтропии H(D) набора D и условной энтропии H(D|A) набора D при заданных условиях признака А плохой, т.е.

g(D,A)=H(D)−H(D∣A)g(D,A)=H(D) - H(D|A)

Если прирост информации больше, это означает, что информационная энтропия после деления меньше, а это означает, что данные после деления имеют тенденцию быть стабильными, а более стабильные данные означают, что мы можем лучше предсказать данные.

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

Предположим, что партия образцов имеет в общей сложностиKКлассификация определяется какck,k=1,2,...,K,но∣Ck∣определяется как принадлежащийCkколичество образцов, затем∑k=1K∣Ck∣=∣d∣,ПредполагатьПредполагая, что партия образцов имеет в общей сложности K категорий, определенных как c_k,k=1,2,...,K, тогда |C_k| определяется как количество образцов, принадлежащих C_k, тогда \sum_{k=1 }^K|C_k |=|d|, пусть
особенностьAимеютnразные значения,a1,a2,...,an. по характеристикамAЗначение будетDразделен наnподмножествоD1,D2,...,Dn,∣Di∣заDiобразецФункция A имеет n различных значений, {a_1,a_2, ...,a_n}. Затем в соответствии со значением признака A, D делится на n подмножеств D_1, D_2,..., D_n, |D_i| являются выборками D_i
номер,∑i=1n∣Di∣=∣D∣. Также определите подмножестваDiпринадлежитCkКоллекция образцовDij,ноDij=Di∩Ck,число, \sum_{i=1}^n|D_i|= |D|. При этом множество отсчетов, принадлежащих C_k в подмножестве D_i, определяется как D_{ij}, тогда D_{ij} = D_i \cap C_k,
∣Dik∣определяется какDikколичество образцов.|D_{ik}| определяется как количество выборок D_{ik}.

Затем, согласно приведенному выше описанию, эмпирическая условная энтропия H(D|A) признака A для набора данных D

H(D∣A)=−∑i=1nDiD ∑k=1KDikDi log⁡2DikDi H(D|A) = - \sum_{i=1}^n \frac{D_i}{D}\ \sum_{k=1}^K \frac{D_{ik}}{D_i} \ \log_2{ \frac{D_{ik}}{D_i} \ }

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

2.3 Стратегия обрезки

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

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

  1. Предварительная обрезка: обрезка выполняется на этапе генерации дерева.
  2. Постобрезка: после создания дерева проверьте, какие ветви нужно удалить.

在这里插入图片描述

2.4 Алгоритм ID3

Алгоритм ID3 был впервые предложен Дж. Россом Куинланом в Сиднейском университете в 1975 г. Ядром алгоритма является «информационная энтропия». Алгоритм ID3 вычисляет прирост информации для каждого атрибута и считает, что атрибут с высоким приростом информации является хорошим атрибутом Каждое подразделение выбирает атрибут с наибольшим приростом информации в качестве стандарта разделения и повторяет этот процесс до тех пор, пока не будет получено дерево решений, которое может идеально классифицировать обучающие выборки.

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

2.4.1 Алгоритм ID3 для построения схемы дерева решений

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

2.4.2 Обзор преимуществ и недостатков алгоритма ID3

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

2.5 Алгоритм C4.5

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

2.5.1 Алгоритм C4.5 для построения схемы дерева решений

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

2.5.2 Обзор преимуществ и недостатков алгоритма C4.5

  • Структура модели: N-арное дерево, если значение признака больше, то объем расчета очень значительный.

  • Цель модели: подходит для решения задач классификации.

  • Корреляция признаков: непрерывная дискретизация признаков (метод дискретизации, для M признаков есть выбор признаков M-1, также требуется сортировка значений признаков, и значением каждой пороговой точки сегментации кандидата является указанное выше отсортированное значение атрибута. Средняя точка последовательные элементы до и после средней пары, что эквивалентно увеличению дискретных признаков). Он поддерживает обработку дискретных признаков и с определенной вероятностью делит недостающие собственные значения на разные узлы.

  • Оптимизация модели: пессимистическая стратегия обрезки деревьев.

  • Потребление памяти: необходимость сортировки собственных значений, работа с памятью, простой OOM.

  • Вычислительная эффективность: N-арное дерево разветвляется с пространством признаков выборки и требует многократного сканирования и сортировки, а время вычислений велико.

2.6 Алгоритм CART

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

По сравнению с ID3 и C4.5 дерево CART несколько упрощено: вместо дерева с несколькими ответвлениями используется бинарное дерево, что повышает эффективность генерации деревьев решений и снижает объем вычислений. А дерево классификации использует коэффициент Джини в качестве количества примеси переменной, что сокращает время, затрачиваемое на большое количество логарифмических операций.

2.6.1 Дерево классификации

Позвольте мне представить дерево классификации на основе CART. Когда CART используется в качестве дерева классификации, атрибуты объектов могут быть непрерывными или дискретными.Стратегия разделения узлов дерева основана на индексе Джини.Далее, индекс Джини будет введен первым.

2.6.1.1 Индекс Джини

Определение: В задаче классификации, предполагая, что существует K классов, вероятность того, что точка выборки принадлежит K-му классу, равна pk, тогда индекс Джини распределения вероятностей равен

Gini(p)=∑k=1Kpk(1−Pk)=1−∑k=1Kpk2Gini(p) = \sum_{k=1}^Kp_k(1-P_k) = 1 - \sum_{k=1}^K{p_k}^2

Для данного выборочного набора D его индекс Джини равен:

Gini(D)=1−∑k=1K(∣CK∣∣D∣ )2Gini(D) = 1 - \sum_{k=1}^K{( \frac{|C_K|}{|D|} \ )}^2

Тогда при условии признака А индекс Джини в сочетании с D составляет, D1 и D2 представляют собой два диапазона, которые делятся в соответствии с определенным значением признака А.

Джини(D,A) = \frac{|D_1|}{|D|} \ Gini(D_i)+ \frac{|D_2|}{|D|} Джини(D_2) \

Индекс Джини Gini представляет собой неопределенность данных, а Gini(D, A) представляет собой неопределенность множества D после разделения признака A = a. Тогда, в отличие от прироста информации, чем меньше индекс Джини, тем примесь Модель низкая, а характеристика около.

2.6.1.2 Генерация дерева классификации

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

2.6.2 Дерево регрессии

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

Процесс выглядит следующим образом: Для любого признака A вычислить по очереди все возможные значения точки разделения, разделить выборочные данные на две части D1 и D2 по этому значению, вычислить соответствующие Loss по MSE и сложить их (вывод дерева регрессии не является категорией, он использует среднее значение или медиану конечного листа для прогнозирования выходного результата.), а затем выбирает значение признака с наименьшими потерями, затем разбивает узлы и повторно делит набор данных соответствующих узлов. , а затем рекурсивно выполняет этот процесс, который называется Can.

min⁡j,s[min⁡C1∑xiеR1(j,s)(yi−c1)2+min⁡C1∑xiеR2(j,s)(yj−c2)2]\min\limits_{j,s}[\min\limits_{C1}\sum_{x_i \in R_1(j,s)}(y_i - c_1)^2 + \min\limits_{C1}\sum_{x_i \in R_2(j,s)}(y_j - c_2)^2 ]

Среди них удобство атмосферы — j, точка сегментации — s, а набор данных разделен на две части, C1 и C2, и мы используем приведенный выше алгоритм для поиска наименьших потерь.

Преимущества и недостатки дерева CART

  • Структура модели: используйте форму двоичного дерева для повышения эффективности сортировки дерева решений.

  • Цели модели: Поддержка деревьев классификации и деревьев регрессии.

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

  • Оптимизация модели: используйте сокращение для практики оптимизации и сокращения на основе сложности затрат.

  • Вычислительные затраты: дерево классификации использует коэффициенты Джини для сокращения сложных операций.

3 Представьтесь

Личное представление: Ду Баокун, создатель федеративного обучения JD.com от 0 до 1, возглавил команду по созданию решения для федеративного обучения JD.com, реализовал супер-крупномасштабное промышленное решение для федеративного обучения в области маркетинга электронной коммерции. , и поддержал сверхкрупномасштабный образец выравнивания конфиденциальности PSI, существует множество моделей, таких как модель безопасного дерева и модель нейронной сети, и моделирование не ограничено В то же время он руководил командой, чтобы реализовать посадку бизнеса стороны, создали новую точку роста бизнеса и принесли значительные экономические выгоды для бизнеса.

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

Категории