An abstract example for "The Optimality of Naive Bayes". Part 1.

Here I will try to provide a small illustration for Harry Zhang's article "The Optimality of Naive Bayes". This example will explain how Naive Bayes classifier can be optimal in case of dependencies between attributes. If you need more background about the subject read the article first.

Let's consider a document classification problem, for simplicity we will search for only two words in each document: W1 and W2. We will use boolean values (T and F) to encode possible variable values. W1=T means some document contains W1, W1=F means otherwise. Each document can be classified into 2 categories: more important (C=T) and less important (C=F).

Let's suppose we have probabilities for Naive Bayes classifier as in tables below.

Category probabilities

	C=T	C=F
P	0.6	0.4

Conditional probabilities for W1:

	W1=T	W1=F
C=T	0.1	0.9
C=F	0.3	0.7

Conditional probabilities for W2:

	W2=T	W2=F
C=T	0.3	0.7
C=F	0.4	0.6

Now, let's calculate scores for NB (Naive Bayes) classifier. For example, what category will NB classifier select for document with W1=T, W2=T? According to Bayes rule and independence assumption we can calculate:

$P(C=T| W1=T, W2=T)=\frac{P(W1=T|C=T)\times P(W2=T|C=T)}{P(W1=T, W2=T)}\times P(C=T)$

By using values from tables above and removing denominator, because it's the same for both categories we get:

$Score(C=T| W1=T, W2=T)=0.1\times 0.3\times 0.6=0.018$

similarly for C=F:

$Score(C=F| W1=T, W2=T)=0.3\times 0.4\times 0.4=0.048$

So, NB classifier tells us to select C=F category.

Now, let's assume that our attribute independence assumption is wrong and W2 attribute depends on W1 and dependency can be described by following conditional probability table:

C	W1	W2=T	W2=F
C=T	W1=T	0.4	0.6
C=T	W1=F	0.3	0.7
C=F	W1=T	0.5	0.5
C=F	W1=F	0.4	0.6

We can calculate joint distribution according to Bayes network rule (see details on wiki):

C	W1	W2	P(C,W1,W2)
T	T	T	0.024
T	T	F	0.036
T	F	T	0.162
T	F	F	0.378
F	T	T	0.06
F	T	F	0.06
F	F	T	0.112
F	F	F	0.168

First values was calculated as:

$P(W1=T,W2=T,C=T)=P(C=T)\times P(W1=T|C=T)\times P(W2=T|W1=T,C=T)$
$P(W1=T,W2=T,C=T)=0.6\times 0.1\times 0.4=0.024$

Now let's calculate several conditional probabilities taking into account local dependency:

	P
P(W2=T|W1,C=T)	0.31
P(W2=F|W1,C=T)	0.69
P(W2=T|W1,C=F)	0.43
P(W2=F|W1,C=F)	0.57

First value is calculated according to Bayes network rule as follows:

$P(W2=T|W1, C=T) = \frac{P(W1, W2=T, C=T)}{P(W1, W2, C=T)}=\frac{P(W1=T,W2=T,C=T)+P(W1=F,W2=T,C=T)}{P(W1=T,W2=T,C=T)+P(W1=T,W2=F,C=T)+P(W1=F,W2=T,C=T)+P(W1=F,W2=F,C=T)}$

$\frac{0.024+0.162}{0.024+0.036+0.162+0.378}=\frac{0.186}{0.6}=0.31$

Then ddr values can be calculated as follows:

$ddr\left(T\right)=\frac{dd+\left(T\right)}{dd-\left(T\right)}=\frac{P(W2=T|W1,C=T)}{P(W2=T|C=T)}\times \frac{P(W2=T|C=F)}{P(W2=T|W1,C=F)}$

$ddr\left(T\right)=\frac{0.31}{0.3}\times \frac{0.4}{0.43}\approx 0.961$

Similarly for ddr(F):

$ddr\left(F\right)=\frac{0.69}{0.7}\times \frac{0.6}{0.57}\approx 1.04$

Both ddr(T) and ddr(F) are close to 1. So, we can conclude, due to Harry's article, that local dependency distributed evenly in both categories and doesn't change classifier decision. Also, it means that NB classifier is optimal solution for the problem.
In the next part of this post we will make sure of optimality of NB classifier and consider contr-example where NB classifier will not be optimal.

Особенности применения наивного байесовского классификатора

Сокращенный и переработанный перевод статьи Harry Zhang. 

Наивный байесовский классификатор один из наиболее эффективных алгоритмов машинного обучения и data mining. Его неплохие результаты в задачах классификации удивительны, поскольку предположение об условной независимости, на котором он основан, редко встречается в реальных условиях. Отсюда возникает вопрос: какова истинная причина успехов алгоритма в задачах классификации?

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

Введение

Как известно, в задаче классификации обучающий пример E представляется в виде кортежа значений атрибутов (x₁, x₂, ··· , x_n), где x_i является значением атрибута X_i. Пусть C представляет классифицируемую переменную, а c - конкретное значение C. Далее будем предполагать, что имеется только 2 класса: + (положительный класс) и - (отрицательный класс).

Классификатор - это функция, которая присваивает метку класса некоторому кортежу атрибутов. С точки зрения теории вероятностей, в соответствии с правилом Байеса, вероятность принадлежности примера E = (x₁, x₂, ··· , x_n) классу c определяется формулой:

Пример E классифицируется в положительный класс тогда и только тогда, когда

при этом функция f_b(E) называется байесовским классификатором.

Используя предположение о независимости атрибутов при данном значении c, получаем

 и итоговая формула для классификатора будет выглядеть так:

 Функция f_nb(E) называется наивным байесовским классификатором. На рисунке ниже приведена схема наивного байесовского классификатора. Узел каждого атрибута не имеет родителей за исключением узла класса.

Такой граф является простейшей байесовской сетью, в которой все атрибуты независимы для данного значения переменной класса. Это называется условной независимостью. Очевидно, что такая независимость редко встречается в реальной жизни. Наиболее подходящий способ обойти это ограничение - расширить структуру графа для представления связей между узлами атрибутов. Назовем дополненным наивным байесовским классификатором (augmented naive Bayes - ANB) расширенный наивный классификатор Байеса, в котором существуют связи между узлами-атрибутами. На рисунке ниже представлен пример ANB    

 

Совместное распределение вероятностей для этого графа может быть описано формулой:

где pa(x_i) обозначает значения родительских узлов X_i(здесь и далее pa(x_i) не включает узел C - прим. перев.). Таким образом, ANB является специальной формой байесовской сети, в которой нет выделенного узла, представляющего классифицируемую переменную.

Объяснение эффективности наивного байесовского классификатора

Определение 1. Два классификатора f₁ и f₂ называются равными для данного примера E, если  f₁(E) ≥ 0, тогда и только тогда, когда f₂(E) ≥ 0. Обозначим это как f₁(E)  = f₂(E). Если для каждого примера из набора выполняется f₁(E) = f₂(E), будем называть f₁ и f₂ равными и обозначать это как f₁ = f₂.

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

Рассмотрим некоторый ANB граф G с двумя классами {+, -}, как было указано выше зависимости между узлами графа представлены дугами. Для каждого узла влияние ее родителей определяется соответствующей условной вероятностью. Назовем локальной зависимостью узла зависимость между им и его родителями. Как можно измерить локальную зависимость узла для каждого класса? Естественно, отношением условных вероятностей узла с учетом и без учета значений родительских узлов. Это отношение покажет насколько сильно родители влияют на  узел в каждом классе.

Определение 2. Для узла X в ANB графе G дериват локальной зависимости X в классах + и - определяется как:

dd⁺_G(x|pa(x)) отражает силу локальной зависимости узла X в классе +. Аналогично для dd^-_G(x|pa(x)).

Подведем промежуточный итог:

1. Когда узел X не имеет родителей, дериваты обоих классов равны 1.
2. Когда дериват dd⁺_G(x|pa(x)) ≥ 1, локальная зависимость X в классе + поддерживает решение в пользу класса +. В противном случае - в пользу класса -. Аналогично когда дериват класса - больше 1, локальная зависимость X поддерживает решение в пользу класса -, в противном случае - в пользу класса +.

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

Определение 3.  Для узла X ANB графа G отношением дериватов локальной зависимости называется следующая величина: 

Указанное соотношение измеряет влияние локальной зависимости узла X на выбор класса.  Справедливы следующие соотношения:

1. Если X не имеет родительских узлов ddr_G(x)=1
2. Если dd⁺_G(x|pa(x)) = dd^-_G(x|pa(x)), то ddr_G(x)=1. Это означает, что локальные зависимости X распределены в обоих классах равномерно. Таким образом, зависимости не влияют на классификацию, насколько бы сильными они ни были.
3. Если  ddr_G(x) > 1, то поддержка оказываемая локальной зависимостью в классе + сильнее, чем в классе -. Значение меньше 1 означает противоположное. 

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

Теорема 1. Для данного ANB графа G и соответствующего ему наивного байесовского графа G_nb (полученного из G путем отбрасывания дуг между узлами атрибутов) и соответствующих им классификаторов f_b и f_nb для данного примера E = (x₁, x₂, ··· , x_n) выполняется следующее соотношение:

где П ⁿ  _i=1 ddr_G(x_i) называется коэффициентом распределения зависимости и обозначается как DF_G(E).

Из теоремы следует, что именно коэффициент распределения зависимости определяет разницу между ANB и соответствующим NB-классификатором. Далее, видно, что коэффициент является произведением отношений дериватов локальных зависимостей всех атрибутных узлов. Поэтому он отражает общее распределение зависимости. Например, когда DF_G(E)=1, G будет классифицировать E как и G_nb. На самом деле, не обязательно даже требовать выполнения DF_G(E)=1, чтобы получить равенство классификаторов. См. теорему ниже.

Теорема 2. Для данного примера E = (x₁, x₂, ··· , x_n), ANB граф G равен (определение равенства см. в начале статьи) соответствующему графу G_nb тогда и только тогда, когда  f_b(E) ≥ 1, DF_G(E) ≤ f_b(E) или f_b(E) < 1, DF_G(E) > f_b(E).

Итак, мы получаем следующие результаты:
1. Когда DF_G(E)=1, зависимости  в ANB графе G не имеют влияния на решение классификации. Всего существует три причины для DF_G(E)=1:

• отсутствие зависимости между атрибутами
• равенство ddr_G(x)=1 для всех атрибутов, что означает равномерное распределение локальных зависимостей в обоих классах
• влияние, которое распространяют некоторые локальные зависимости поддерживая класс + для примера E,  нивелируется влиянием других локальных зависимостей, поддерживающих класс -.

2. Равенство f_b(E) = f_nb(E) не требует, чтобы  DF_G(E)=1. Точное условие дается в Теореме 2.
3. Зависимости в ANB графе меняет решение классификации по сравнению с наивным классификатором, только в случае нарушения условий Теоремы 2.

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

Иллюстрация различных уровней изоляции транзакций SQL Server

Как известно SQL Server поддерживает 5 уровней изоляции транзакций:

• READ UNCOMMITTED
• READ COMMITTED
• REPEATABLE READ
• SNAPSHOT
• SERIALIZABLE

По умолчанию используется READ COMMITTED, а несколько особняком стоит SNAPSHOT.

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

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

Создадим таблицу

CREATE TABLE [dbo].[Transac](

[fid] [int] IDENTITY(1,1) NOT NULL,

[fvalue] [int] NOT NULL

) 

Создадим первичный ключ по полю fid и добавим в нее несколько записей

INSERT INTO [dbo].[Transac]([fvalue])

VALUES (1),(2),(3)

Пример 1: Чтение против обновления

Транзакция 1	Транзакция 2
SET TRANSACTION ISOLATION LEVEL READ COMMITTED; GO begin tran UPDATE [dbo].[Transac] set fvalue = 10 where fid=1 WAITFOR DELAY '00:00:10' commit tran	SET TRANSACTION ISOLATION LEVEL READ COMMITTED; GO begin tran SELECT * FROM [dbo].[Transac] where fid between 1 and 2 commit tran

Если запустить сначала транзакцию 1 и затем транзакцию 2, то выполнение второй транзакции будет приостановлено. Это справедливо не только для использованного в примере уровня READ COMMITTED, но и для более высоких уровней REPEATABLE READ и SERIALIZABLE. Следует заметить, что обратное действие (для его реализации придется перенести конструкцию WAITFOR в транзакцию 2 и выполнить ее первой) не приводит к видимой задержке, поскольку блокировка чтения будет снята сразу после получения данных:

Транзакция 1	Транзакция 2
SET TRANSACTION ISOLATION LEVEL READ COMMITTED; GO begin tran UPDATE [dbo].[Transac] set fvalue = 10 where fid=1 commit tran	SET TRANSACTION ISOLATION LEVEL READ COMMITTED; GO begin tran SELECT * FROM [dbo].[Transac] where fid between 1 and 2 WAITFOR DELAY '00:00:10' commit tran

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

1. Использование версионирования строк
2. Отключение разделяемой блокировки (shared lock) при выполнении запроса чтения

Для включения поддержки версий строк нужно выполнить следующую команду:

ALTER DATABASE <databasename> SET READ_COMMITTED_SNAPSHOT ON

После этого поведение транзакций уровня READ COMMITTED будет изменено: вместо ожидания последней версии данных транзакция будет получать версию данных актуальную на момент выполнения и приведенный выше пример сможет выполниться без блокирования чтения.
Второй подход предполагает прямой отказ от использования shared locks при выполнени запроса на чтение. Добиться этого можно 2 спсобами:

1. Использовать хинт NO LOCK
2. Переключить уровень транзакции чтения на READ UNCOMMITTED

В первом случае запрос примет вид:

SELECT * FROM [dbo].[Transac] WITH (NOLOCK)
where fid between 1 and 2

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

Пример 2: Повторяющееся чтение с уровнем REPEATABLE READ

Добавим новое поле fmax в нашу таблицу и не забудем создать первичный ключ по полю fid

CREATE TABLE [dbo].[Transac](
 [fid] [int] IDENTITY(1,1) NOT NULL,
 [fvalue] [int] NOT NULL,
 [fmax] [int]
)

Поле fmax будет отмечать записи с наибольшим значением поля fvalue. Заполним таблицу значениями:

INSERT INTO [dbo].[Transac]([fvalue], [fmax])
VALUES (1,0),(2,0),(3,1)

Рассмотрим пример, когда мы хотим сначала изменить значение поля fvalue, а затем пересчитать значение поля fmax:

Транзакция 1	Транзакция 2
SET TRANSACTION ISOLATION LEVEL READ COMMITTED; GO begin tran declare @max as int UPDATE [dbo].[Transac] SET fvalue = 10 where fid=1 SELECT @max=MAX(fvalue) from [dbo].Transac WAITFOR DELAY '00:00:10' UPDATE [dbo].[Transac] SET fmax = 0 UPDATE [dbo].[Transac] SET fmax = 1 where fvalue=@max commit tran	SET TRANSACTION ISOLATION LEVEL READ COMMITTED; GO begin tran declare @max as int UPDATE [dbo].[Transac] SET fvalue = 15 where fid=2 SELECT @max=MAX(fvalue) from [dbo].Transac WAITFOR DELAY '00:00:10' UPDATE [dbo].[Transac] SET fmax = 0 UPDATE [dbo].[Transac] SET fmax = 1 where fvalue=@max commit tran

Последовательное выполнение этого примера приведет к deadlock, поскольку каждая из транзакций успеет внести изменение в таблицу и попытается выполнить операцию в режиме READ COMMITTED, которая не может быть завершена из-за внесенных изменений другой транзакцией.
Переключим транзакции в режим REPEATABLE READ:

SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;

В данном режиме SQL Server предотвращает изменение данных конкурирующими транзакциями. В итоге, транзакция, выполняющаяся второй, не сможет внести изменения до завершения транзакции, выполняющейся первой и данные будут корректно посчитаны.
Следует отметить, что, если при одновременном выполнении каждая из транзакций выполнит только первую команду UPDATE, все равно произойдет deadlock, поскольку инструкция SELECT не сможет наложить блокировку на изменяемые записи.

Пример 3: Фантомное чтение с уровнем SERIALIZABLE

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

Транзакция 1	Транзакция 2
SET TRANSACTION ISOLATION LEVEL READ COMMITTED; GO begin tran declare @max as int SELECT @max=MAX(fvalue)FROM [dbo].[Transac] WAITFOR DELAY '00:00:10' INSERT INTO [dbo].[Transac] (fvalue) VALUES (@max+1) commit tran	SET TRANSACTION ISOLATION LEVEL READ COMMITTED; GO begin tran declare @max as int SELECT @max=MAX(fvalue)FROM [dbo].[Transac] WAITFOR DELAY '00:00:10' INSERT INTO [dbo].[Transac] (fvalue) VALUES (@max+1) commit tran

При совеместном выполнении этих транзакций и первоначальном составе данных в таблице мы получим такой результат:

fid	fvalue
1	1
2	2
3	3
4	4
5	4

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

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

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

Особенности использования ADFS с клиентами, не поддерживающими SNI

Недавно при тестировании развернутой конфигурации ADFS столкнулись с проблемой подключения к ADFS 3.0 с использованием Internet Explorer 8 под управлением Windows XP. В браузере получаем вот такое сообщение

При использовании IE 8 под управлением Windows 7 проблема не повторилась, так же как и для Google Chrome.

Первая мысль состояла в том, что в Windows XP отсутствует поддержка протоколов TLS 1.1 и 1.2, а использование TLS 1.0 может быть запрещено на сервере. Быстрая проверка, однако, опровергла это предположение: отключив использование TLS 1.1 и 1.2, Internet Explorer под Windows 7 переключился на использование TLS 1.0. Проверка настроек SChannel в реестре на сервере подтвердила: используется конфигурация по умолчанию, в которой TLS 1.0 разрешен.

Очевидно, требовалось более глубокое исследование проблемы. Первое, что нужно было сделать - проверить на каком шаге прерывается процесс SSL handshake. И тут ждал сюрприз, дело в том, что как такового процесса "рукопожатия" не было. Клиент отправлял перечень поддерживаемых шифров (cipher suite), но сервер в ответ просто разрывал соединение.

Погуглив, стало понятно, что всё это в точности совпадает с симптомами отсутствия поддержки расширения Server Name Indication (SNI) протокола TLS (подробнее можно посмотреть тут). Предлагаемый вариант решения предусматривал назначение сертификата на фиктивный IP адрес 0.0.0.0, что позволяло выполнить сопоставление с запросом, не содержащим имени сервера (а именно такие запросы отправлял IE 8 под Windows XP):

Однако, даже реализация этого решения не позволила добиться корректной работы в IE 8.

Сертификат, созданный  при развертывании ADFS, по каким-то причинам не хотел работать в таком режиме. Проблему решило создание нового сертификата и назначение его на адрес 0.0.0.0 и все используемые имена ADFS при помощи следующих команд:

 http add sslcert ipport=0.0.0.0:443 certhash=<cert hash> appid={5d89a20c-beab-4389-9447-324788eb944a} certstorename=MY sslctlstorename=AdfsTrustedDevices  
 http add sslcert hostnameport=<adfs hostname>:443 certhash=‎<cert hash> appid={5d89a20c-beab-4389-9447-324788eb944a} certstorename=MY sslctlstorename=AdfsTrustedDevices  

После этого приложение, наконец-то, заработало.

При исследовании очень помогла статья Kaushal Kumar Panday с пошаговым исследованием проблем SSL. За что автору отдельное спасибо.