Pull to refresh

Comments 60

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

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


Что такое чувствительность

Если я вас правильно понял, то немного не совсем так. Не от входа корень считается, потому что например функция-константа имеет размер входа n, но чувствительность ноль.
Правильная формулировка такая: чувствительность не меньше корня из deg(f) (степени функции).
А что такое степень надо говорить отдельно.
Любую булеву функцию можно представить в виде полинома. Я не уверен, что прав, но вроде бы имеется в виду Полином Жегалкина. Собственно deg(f), т.е. степень функции — это степень этого полинома, т.е. максимальная степень его слагаемых.

Вообще парень доказал штуку, которая довольно просто формулируется в терминах графов. В n-мерном кубическом графе любой подграф степени 2^(n-1)+1 (т.е. имеющий больше половины вершин исходного графа) имеет вершину степени не меньше чем sqrt(n).

Правда я понятия не имею, как из этой теоремы следует теорема чувствительности, но вроде как это известный переход, на который ссылается автор. Только разобраться надо.
Нашёл статью 1992-го года, в которой описывается эквивалентность утверждений про кубический граф и про чувствительность функции www.sciencedirect.com/science/article/pii/0097316592900608
Там ещё пара страниц доказательства, которые я пожалуй пока не осилю)
Это одна из тех удивительных вещей, что делают нашу жизнь прекрасной…
Обьяснение в виде твита — шикарное.
Это как раз тот момент, когда специалист с профильным университетским дипломом может спокойно признать, что оно выглядит как иностранный язык.
Ну, чтобы понять суть статьи в самом приближённом виде, надо самому попробовать закодить куб и натянуть на его поверхности текстуры скайбокса. Я попробовал. Узнал много нового.

проще говоря — удалось доказать математическую зависимость "меры чуствительности" относительно прочих мер (т.е. "не меньше чем корень" и т.д.) и теперь у математиков будет на одну лекцию больше рассказа для студентов (заодно и мотивация :) "вот видите — как просто, вы тоже можете так, если будете больше думать")

гипотеза «чувствительности» ставила в тупик многих выдающихся специалистов по информатике, но её новое доказательство оказалось настолько простым, что один исследователь смог свести его к единственному твиту
Чтобы «статья» была подлиннее, давайте повторим заголовок.
Чтобы «статья» была подлиннее, давайте повторим заголовок.
  1. Эта статья могла бы быть длиннее, если бы повторяла заголовок — писал в комментариях к этой статье пользователь GeMir с хабрахабра в интернете


  2. В 2019 году GeMir, сейчас находящийся на хабрахабре, предположил, что статья могла бы быть длиннее, если бы повторяла заголовок. «Этот вопрос, я бы сказал, был выдающимся в области написания статей», — сказал GeMir.


  3. «Люди писали длинные, сложные статьи, пытаясь достичь совсем небольшого удлинения», — сказал GeMir с хабрахабра.


  4. Чтобы «статья» была подлиннее, давайте повторим заголовок. — сказал GeMir



Источник
  1. «Эта гипотеза была одной из самых раздражающих и позорных открытых задач во всей комбинаторике и теоретической информатике», — писал в своём блоге Скот Ааронсон из Техасского университета в Остине.
  2. В 1992 году Ноам Нисан из Еврейского университета в Иерусалиме и Марио Сегеды, сейчас работающий в университете Рутгерса, предположили, что чувствительность всё же укладывается в эту платформу. Но никто не мог этого доказать. «Этот вопрос, я бы сказал, был выдающимся в области изучения булевых функций», — сказал Серведио.
  3. «Люди писали длинные, сложные работы, пытаясь достичь совсем небольшого прогресса», — сказал Райан О’Доннел из университета Карнеги-Меллон.
  4. «Этот вопрос 30 лет не давал людям спать спокойно», — сказал Ааронсон.


PS: На самом деле это просто жутко бесящий "западный" науч-поп стиль.


Я хотел сказать что такой стиль написания научно-популярных статей очень част на западе.


"Часто можно встретить научно популярную статью или фильм которая повторяет одно и то же несколько раз" — сказал я сегодня.

Мне вот что интересно, если не повторяться, то читатели не поймут или за буковки не заплатят?
А мне вот этот кусок понравился:
Эта гипотеза связана с булевыми функциями — правилами преобразования строк входящих битов (нулей и единиц) в единственный бит. Одно такое правило выдаёт 1, когда все входящие биты равны 1, и 0 в другом случае; другое правило выдаёт 0, если в строке содержится чётное количество единиц, и 1 в другом случае. Каждая компьютерная схема является некоей комбинацией булевых функций, что делает их «строительным материалом всего, что делается в информатике», — сказал Рокко Серведио из Колумбийского университета.

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

По-моему, вполне нормально:


Эта гипотеза связана с булевыми функциями — правилами преобразования строк входящих битов (нулей и единиц) в единственный бит.

^ Гипотеза, о которой будут говорить — про хэш-функции (так, MD5 хэширует произвольный файл в набор из 128 бит, а описываемая — в набор, если его так можно назвать, из 1 бита).


Одно такое правило выдаёт 1, когда все входящие биты равны 1, и 0

^ Пример одного из таких алгоритмов


другом случае; другое правило выдаёт 0, если в строке содержится чётное количество единиц, и 1 в другом случае.

^ Пример другого алгоритма того же класса


Каждая компьютерная схема является некоей комбинацией булевых функций, что делает их «строительным материалом всего, что делается в информатике», — сказал Рокко Серведио из Колумбийского университета.

^ А вот это, конечно, хабрааудитории общеизвестно.


P.S. Задумался. Сдаётся мне, функции коррекции ошибок следует искать среди функций с минимальной чувствительностью...

Гипотеза, о которой будут говорить — про хэш-функции
Хэш-функция с двумя значениями? Полезно. Если уж хочется зачем-то дать синоним булевой функции, то это называется «предикат».

Пример одного из таких алгоритмов
Этот «алгоритм» называется AND, конъюнкция

Пример другого алгоритма того же класса
А этот XOR.

То есть, по сути, в том абзаце дается сначала примерное определение булевых функций «на пальцах». Затем приводят два примера: and и xor. А затем следует действительно какое-то капитанское утверждение.
Хэш-функция с двумя значениями? Полезно.

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


Этот «алгоритм» называется AND, конъюнкция… А этот XOR.

Несущественные детали. Аффтар всего-навсего приводит примеры. Примеры, как в большинстве случаев, упрощены до невозможности, чтобы понятно было даже самому распоследнему дебилу.


Вы в математику вообще умеете? Там очень многое основывается на предельных случаях (утрируя, "докажем теорему для N участников… рассмотрим случай, когда N=1...") и индукции.

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

Хэш-функция — это любая функция, (неуникально) отображающая пространство бОльшего размера на пространство меньшего размер

Я не буду комментировать это определение, только замечу, что булева функция f(b) = b ему не соотвествует.

Вы в математику вообще умеете? Там очень многое основывается на предельных случаях (утрируя, «докажем теорему для N участников… рассмотрим случай, когда N=1...») и индукции.

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

Хеш-функция — функция, осуществляющая преобразование массива входных данных произвольной длины в (выходную) битовую строку установленной длины. В данном случае "установленная длина" = 1 бит.


только замечу, что булева функция f(b) = b ему не соотвествует.

Жду объяснений, как именно не соответствует. Как я уже писал выше, это просто частный случай хеш-функции: из пространства размера X переводит в пространство размера 1. Практическая ценность, конечно, близка к нулю (но выше я уже упоминал, например, коды обнаружения/коррекции ошибок: результат "свёртки" = 0 — ошибки нет, результат 1 = ошибка есть).

Хеш-функция — функция, осуществляющая преобразование массива входных данных произвольной длины в (выходную) битовую строку установленной длины.
Можно подать входные данные на набор булевых функций, где каждая функция отвечает за свой выходной бит в выходных данных, и получить таким образом выход любой требуемой разрядности. Или такая «сборка» уже не будет хеш-функцией?

Я не понял, кому Вы это сказали — судя по треду, мне; судя по логике — моему оппоненту. Но я с Вами полностью согласен. (Правда, такие функции могут получиться весьма сложными, но тем не менее принципиально Вы правы. Мы ведь тут не придумываем, как эффективнее функции вычислять, а всего лишь занимаемся интеллектуальным онанизмом упражнениями.)

Мне интересна тема хеш-функций с булевым выходом, поэтому спросил у того, кто видит их связь со статьёй, — у Вас.

Интуитивно предполагаю, что чувствительность у хеш-функций должна быть высокой. То есть, чувствительность можно использовать как оценку «качества» для отбора хеш-функций, порождённых, к примеру, генетическим алгоритмом.

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

Вот хочу спросить, используют ли чувствительность для оценки хеш-функций?

Видите ли, любая функция, осуществляющая вышеописанное отображение, является, по определению, хеш-функцией. А вот является ли она хорошей хеш-функцией — это уже совершенно другой вопрос ;) И моя интуиция с Вашей согласна — (именно для повышения чувствительности в MD5 и прочих алгоритмах применяют неоднократное перемешивание битов). Вот то, что "малое изменение исходного файла вызывает значительное изменение результата" называется "чувствительностью" — это я из этой статьи узнал :)


Вот хочу спросить, используют ли чувствительность для оценки хеш-функций?

Не знаю, но мне кажется, было бы логично так делать!

Можно было написать академично: "любая булева функция может быть представлена как полином Жегалкина".


Можно написать по-простому: "комбинируя AND и XOR можно составить любое условие".


А можно написать так, как написано в статье — длинно, наукообразно, и запутанно.


А вот это, конечно, хабрааудитории общеизвестно.

Надеюсь, что всё-таки да. Особенно во втором варианте.

Если быть совсем точными, то:
«комбинируя AND, XOR, константу 1 можно составить любое условие».

Без константы1 система вроде не полная.
А так да, печальная статья(
Этот аккаунт все время выдает публикации в таком стиле. Я уже даже научился пропускать записи в ленте, не читая заголовок, если вижу характерный аватар. Но бывает (как сейчас, например), что переходишь в статью из «читают сейчас» или «обсуждаемого».
Я не знаю, насколько давно это там началось, но вот буквально на днях дочитал науч-поп книгу "Математика. Утрата определённости" (1980 г.), и там тоже самое — одна и та же мысль по пять раз (раза 3 в пределах нескольких страниц после первого упоминания и потом еще парочку дальше по тексту) и куча воды…
> «западный» науч-поп стиль
никто не заставляет бесполезного графомана Вячеслава переводить все, он мог бы взять пример с уважаемого Ализара, который постит новости только по сути. У Голованова стиль такой же как у убогих журналистов желтой прессы — яркий заголовок и бесполезный контент.
А нельзя ли было кратко и по сути, первые 9 абзацев вообще не несут никакой смысловой нагрузки (их можно было бы смело вынести в конец статьи).
Легко: видим автора, плашку «Перевод», проходим мимо.
Если совсем нечего делать и нет свежих статей — пробегаем текст глазами в течение 10 секунд и пытаемся найти что-то интересное, а потом проходим мимо.
Эм. Самое интересное в статье находится по клику на ссылку «Автор оригинала».
Действительно. Вношу поправку:
Если совсем нечего делать — пробегая глазами, мотаем до низа и кликаем на оригинал. Но там тоже сильно не факт, что будет интересно. Ув. SLY_G иногдапериодически ошибается при переводе каких-то технических деталей, но суть обычно передает верно, и океаны воды в статьях — не его вина.
И интересные статьи он тоже переводит. Чего стоит первая половина цикла «Спросите Итана».
Если я правильно понял, дендриты в мозге тоже ведь так работают, как на первой анимированной гифке? В итоге выход — нейрон пускает-таки импульс в аксон к дендритам следующего нейрона.
Т.е. это доказательство может оказаться полезным в понимании работы мозга.
Для дендритной (к примеру, базальной) ветки, чтобы она сработала должна активироваться цепочка синапсов. Похоже как на гифке, но она просто приведена как пример некой сложной булевой функции, полученной как комбинация нескольких простых.

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

Прошу прощения у математиков, постарался убрать все математические термины из объяснения.


Что такое чувствительность функции на пальцах

Есть функция от нескольких булевых аргументов. Для примера пусть их будет 5. Мы хотим измерить ее чувствительность. Возьмем любой произвольный вход


f(0,1,0,1,1) = 1

каждый аргумент по очереди меняем 0 -> 1, 1 -> 0


f(1,1,0,1,1) = 1
f(0,0,0,1,1) = 0
f(0,1,1,1,1) = 1
f(0,1,0,0,1) = 1
f(0,1,0,1,0) = 0

Смотрим, что функция поменяла свое значение с 1 на 0 для двух вариантов. Значит "чувствительность" этого входа 2.


Для того чтобы узнать чувствительность функции, нам нужно пробежать по каждому возможному входу (в этом случае их 2^5) и выбрать максимальную чувствительность.


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

UFO landed and left these words here
Если я правильно понял, гипотеза в том что чувствительность такой функции с n аргументами больше или равна sqrt(n) в виде формулы:
Чувстветельность(f_n) >= sqrt(n)
UFO landed and left these words here
Доказательство опирается на граф в виде кубика. Если от входных данных ничего не зависит, как в случае с функцией константой, то этот метод не применим, т.к. нет вершин двух разных цветов. Со всеми остальными функциями, с т.ч. XOR — єта нижняя граница работает.
Значит, «чувствительность» этого входа 2.
Не очень понял, что в данном случае понимается под входом. Можно чуть поподробнее этот момент?
Статья — сплошная вода. Где само доказательство? Как оно работает? Единственное, что здесь было интересного — картинка с кубом — осталось непереведённым.

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

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

Учёный из Венесуэлы придумал поистине замечательное доказательство, но у него не хватило бумаги, чтобы его записать :->

А зачем вообще нужно понятие чувствительности, где это можно применить, какого черта вообще придумали эту гипотезу?
Ну в статье это раскрывается косвенно. Если прикинуть с высоты обывателя (то есть то что можем сделать я и любой другой кто не ленится) очевидно что первое применение это стоит ли проводить оценку входных данных порционно (высокая чувствительность) или необходимы все данные за раз (низкая). Был описан пример нейронных сетей например.
Повторю, это — чушь. в булевой алгебре нет понятия чувствительности, вероятности, и прочее. У булевых функций, может быть много аргументов, но все они или 0, или 1, все!!! это закон. Если какой то то ученый утверждает, что 0, может стать, 1, тут ему нужно заняться другим понятием — передача данных с искажениями информации. и восстановлением ее. И еще, когда в статье, или как у вас пишут посте, банкир оперирует понятиями квантовой механики(суперпозицией, или задать сразу несколько вопросов, ну чушь), попридержи коней, не могут они этого знать, по определению. Банкир, человек, который по определению, не может знать теории квантовой физики. Сам прочти, и не переводи больше, не надо.
Only those users with full accounts are able to leave comments. Log in, please.