Re: Комбинаторика vs теорвер

[arseniiv]

Mihaylo в сообщении #1054703 писал(а):

Таким же образом вы ошибаетесь, когда утверждаете, что формула Хартли выводится из формулы Шеннона. Глупость! Это просто тривиализация формулы.

Это просто игра словами.

[Mihaylo]

Ну если не совсем понятно, что есть "тривиализация формулы", приведу пример.
$\sin ^2 x + \cos ^2 x = 1\quad\quad \quad\quad\quad\quad\quad (1)$
$\sin ^2 (x+y) + \cos ^2 (x+y) = 1\quad \quad \quad (2)$

Обе формулы верны, из тождества (1) выводится тождество (2) и, наоборот, из (2) выводится (1). Никто не будет утверждать, что тождество (1) не работает для суммы углов, а тождество (2) более универсально и общно, т.к. из него можно вывести формулу (1), приняв $y=0$. Переход от (2) к (1) - это есть тривиализация, упрощение, а не вывод.
Абсолютно такая же ситуация в теории информации. Можно рассмотреть $n$ повторений событий и тогда мера Хартли усложнится до меры Шеннона. Можно уйти от повторения событий (математически это подстановка $p=\frac{1}{n}$) и тогда "выводится" мера Хартли.

На самом деле обе меры равнозначны по применимости, т.к. выводятся друг из друга. Хартлиевская мера более проста, понятна и элементарна как и тождество (1).

[arseniiv]

Mihaylo в сообщении #1054855 писал(а):

Ну если не совсем понятно, что есть "тривиализация формулы", приведу пример.

Не, я понял. Это просто подстановка, как и думал. Но выделять отдельно следствия, являющиеся корректными подстановками — по-моему, странно. Они всё равно останутся следствиями.

Mihaylo в сообщении #1054855 писал(а):

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

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

[Mihaylo]

arseniiv писал(а):

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

Ну во всяком случае, как принято говорить в компьютерной науке, эти вещи равнозначны с точностью до константы О(1).

Что касается меры Шеннона, то она лишь асимптотически сходится с мерой Хартли. Почему-то в теории информации принято считать, что мера Шеннона более точна... С некоторых пор я стал считать наоборот, а именно: формула Шеннона является приближенной и справедлива лишь при большом количестве повторений и при вероятностях $p_i$, отдаленных от нуля (не стремящихся к нулю). (При нулевой вероятности - справедлива.) Эти умозаключения - следствие применения формулы Муавра-Стирлинга при выводе меры Шеннона из меры Хартли.

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

[epros]

Mihaylo в сообщении #1054889 писал(а):

Эти умозаключения - следствие применения формулы Муавра-Стирлинга при выводе меры Шеннона из меры Хартли.

Мера Шеннона из меры Хартли не выводится по той же причине, по которой из частотного определения вероятности не выводится Колмогоровское определение вероятности: Первое применимо только к конечным множествам исходов, а второе -- и к бесконечным в том числе.

Я в другой теме уже приводил похожий пример с лампочками, повторю его здесь: Как известно, потребляемая мощность лампочки $P$ в Ваттах связана с её электрическим сопротивлением $R$ в Омах следующей формулой:

$$P=\frac{220^2}{R}.$$

Если сказано, что на складе есть лампочки от 10 до 1000 Ватт мощности, то какое распределение следует считать "равномерным" -- по мощностям или по сопротивлениям? Если бы существовало конечное множество возможных значений мощности (или сопротивления), то ответ можно было бы свести к частотной мере. Но если возможные значения мощностей (или сопротивлений) определяются хотя бы рациональными (не говоря уж о действительных) числами, то однозначного частотного определения "равномерного распределения" не существует.

[arseniiv]

Mihaylo в сообщении #1054889 писал(а):

Ну во всяком случае, как принято говорить в компьютерной науке, эти вещи равнозначны с точностью до константы О(1).

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

Mihaylo в сообщении #1054889 писал(а):

Эти умозаключения - следствие применения формулы Муавра-Стирлинга при выводе меры Шеннона из меры Хартли.

Тогда вам и производную надо назвать менее точной, чем конечные разности. А то пределы какие-то…

Mihaylo в сообщении #1054889 писал(а):

Причина, которая практически вынуждает меня считать формулу Шеннона асимптотической - это существование других мер энтропии <…> которые удобнее выводить, применяя формулу Хартли.

Это тяжело назвать причиной. Из предположения, что есть какие-то другие вещи, которые удобнее выводить не из неё, как-то упорно не хочет ничего следовать про асимптотичность. Что я упускаю?

[Mihaylo]

epros писал(а):

Первое применимо только к конечным множествам исходов, а второе -- и к бесконечным в том числе.

Парирование такое: на практике бесконечность все равно недостижима. Но можно рассматривать предел, чтобы заглянуть в бесконечность... Вообще с моей точки зрения, бесконечность - не проблема. Какая в этом сложность?

epros писал(а):

Я в другой теме уже приводил похожий пример с лампочками, повторю его здесь:

Я нашел ту тему и продолжу обсуждение там. У меня есть ответ на эту задачу.

-- 19.09.2015, 18:04 --

arseniiv писал(а):

Что я упускаю?

Упускаете математическое чутье. Что-то здесь мне кажется не так, это мое ощущение. Истинной мерой энтропии должно быть количество вопросов "да"/"нет" - конечная величина, применимая к задачам с конечными величинами.

[epros]

Mihaylo в сообщении #1054931 писал(а):

на практике бесконечность все равно недостижима. Но можно рассматривать предел, чтобы заглянуть в бесконечность... Вообще с моей точки зрения, бесконечность - не проблема. Какая в этом сложность?

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

А достижимость или недостижимость бесконечности значения не имеет.

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

[Mihaylo]

Хорошо, предлагаю рассмотреть следующие организационные моменты нашей дискуссии:
1. Мы должны осознавать, что нашей дискуссией управляет наше личное самолюбие (мы хотим доказать друг другу, что мы умные и получить удовлетворение от признания точки зрения). Я стараюсь разорвать этот замкнутый круг и направить его на обогащение личного багажа знаний. Тем более, что этот багаж не такой тяжелый, хотя и не пустой. Я с удовольствием послушаю такую обоснованную точку зрения, которая вернет меня на землю.
2. Предлагаю общаться в удовольствие.
3. Разговор следует разделить на несколько ветвей. Меня очень интересует опровержение асимптотичности меры Шеннона. Об этом пишем в настоящей теме. Об аксиоматичности выбора пространства элементарных событий будем писать в "теме, которую я нашел".

Ок?

-- 19.09.2015, 20:27 --

С моей точки зрения вероятность - это не частота событий при числе повторений, стремящемся к бесконечности. Это значит, что такие случаи не имеет практического смысла рассматривать. И точка.
Более того, согласно моей точке зрения, вероятность не определяется через частоту, она всегда определяется через равномерность распределения (как в задаче о лампочках). Равномерность распределения - это есть реализация принципа симметрии. Тут можно добавить, что если переменная $y$ известным образом зависит от $x$, то симметрия максимально применима для переменной $x$, для $y$ принцип симметрии уже нельзя применять, $y$ не симметрично.
Через частоту (частотное распределение) можно определить другую частоту (частотное распределение). С моей точки зрения теорию вероятностей в многих случаях случаях следует называть "теорией частот". Если рассматривать статистику попадания стрелка в мишень, то здесь работает "теория частот", а не теория вероятностей. "Теория частот" - это не глупость, вспомните как формулируются основные определения и законы теории вероятностей - формула сложения и умножения вероятностей, условная вероятность. Там везде частота.

Вот я сделал общий обзор своей теории, меня требуется опустить на землю.

[Евгений Машеров]

Ну, я бы предложил вопрос - у нас есть два передаваемых символа. 0 с вероятностью $\frac 1 {256}$ и 1 с вероятностью $\frac {255} {256}$. Какова информация, приходящаяся на единичный символ?

[arseniiv]

(Оффтоп)

Mihaylo в сообщении #1054931 писал(а):

Упускаете математическое чутье. Что-то здесь мне кажется не так, это мое ощущение.

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

Mihaylo в сообщении #1054970 писал(а):

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

Т. е. до этого вам ничего нового не сказали? Тогда дальше я пас, извините уж.

Mihaylo в сообщении #1054970 писал(а):

Предлагаю общаться в удовольствие.

Хорошее предложение. Для собственного удовольствия покину тему.

[Mihaylo]

Евгений Машеров писал(а):

Ну, я бы предложил вопрос - у нас есть два передаваемых символа. 0 с вероятностью $\frac 1 {256}$ и 1 с вероятностью $\frac {255} {256}$. Какова информация, приходящаяся на единичный символ?

Это несерьезная задача. Пусть есть сообщение из $n$ символов, в котором встречается $\frac{n}{256}$ нулей и $\frac{255n}{256}$ единиц. Задача сформулирована аналогично?
Тогда число вариантов сообщений длины $n$, в котором имеется ровно столько нулей и единиц, равно $\frac{n!}{(\frac{n}{256})!(\frac{255n}{256})!}$
Энтропия равна $H=\log \frac{n!}{(\frac{n}{256})!(\frac{255n}{256})!}$
Энтропия в расчете на один символ
$h=\frac{1}{n}\log \frac{n!}{(\frac{n}{256})!(\frac{255n}{256})!}$

Примем $n=256$, тогда $h=\frac{1}{256}\log 256 = \frac{8}{256}=\frac{1}{32}=0,03125$. Основание логарифма - двойка.
Формула Шеннона дает результат $h=-\frac{1}{256}\log(\frac{1}{256})-\frac{255}{256}\log(\frac{255}{256})\approx0,0368$.
Уверяю, оба метода будут всегда давать близкие результаты при любых $n$.

Я выдвигаю гипотезу, что формула Шеннона дает приближенный результат.

[Евгений Машеров]

Примем иное n, и получим другой результат?

[Mihaylo]

Давайте посчитаем для $n=1024$.
$h=\frac{1}{1024}\log \frac{1024\cdot 1023\cdot 1022\cdot 1021}{24} \approx 0,0345$.

С увеличением $n$ будем приближаться к шенноновскому результату.

Гипотеза: фактически энтропия зависит от количества данных $n$. Зависимость несильная, но она есть.

[Евгений Машеров]

Если информация зависит от количества данных, то она неаддитивна. Рассматривая количество информации в последовательности, мы вынуждены будем узнавать, сколько символов, которые мы не видели и которые нас не интересуют, она ещё содержит.
А задача - ну, давайте посерьёзнее. После нуля в 70% случаев следует единица, иначе ноль. После единицы в 80% случаев следует ноль, иначе единица. Найти энтропию символа.