In this third part, we will discuss Machine Learning, specifically the prediction task in the context of information theory.

The concept of Mutual Information (MI) is related to the prediction task. In fact, the prediction task can be viewed as the problem of extracting information about the signal from the factors. Some part of the information about the signal is contained in the factors. If you write a function that calculates a value close to the signal based on the factors, then this will demonstrate that you have been able to extract MI between the signal and the factors.

In Part 1, we became familiar with the concept of entropy.

In this part, we will delve into the concept of Mutual Information, which opens doors to error-resistant coding, compression algorithms, and offers a fresh perspective on regression and Machine Learning tasks.

It is an essential component that will pave the way, in the next section, for tackling Machine Learning problems as tasks of extracting mutual information between features and the predicted variable.

Here, there will be three interesting and crucial visualizations.

The first one will visualize entropy for two random variables and their mutual information.
The second one will shed light on the very concept of dependency between two random variables, emphasizing that zero correlation does not imply independence.
The third one will demonstrate that the bandwidth of an information channel has a straightforward geometric interpretation through the convexity measure of the entropy function.

In the meantime, we will prove a simplified version of the Shannon-Hartley theorem regarding the maximum bandwidth of a noisy channel. Let's dive in!

I've long wanted to create educational materials on the topic of Information Theory + Machine Learning. I found some old drafts and decided to polish them up here, on Habr.

Information Theory and Machine Learning seem to me like an interesting pair of fields, the deep connection between which is often unknown to ML engineers, and whose synergy has not yet been fully revealed.

Let's start with basic concepts like Entropy, Information in a message, Mutual Information, and channel capacity. Next, there will be materials on the similarity between tasks of maximizing Mutual Information and minimizing Loss in regression problems. Then there will be a section on Information Geometry: Fisher metric, geodesics, gradient methods, and their connection to Gaussian processes (moving along the gradient using SGD is moving along the geodesic with noise).

It's also necessary to touch upon AIC, Information Bottleneck, and discuss how information flows in neural networks – Mutual Information between layers (Information Theory of Deep Learning, Naftali Tishby), and much more. It's not certain that I'll be able to cover everything listed, but I'll try to get started.

This is a translated and adopted article I wrote for the Aha'22 (30 May 2022) conference. It describes an approach to a marketplace prices optimisation. Here I've outlined some important definitions and tried to define the scopes and roles of ML, algorithms, and humans in optimal pricing. Although the article covers rather basic things, still, you can find out some new formulas and ideas, because these basics are somewhat "well-known only in a very closed clubs", and besides, the real gem found here is the detailed recipe for ML engineers how to build optimal pricing systems.

Понятие Mutual Information (MI) связано с задачей прогноза. Собственно, задачу прогноза можно рассматривать как задачу извлечения информации о сигнале из факторов. Какая-то часть информации о сигнале содержится в факторах. И если вы напишите функцию, которая по факторам вычисляет число близкое к сигналу, то это и будет демонстрацией того, что вы смогли извлечь MI между сигналом и факторами.

В этой части я рассказываю про Взаимную Информацию – концепцию, которая открывает двери в помехоустойчивое кодирование, алгоритмы сжатия, а также даёт новый взгляд на задачи регрессии и Machine Learning.

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

Здесь будет три важных картинки.

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

Между делом мы докажем упрощённый вариант теоремы Шаннона-Хартли о максимальной пропускной способности канала с шумом. Погнали!

Теория Информации и Machine Learning мне видятся как интересная пара областей, глубокая связь которых часто неизвестна ML инженерам, и синергия которых раскрыта ещё не в полной мере.

Начнём с базовых понятий Энтропии, Информации в сообщении, Mutual Information, пропускной способности канала. Далее будут материалы про схожесть задач максимизации Mutual Information и минимизации Loss-а в регрессионных задачах. Затем будет часть про метрику Фишера, геодезические и градиентные методы, и их связь с гауссовскими процессами.

Суффиксное дерево (Suffix Tree, ST) – это структура данных, которая позволяет "проиндексировать" строку за линейное время от её длины, чтобы потом быстро находить подстроки (за время О(длина искомой подстроки)).

Тема построения Suffix Tree и его применения хорошо раскрыта в Интернет (википедия, статья на хабр про алгоритм Вейнера, язык Си, и статья на хабр про алгоритм Укконена). Но всегда есть соблазн поучаствовать в соревновании "написать проще и яснее", хотя шансов мало. Тем не менее, рискну.

Несмотря на сложность, алгоритм построения ST умещается в 35 строк на python (см. ниже метод _build_tree). Их буквально можно выучить и воспроизводить по памяти как некое произведение искусства, как воплощенный в набор символов труд человеческой мысли, причём не одного человека, и первые из них точно гении. :) Есть соблазн, всматриваясь в код, прикоснуться к великому и чему-то научиться.

Спорить плохо, но раз уж всё равно все спорят, то почему бы не делать это конструктивно и продуктивно :)

Лайфхак как успешно убеждать датасайентистов по результатам A/B тестирования. Работают такие аргументы:

Кривая эластичности спроса по цене – это то, как продажи зависят от цены.Чем меньше цена, тем больше продаж и наоборот.

В этой статье рассказывается про ML методы получения кривых спроса сразу для сотен тысяч товаров (нейросети, pyTorch), а также как, имея кривые спроса, решать бизнес задачу про баланс оборота и прибыли – в этом нам поможет метод множителей Лагранжа. Что первично – ограничение на прибыль или множитель Лагранжа? Как инженерам объяснить, что такое kvi-товары и товары-герои? Это и многое другое