x, y, z

Математическая теория информации Клода Шеннона

Андрей Соболевский

Комментарии: 0

Ольга Орлова: В 1948 году американский математик Клод Шеннон опубликовал статью «Математическая теория информации». Тогда, 70 лет назад, эта работа легла в основу современной теории информации и принесла ученому мировую славу. А математика с тех пор стала влиять на жизнь людей в реальном, а не отложенном времени. О том, где сегодня лежит граница между полезной и бесполезной математикой, мы решили спросить директора Института проблем передачи информации имени Харкевича Российской академии наук Андрея Соболевского.

Здравствуйте, Андрей. Спасибо, что пришли к нам в программу.

Андрей Соболевский: Здравствуйте. Спасибо за приглашение.

Андрей Соболевский, родился в 1974 году в Москве. В 1996 году окончил физический факультет МГУ имени Ломоносова, где преподавал до 2009 года. В 2011 году получил степень кандидата физико-математических наук. В 2014 году стал доктором физико-математических наук по специальности «Математическая физика». В 2009 году перешел на работу в Институт проблем передачи информации Российской академии наук. В 2015 году избран профессором РАН по отделению нанотехнологий и информационных технологий. В 2016 году назначен и в 2017 году избран директором Института проблем передачи информации Российской академии наук.

Ольга Орлова: Итак, в этом году исполняется 70 лет со дня публикации знаменитой работы Клода Шеннона «Математическая теория информации», которая легла в основу современной теории информации, которая, в свою очередь, совершила революцию с нашей с вами жизнью. И это принято считать такой точкой отсчета. И интересно, что тот период, когда математики совершили такой шаг от так называемой бесполезной, эзотерической математики к полезной математики, условно говоря, такой прикладной, которая позволяет решать инженерные задачи, этот период оказался очень небольшим в историческом масштабе – всего лишь каких-то около 40 лет, когда работы Клода Шеннона стали классикой. И многие очевидцы любят вспоминать, как когда он приехал на международный конгресс по теории информации, к нему выстроились ученые-участники конгресса, будучи потрясенными, что Клод Шеннон жив. И кто-то из современников сказал: «Вы понимаете, это как будто Исаак Ньютон сейчас появился на конференции по физике». Многие не могли поверить, что этот человек жив, еще работает, занимается какими-то другими вещами.

И что же удалось сделать Шеннону и другим его коллегам?

Андрей Соболевский: Математика, которая там используется, ее старшему школьнику можно пересказать. Это лучше делать с доской и мелом или хотя бы с бумагой и фломастером. Но точно не в телевизионной студии. Чем эта работа замечательна? Тем, что Шеннон предложил математическую формализацию, математическую модель понятия информации, которая полностью абстрагировалась от содержания, от смысла. И таким образом ему удалось сосредоточиться на инженерно важной вещи – на акте коммуникации, на акте передачи сообщения.

Ольга Орлова: То есть существует математическая запись акта коммуникации, не зависящая от того, что мы говорим?

Андрей Соболевский: Абсолютно. Причем, это на первый взгляд кажется чем-то крайне жестоким, потому что коммуникация – это как раз про смысл. Но это для коммуницирующих объектов так. А для инженера, который должен акт коммуникации обеспечить правильной связью, в общем-то, все равно, что передается. И тут надо сказать, что Шеннон, найдя этот способ формализовать понятие информации, абстрагировавшись от смысла, он сделал похожее на то, что сделал другой великий американский ученый, физик Джозайя Гиббс, самобытный американский, он никоим образом не импортирован из Европы, он ни у кого не учился из европейцев, который предложил такую математическую модель для термодинамики, что когда появилась квантовая механика и возникла совершенно новая физика, выяснилось, что гиббсовская модель канонических ансамблей отлично в квантовой механике работает тоже.

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

То есть даже те несколько лет, которые прошли между 1948 годом, когда была напечатана эта статья, и 1956 годом, когда Шеннон напечатал маленькую одностраничную статью («Bandwagon», такой грузовик, на котором ярмарочный оркестрик ездит по городу и зазывает всех на ярмарку). Там очень ядовитая страничка текста, что «дорогие коллеги, теория информации стала слишком модной и во многих других смежных науках ее люди пытаются использовать, для того чтобы описать, может быть, без достаточных на то оснований…». То есть этот взрывной рост интереса к теории информации был в течение нескольких лет.

Ольга Орлова: Эта статья принесла Шеннону сразу всемирную славу. Но среди математиков вообще его продвижение было не таким…

Андрей Соболевский: Со скепсисом.

Ольга Орлова: Было не таким простым. Причем, это было связано не только с тем, как это происходило, например, в Советском Союзе, где…

Андрей Соболевский: Где были политические причины.

Ольга Орлова: Да. И труды Шеннона были отнесены к разряду «кибернетика», а это буржуазная лженаука в это время. И, соответственно, никто не мог как-то развивать эти идеи. Но ведь то же самое было и среди западных математиков, которые с трудом это все усваивали.

Андрей Соболевский: Даже я бы сказал, что в Советском Союзе Шеннону в каком-то смысле повезло, потому что первая публикация сокращенного русского перевода этой статьи была сделана в 1953 году в сборничке переводов новых свежих американских работ по коммуникациям, который был подготовлен под редакцией тоже инженера, а не математика, Николая Андреевича Железнова. На Николая Андреевича наши математики обиделись. Потому что случилось следующее. У него была задача в сколько-то издательских листов вместить переводы нескольких статей, которые в сумме были больше по объему. Поэтому он начал их сокращать. И в статье Шеннона он оставил все мотивировочное, все концептуальное, а технические доказательства сократил. Дальше Хинчин, Колмогоров, в общем, наши ведущие математики прочитали эту статью. Они, в отличие от многих западных коллег, поняли, насколько важная вещь произошла, оценили, что эти утверждения, сделанные Шенноном, должно быть нетрудно доказать. И начали дублировать его доказательства, потому что они не знали, что доказательства были в американском оригинале. Побочным итогом этой истории явилось то, что очень быстро в 1960-е годы, если мне память не изменяет, появился толстый однотомник «Полное собрание сочинений Шеннона» (комментированное), и долгое время только на русском языке оно существовало. Потом уже совсем в 2000-е годы в юбилейной ситуации издали какое-то и английское издание.

Ольга Орлова: А как вы думаете, а с чем связано, что советские математики поняли, что здесь какой-то важный момент? Потому что у Колмогорова в его воспоминаниях сохранилась такая запись, что он писал: «Значение работ Шеннона для чистой математики не сразу было достаточно оценено. Мне вспоминается, что еще на международном съезде математиков в Амстердаме, - это Международный математический конгресс 1954 года в Амстердаме, - мои американские коллеги, специалисты по теории вероятности считали мой интерес к работам Шеннона несколько преувеличенным, так как это более техника, чем математика. Сейчас такие мнения вряд ли нуждаются в опровержении. Правда, строгое математическое обоснование своих идей Шеннон в сколько-нибудь трудных случаях предоставил своим продолжателям. Однако его математическая интуиция изумительно точна», - пишет Колмогоров.

Как вы думаете, почему так это все происходило? Почему советские математики поняли и что-то почувствовали, инженеры на Западе тоже, а вся мировая математика не пришла в такой восторг в предчувствии огромных перемен, которые разворачиваются.

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

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

У Платона в одном из диалогов Сократ на пиру начинает, для того чтобы проиллюстрировать свою идею, что души не умирают, а переселяются, такой эксперимент. Он начинает спрашивать мальчика-виночерпия, задает ему вопрос за вопросом, и мальчик, отвечая на эти вопросы, постепенно доказывает, что корень из двух – это иррациональное число, что его нельзя записать рациональной дробью. Вывод, который делает Сократ, что бессмертная душа, которая в этом теле находится, она в идеальном мире знает этот факт, но, оказавшись в теле мальчика-виночерпия, требует наводящих вопросов, чтобы вспомнить его. Так или иначе, я не буду солидаризироваться с Сократом в этом смысле, но это был замечательный результат античной математики, именно такой эзотерический, результат про математические структуры. Для практики… я не знаю, 41/29 – это с точностью до уже десятых долей процента приближение корня из двух. Вот, пожалуйста, это рациональная дробь, но она не совсем совпадает с числом.

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

Еще один из людей, которых я хотел бы упомянуть – Леонид Витальевич Канторович. Он ведь, будучи замечательным абстрактным математиком-концептуалистом, еще и чудесные работы по приближенным вычислениям делал. Но это традиционное. Приближенные вычисления – да, это и математика, и с другой стороны практика. А тут внезапно оказывается, что очень простая конструкция из теории вероятности, теории марковских цепей, которые понадобились Шеннону, что они непосредственно применимы для инженера, что без этой цепочки еще других ученых, коллег, физиков, которые с инженерами разговаривают.

Ольга Орлова: Аналогичная в каком-то смысле ситуация… Она где-то совпадала по времени. Она была на несколько лет раньше. Получается, когда Алан Тьюринг пытался создать свою счетную машину, он отталкивался от идей Гильберта, которые вообще никак не имели никакого прикладного смысла, значения и направления.

Андрей Соболевский: Абсолютно. Тьюринг – математический логик по своей специальности. Это очень абстрактная наука. Другое дело, что логики сначала в лице того же Тьюринга оказались востребованы в криптографии, а потом, когда возник искусственный интеллект, логики успешно сделали вид, что часть математической логики – это и есть искусственный интеллект. Тем не менее, в тот момент это, конечно, была очень абстрактная наука. Три имени, про которые хочется поговорить – это Шеннон, с которого мы начали, Канторович, у которого тоже есть юбилей, потому что первая опубликованная работа Канторовича по линейному программированию – это 1938 год, это 80 лет. И Тьюринг, который в эту юбилейную мишень не попадает, ну и слава богу, 1936 год.

Ольга Орлова: Но он все равно современник Шеннона и Канторовича. И они живут в одно время.

Андрей Соболевский: И они очень близки по поколению.

Ольга Орлова: Да. И они, получается, в течение буквально 10 или 15 лет умудряются прямо склеить в трех разных направлениях большую математику и технику.

Андрей Соболевский: Инженерию, да.

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

Андрей Соболевский: Если присмотреться к тому, что сделали эти три совершенно разных человека, которых обычно не объединяют, то там все-такие есть общая какая-то концептуальная подложка у Тьюринга, у Шеннона и внезапно у Канторовича, которого еще меньше принято к ним причислять. Что роднит Тьюринга и Шеннона? У Шеннона ведь две основных идеи. Про одну я сказал. Ему удалось концептуализировать коммуникацию, концептуализировать понятие информации так, что ушел смысл и осталась некая техника этого дела – помехи, распределение вероятностей…

Ольга Орлова: Коммуникация с технической точки зрения.

Андрей Соболевский: Коммуникация с технической точки зрения. Но у него есть еще одна идея, даже более ранняя. У Шеннона есть еще одна плодотворная идея, что любую коммуникацию можно свести к передаче битов, к передаче двоичных символов – нулей и единиц. Это тоже очень правильная и плодотворная абстракция. На практике, разумеется, часто эффективнее пользоваться какими-то другими алфавитами, но концептуально нет большой разницы между тем, что используется на практике и вот этим теоретическим алфавитом из нулей и единиц. А когда появились цифровые вычислительные машины в двоичной логике, то это стало уже и нормой.

Эта же самая идея, но только уже не коммуникация, а алгоритмические вычисления сводятся к манипуляциям нулями и единицами, есть и у Тьюринга. Машина Тьюринга ведь на самом деле модель не компьютера даже. Машина Тьюринга – это модель работающего математика. Работающий математик снабжен записной книжкой. У него есть пишущий инструмент (перо, ручка, карандаш). На страницах этой книжки он пишет свои формулы, иногда перелистывает, возвращается на несколько страниц назад, чтобы посмотреть, что было записано там. Ясно, что на странице вы больше определенного количества знаков не запишите. И дальше Тьюринг говорит – а вот концептуализируем это так: на странице помещается ровно один знак, нолик или единичка. Это бесконечная лента. Проще представить себе ленту, чем книжку. И по этой бесконечной ленте перемещается голова этого математика, у которой есть какое-то внутреннее состояние. Она обозревает ноль или один, записанные в какой-то клеточке, может эту цифру поменять, может куда-то отъехать. Появилась машина Тьюринга.

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

Здесь возникает еще третий наш герой – Леонид Витальевич Канторович (это тоже середина 1930-х годов, уже очевидно пахнет жареным, очевидно, что что-то в мире случится, в 1937 году гражданская война в Испании уже вовсю идет). И там приходит к Канторовичу группа инженеров из фанерного треста, у которых имеется задача. У них есть станки. На них разные виды сырья можно обрабатывать с разной эффективностью. Нужно некоторое количество изделий произвести. Как это сделать оптимальным образом?

Они с этой задачей, прежде чем прийти к Канторовичу, походили еще по Ленинградскому институту математики. На них все смотрели…

Ольга Орлова: Что они пришли не по адресу?

Андрей Соболевский: Да, совершенно не по адресу.

Ольга Орлова: Что к математикам с такими вопросами не обращаются.

Андрей Соболевский: Это абсолютно элементарная задача. Она решается полным перебором. Но полный перебор даже в той постановке, в которой Канторович эту задачу впервые узнал, там полный перебор из миллиарда вариантов. Он это описывает в своей научной автобиографии, такую вообще стоит почитать. Он тоже, столкнувшись с этой задачей и оценив, что инженеры смогли ее достаточно хорошо поставить, понял, что здесь, конечно, есть проблема. Сразу, правда, ничего им не предложил, но после этого зацепился, начал думать и начал постепенно понимать, что это частный представитель важного класса задач. Другие примеры, которые ему приходили в голову, были экономические, потому что он вообще в этот момент еще и об экономике начал думать, что и привело его в итоге к Нобелевской премии по экономике, кстати говоря.

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

Алгоритмическая вычислимость, алгоритмы – раз. Битовая абстракция смысла, которая позволяет манипулировать битами алгоритмически, не отвлекаясь на содержание. И еще третья идея, она тоже сквозная, и тут тоже правильно вернуться к Шеннону. И она, пожалуй… Я не очень вижу, где эта идея содержательно присутствует у двух других людей, она именно у Шеннона, что сложность надо заменять на случайность. И это, кстати говоря, третья сквозная тема. Алгоритмы, биты и случайность вместо сложности.

Это случилось в нескольких разных точках математической науки, случилось почти одновременно на протяжении от 1936 до 1948 года. Другое дело, что там еще много чем эти годы были наполнены. Но прошло совсем немного времени. И кажется, что эти американские вероятностники, которые удивлялись, что Колмогоров заинтересовался сугубо техническим предметом, они просто все-таки еще несколько в XIX веке оставались.

Ольга Орлова: Они не догоняли?

Андрей Соболевский: Да, да, да.

Ольга Орлова: Мы с вами начали разговор с одной научной даты. А мне хотелось бы вспомнить такую человеческую биографическую дату. Удивительно, что в августе 2018 года исполнилось 100 лет уникальной женщине - прикладному математику, которая жива, Кэтрин Джонс, которая в NASA рассчитывала вручную, еще в докомпьютерную эпоху, она рассчитывала траектории движения кораблей. И надо сказать, что очень трогательно было, по-моему, в прошлом году. Ее привезли на церемонию «Оскара». Поскольку по истории жизни Кэтрин Джонс был снят фильм «Скрытые фигуры» В Голливуде. И ее вывезли в коляске, чтобы показать всему миру эту уникальную женщину. Фильм «Скрытые фигуры» был номинирован на «Оскар», где целый отряд чернокожих женщин в тяжелейших условиях дискриминации в то время работали, выполняли фактически роль компьютеров, которых тогда не было. Тогда это были женские мозги.

Андрей Соболевский: Более того, слово «компьютер» тогда означало как раз профессии всех женщин – вычислитель. Они и были компьютеры.

Ольга Орлова: Да. И, конечно, сейчас этот фильм смотрится именно с точки зрения такой политической, феминистской. То есть история их борьбы. А как это смотрится сейчас с точки зрения науки?

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

Ольга Орлова: Математика, полезная в народном хозяйстве.

Андрей Соболевский: Когда у вас из математической модели, из каких-то физических и инженерных формул вам необходимо извлечь число или, может быть, даже не число, а траекторию ракеты, которая должна куда-то долететь. И вы это должны сделать точно, не ошибаясь и максимально эффективно. И это искусство. Причем, оно действительно… Эти женщины, конечно, считали не полностью вручную, у них были счетные машинки, конечно же. Но оперировать этими счетными машинками… программа вычислений была все-таки в их головах. В этом смысле они компьютеры.

С появлением программируемых и вычислительно мощных компьютеров здесь действительно становится меньше искусства и больше техники. Это отчасти жаль, потому что сложность вычислений здесь в том, чтобы дать максимально экономными средствами максимально точный ответ. Кстати, Владимир Михайлович Тихомиров, замечательный наш математик, ученик Колмогорова, который в 1954 году закончил мехмат… Работа Шеннона – 1948 год, на русском языке – 1953. «Bandwagon» - статья 1956 года. Тоже те великие годы. Тихомиров сказал, что на курсе была масса замечательных умненьких девушек. Потом они все куда-то пропали. Потом стало ясно, почему. Потому что они все разошлись по организациям, в которых они были нужны именно как вычислители и работу в которых не надо было слишком сильно афишировать.

Ольга Орлова: Спасибо вам огромное за очень интересный разговор. У нас в программе был директор Института проблем передачи информации имени Харкевича Российской академии наук Андрей Соболевский.

Гамбургский счет
11 октября 2018
ОТР
Комментарии: 0