python и визуализация деревьев

Для примера, есть вот такой маленький массив:

data = [6, 2, 6, 4, 6, 6, 6, 6, 4, 4]

Каждый элемент этого массива — это указатель на родителя. То есть, у нулевого элемента родитель шестой, у первого — второй, у второго — снова шестой и так далее. В принципе, это дерево невелико, поэтому можно поднапрячься, построить его в голове и попытаться осознать, но если элементов будет чуть больше, а как-то визуализировать их всё же захочется, можно воспользоваться Graphviz (в MacOS ставится через Homebrew) и питоновой обёрткой для него — pydot (pip install pydot).

Вот так просто массив можно превратить в картинку:


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

В результате получается вот такое деревце:


python переменная и указатель

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


Что выведет следующий кусок кода?

a = b = 0.1
a = 1
b = 2
print(f'a = {a}')
print(f'b = {b}')

Довольно предсказуемо:

a = 1
b = 2



А теперь вместо числа,  присвоим list и обновим его, добавив некое значение:

a = b = [1, 2]
a.append(3)
b.append(4)
print(f'a = {a}')
print(f'b = {b}')

Что будет на выходе? Я бы подумал, что:

a = [1, 2, 3]
b = [1, 2, 4]

Однако, сюрприз, на выходе получится:

a = [1, 2, 3, 4]
b = [1, 2, 3, 4]

Потому как в этом случае, хотя это и не совсем очевидно, a и b — это указатели на объект!

и снова Байес

Есть некое заболевание, про которое известно, что от него страдает 3% популяции. Существует тест, который с точностью 80% определяет, имеет человек это заболевание или нет, при этом тест в 13% случаев срабатывает ложно положительно, то есть, определяет заболевание у того, у кого его на самом деле нет.

Если тест показал, что у некоего человека есть заболевание, насколько вероятно, что этот человек реально болен?

Collapse )

Отношение правдоподобий

Правдоподобием можно использовать для сравнения возможных значений параметра 𝛑. Например, студент случайным образом отвечал на вопросы теста, подразумевающие ответ "да" или "нет", и оказалось, что у него 8 правильных ответов из 10. Если он отвечал случайно, то параметр 𝛑 должен был оказаться равен 0.5, однако данные говорят о том, что он равен 0.8. Насколько более вероятно, что студент отвечал неслучайно, то есть попал в точку в 80% случаев, по сравнению с альтернативной гипотезой, что студен всё-таки отвечал на вопросы случайно?

Для того, чтобы провести такое сравнение, можно посчитать отношение правдоподобий:



На графике это выглядит так:


То есть, конкретно эти данные говорят о том, что гипотеза о неслучайном 80% попаданий в 6.87 раз более вероятна гипотезы случайного выбора.

Collapse )

Правдоподобие и размер выборки

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

На графике ниже отображены кривые для выборок 5 из 10, 50 из 100 и 500 из 1000:



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

Эта иллюстрация показывает, что с ростом размера выборки данные всё плотнее распределяются в районе значения истинной вероятности (в этом случае оно равно 0.5). То есть, мы получаем всё более точное доказательство, что максимальное правдоподобие достигается при истинной вероятности равной 0.5.

Комбинирование правдоподобий

Интересная особенность правдоподобий состоит в том, что их можно комбинировать. Представим, что два студента пришли на тестирование, состоящее из десяти закрытых вопросов, то есть, вопросов, подразумевающих ответ "да" или "нет". Студенты не знают ответа ни на один вопрос и случайным образом расставляют галочки. В результате, один угадывает 4 ответа, второй — 8.

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

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


Вот так выглядят эти кривые правдоподобий:


Как видите, в обоих случаях, при вычислении правдоподобия "12 значений из 20" и при комбинировании, значения параметра 𝝿 оказываются одинаковыми.

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

Вероятность и правдоподобие

Хотя вероятность и правдоподобие тесно связаны, смысл их различен.

При вычислении вероятности, параметр истинной вероятности (англ. true probability) зафиксирован. То есть, у нас есть оценка значения истинной вероятности, основываясь на которой, можно вычислить вероятность отдельных исходов. Например, предполагая, что монета правильная, мы принимаем истинную вероятность за 0.5 и пытаемся оценить вероятность каждого исхода при десяти испытаниях (0 решек и 10 орлов, 1 решка и 9 орлов и т.д.). На выходе получается функция вероятности (англ. probability mass function).

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

k-armed бандит и 𝜺-greedy алгоритм. Оптимистичная инициализация переменной.



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

Для методов с переменным значением константы 1/n, как в этой статье, влияние bias исчезает в тот момент, когда каждое действие оказалось выбрано хотя бы один раз. В том же случае, когда коэффициент 𝛼 — константа, bias присутствует постоянно, хотя его влияние и снижается с течением времени.

Оказывается, правильная инициализация Q может сподвигнуть даже жадный алгоритм заняться исследованием. Так, если переменную Q инициализировать не нулями, как это делалось в предыдущей статье, а, например, прибавить к каждому значению 5, то при любом действии на начальном этапе награда оказывается значительно ниже изначального оценочного ожидания. В результате все варианты действий будут опробованы несколько раз прежде, чем начнётся схождение. То есть, даже в случае использования жадного алгоритма будет производиться исследование.

Для примера, сравним два варианта. В первом оптимистичном переменная Q при инициализации увеличена на 5, а параметр 𝜺 равен нулю, то есть применён жадный алгоритм. Во втором — Q инициализирован нулями, а параметр 𝜺 равен 0.1. В обоих случаях 𝛼 = 0.1


Collapse )

k-armed бандит и 𝜺-greedy алгоритм. Нестационарная проблема.


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

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

q_star[problem] += np.random.normal(0, 0.01, k)



В этом случае всё становится, мягко говоря, очень печально.




Collapse )

k-armed бандит и 𝜺-greedy алгоритм


При решении проблемы k-рукого бандита на каждом временном отрезке t есть два варианта действий: использование текущего знания о максимальном вознаграждении (exploiting) и исследование (exploring).

Если принять действие на каждом временном отрезке t за A_t, а соответствующую награду за R_t, то значение ожидаемой награды будет зависеть от выбранного действия a:









Если применять жадный (greedy) алгоритм, то каждое действие окажется использованием текущего знания о максимальном вознаграждении. То есть, если у нас есть сведения только об одном вознаграждении на определённом шаге, то нет никаких гарантий, что именно его значение максимально. Так что хорошо бы, хотя бы в некоторых случаях, производить исследование. Для этого введём параметр 𝜺, который будет отображать вероятность того, что на этом шаге будет произведено исследование. Такой подход называется 𝜺-жадным (𝜺-greedy).
Collapse )