Член-корреспондент РАН Евгений Щепин: наша математика может спасти кому-то жизнь

^{Фото: Е. Либрик}

^{Каждый из#nbsp;нас сталкивался с#nbsp;ситуацией, когда на#nbsp;экране компьютера внезапно возникает реклама того, о#nbsp;чем вы#nbsp;недавно думали. Неужели компьютеры научились проникать в#nbsp;наши мысли? Как современные технологии внедряются в#nbsp;наше сознание, распознают наш пол и#nbsp;выясняют наши интересы? Можно#nbsp;ли использовать эти технологии не#nbsp;только для#nbsp;навязчивой рекламы, но#nbsp;и#nbsp;на благо человека#nbsp;— например, для#nbsp;диагностики опасных для#nbsp;здоровья состояний? Обо всем этом рассказывает член-корреспондент РАН Евгений Витальевич Щепин, главный научный сотрудник отдела геометрии и#nbsp;топологии Математического института им.#nbsp;В.#nbsp;А.#nbsp;Стеклова.}

^{—#nbsp;Евгений Витальевич, мы#nbsp;находимся в#nbsp;историческом месте института#nbsp;— библиотеке, которую собирал еще его основатель, выдающийся математик академик В.#nbsp;А.#nbsp;Стеклов. Одна из#nbsp;ваших научных задач#nbsp;— распознавание текстов. Скажите, если взять какой-то текст, например опубликованный в#nbsp;этой книжке, каким образом можно его математически распознать?}

^{—#nbsp;Происходит это следующим образом. Сканер выдает оцифрованное изображение сканируемой страницы текста, которое представляет собой последовательность строчек: байт, которые выражают степень «серости» соответствующих точек сканируемой страницы.}

^{Сначала оцифрованное изображение бинаризуется: если серость точки не#nbsp;превосходит некоторого выбранного порога, то#nbsp;она обнуляется, а#nbsp;иначе заменяется единицей. Таким образом, в#nbsp;компьютере изображение символа представляет собой так называемую булеву матрицу из#nbsp;нулей и#nbsp;единиц, в#nbsp;которой нули соответствуют фону, а#nbsp;единицы точкам изображения. Булева матрица символа содержит всю необходимую для#nbsp;распознавания информацию. Взглянув на#nbsp;нее, человек сразу его распознает.}

^{—#nbsp;Как#nbsp;же его распознать компьютеру?}

^{—#nbsp;Простейший матричный способ распознавания заключается в#nbsp;поэлементном сравнении символа с#nbsp;матрицами образцов, имеющихся у#nbsp;компьютера. Количество различающихся элементов служит мерой близости матриц. Образец, матрица которого наименее отличается от#nbsp;распознаваемой, и#nbsp;объявляется компьютером результатом распознавания, если, конечно, количество различий не#nbsp;слишком велико. В#nbsp;противном случае компьютер считает символ не#nbsp;распознанным.}

^{—#nbsp;Таким образом можно распознать любой текст?}

^{—#nbsp;Нет, к#nbsp;сожалению, распознавание матричным способом годится только для#nbsp;печатного текста и#nbsp;требует от#nbsp;пользователя долгого предварительного обучения программы. Булева матрица символа содержит всю необходимую информацию о#nbsp;нем, но#nbsp;при этом еще и#nbsp;слишком много избыточной. Встает вопрос: как выделить из#nbsp;нее существенную информацию для#nbsp;распознавания?}

^{Мы#nbsp;придумали такой способ. Любая строка матрицы представляет собой последовательность нулей и#nbsp;единиц. Последовательность единиц строки, предшествуемую и#nbsp;завершаемую нулями, будем называть пересечением с#nbsp;символом, а#nbsp;последовательность нулей строки, предшествуемую и#nbsp;завершаемую единицами,#nbsp;— пересечением с#nbsp;фоном.}

^{Если мы#nbsp;последовательно, двигаясь сверху вниз, заменим все строки матрицы количеством пересечений с#nbsp;символом, то#nbsp;получим последовательность пересечений, которая хотя и#nbsp;недостаточна для#nbsp;полного распознавания, но#nbsp;имеет долю полезной информации намного выше исходной матрицы.}

^{Последовательность пересечений, в#nbsp;свою очередь, можно сократить, удалив из#nbsp;нее все элементы, которым предшествуют точно такие#nbsp;же. В#nbsp;результате из#nbsp;матрицы получится короткий код числа пересечений. Например, для#nbsp;буквы I#nbsp;в#nbsp;любом шрифте код пересечений состоит из#nbsp;единственной единицы, для#nbsp;V#nbsp;код будет 2−1, для#nbsp;Н#nbsp;код 2−1-2 и#nbsp;т.#nbsp;д.}

^{—#nbsp;Вам удалось усовершенствовать код пересечений. Это так?}

^{—#nbsp;Да, для#nbsp;этого мне пришлось проанализировать пары соседних строк матрицы. А#nbsp;именно, будем говорить, что пересечение символа нижней строки продолжает пересечение верхней, если один из#nbsp;элементов верхнего пересечения находится точно над элементом нижнего. Аналогично определяется понятие продолжения для#nbsp;фоновых пересечений.}

^{Пересечения, не#nbsp;выступающие ничьими продолжениями из#nbsp;предыдущей строки, кодируются символом Р (рождение). Пересечения, не#nbsp;имеющие продолжения на#nbsp;следующей строчке, кодируются символом С (смерть). Остальные кодируются символом П (продолжение). Большинство строк матрицы символа содержат только пересечения типа П. Опустив эти строки, мы#nbsp;получим ПРС-код символа, который содержит существенно больше информации, чем обычный код пересечений, весьма устойчив к#nbsp;изменениям шрифта и#nbsp;даже пригоден к#nbsp;распознаванию рукописных символов.}

^{—#nbsp;Это почти что человеческая жизнь! А#nbsp;как можно записать такой код?}

^{—#nbsp;ПРС-код символа можно написать по#nbsp;одному его виду, не#nbsp;зная матрицы. Например, ПРС-код буквы A#nbsp;будет выглядеть как Р; ПРП; ПСП; ПРП; СС, причем этот код не#nbsp;зависит от#nbsp;жирности буквы и#nbsp;ее#nbsp;наклона.}

^{—#nbsp;Этого достаточно для#nbsp;распознавания текста?}

^{—#nbsp;Одного ПРС-кода, конечно, недостаточно. Например, такой#nbsp;же ПРС-код, как А, имеют буквы Я и Д. Поэтому к#nbsp;нему добавляют другие, метрические признаки, например учет расстояний между различными строками, что позволяет надежно отличить, А#nbsp;от Д.}

^{—#nbsp;Как вы#nbsp;— чистый математик#nbsp;— пришли к#nbsp;распознаванию текстов?}

^{—#nbsp;Появление персональных компьютеров в#nbsp;конце 1980-х гг. стимулировало исследования по#nbsp;распознаванию образов. Так, в#nbsp;институте Стеклова при отделе топологии организовался небольшой семинар по#nbsp;этой теме. Начали мы#nbsp;с#nbsp;распознавания рукописных символов. Среди участников-топологов был хороший программист Григорий Непомнящий, который реализовывал возникавшие интересные топологические идеи на#nbsp;привезенном мною из-за границы#nbsp;ПК. Потом появился Виталий Кляцкин из#nbsp;Тулы, который привлек участников семинара к#nbsp;выполнению связанного с#nbsp;распознаванием военного заказа.}

^{Годичная работа над этим заказом привела к#nbsp;появлению уверенного в#nbsp;своих силах сплоченного коллектива программистов-математиков. И#nbsp;в#nbsp;начале 1990-х гг. этот коллектив под моим руководством составил костяк фирмы, взявшейся создать программу оптического распознавания текстов, основанную на#nbsp;открытом мной ПРС-коде, который был нашей коммерческой тайной. Получившаяся у#nbsp;нас тогда программа «Крипт» была одной из#nbsp;лучших на#nbsp;рынке. Например, первая версия FineReader ей#nbsp;заметно уступала. Программу можно было быстро обучить распознавать любой текст. Например, текст на#nbsp;армянском языке.}

^{—#nbsp;Никогда не#nbsp;слышала о#nbsp;такой программе…}

^{—#nbsp;Коммерческое распространение программы потребовало роста фирмы: нужно было готовить подробную документацию, защиту от#nbsp;копирования, драйверы для#nbsp;разных сканеров, подключать словари и#nbsp;многое другое. А#nbsp;в#nbsp;1995#nbsp;г.#nbsp;наш главный программист Григорий Непомнящий эмигрировал в#nbsp;США. И#nbsp;наша маленькая фирма не#nbsp;выдержала конкуренции с#nbsp;большими фирмами. После ее#nbsp;«кончины» в#nbsp;1995#nbsp;г.#nbsp;я и#nbsp;некоторые мои товарищи поработали еще в#nbsp;оптическом распознавании на#nbsp;конкурентов из#nbsp;Cognitive Technologies, но#nbsp;с#nbsp;1998#nbsp;г.#nbsp;я не#nbsp;занимался оптическим распознаванием.}

^{—#nbsp;Вы#nbsp;немало времени и#nbsp;сил посвятили еще одной научной задаче, связанной с#nbsp;суперкомпьютерами. Расскажите, пожалуйста, что такое кривые Пеано и#nbsp;как они связаны с#nbsp;суперкомпьютерами?}

^{—#nbsp;В#nbsp;данный момент у#nbsp;суперкомпьютеров есть такая проблема: задач для#nbsp;них мало. Суперкомпьютеров наделали много, а#nbsp;чем их#nbsp;загрузить? Задача с#nbsp;кривыми Пеано позволяет загрузить суперкомпьютер основательно. Приблизительно эту задачу можно сформулировать так: представьте, что у#nbsp;нас есть n-мерная решетка. Нам нужно ее#nbsp;как-то упорядочить#nbsp;— всем элементам решетки дать номера так, чтобы узлы решетки с#nbsp;близкими номерами находились по#nbsp;возможности недалеко друг от#nbsp;друга.}

^{Эту задачу и#nbsp;решают многомерные кривые Пеано. Например, еще в#nbsp;самом начале компьютерного времени у#nbsp;меня была идея сделать развертку телевизора по#nbsp;кривой Пеано.}

^{Развертка#nbsp;— это строчки на#nbsp;экране. А#nbsp;теперь представьте#nbsp;— пошла помеха. Тогда она выбивает несколько строчек. А#nbsp;кривая Пеано устроена так: если у#nbsp;вас пошла помеха, то#nbsp;она не#nbsp;растянется на#nbsp;весь экран, а#nbsp;свернется. Поэтому телевизор с#nbsp;пеановской разверткой был#nbsp;бы лучше обычного. Помехи меньше#nbsp;бы мешали на#nbsp;экране.}

^{—#nbsp;У#nbsp;вас это получилось?}

^{—#nbsp;Нет. Теоретически все это ясно, есть обоснования, есть кривые, есть формулы. Сделать все это вполне возможно. Но, к#nbsp;сожалению, электронно-лучевые трубки ушли в#nbsp;прошлое, сейчас все телевидение устроено по-другому.}

^{Зато по#nbsp;поводу телевидения у#nbsp;меня есть другая замечательная идея, которую хорошо#nbsp;бы внедрить. Это цифровой двумерный аналог пеановской кривой. Представьте себе, что у#nbsp;нас есть шахматная доска на#nbsp;64 клетки. Есть палитра цветов#nbsp;— red, green, blue. Для#nbsp;каждого цвета#nbsp;— четыре градации. И#nbsp;тогда у#nbsp;нас получится всего градаций цвета тоже 64, 43, так#nbsp;же как шахматная доска. И#nbsp;теперь каждую клетку шахматной доски нужно раскрасить в#nbsp;один из#nbsp;цветов. Все будут разного цвета. Но#nbsp;нужно раскрасить так, чтобы соседние клетки были окрашены в#nbsp;соседние цвета. Такая непрерывная гамма, где цвет все время меняется.}

^{—#nbsp;Это будет красиво.}

^{—#nbsp;Красиво. Вот это было замечательно сделано обычным компьютером. Обошлись без суперкомпьютера. У#nbsp;нас с#nbsp;сыном (он#nbsp;программист) опубликована статья на#nbsp;эту тему. Я#nbsp;был уверен, что такую раскладку невозможно сделать. Придумал алгоритм, который хорошо сокращал счет. Компьютер считал ночь.}

^{—#nbsp;Вы#nbsp;пытались сделать то, во#nbsp;что не#nbsp;верили?}

^{—#nbsp;Думал, что нельзя. И#nbsp;вдруг компьютер выдал#nbsp;— оказалось, что такая раскладка уникальна. Их#nbsp;существует ровно четыре. Они друг от#nbsp;друга отличаются поворотом. И#nbsp;действительно картинка очень красивая.}

^{—#nbsp;И#nbsp;каким образом вы#nbsp;хотите это внедрить на#nbsp;телевидении?}

^{—#nbsp;Оказывается, в#nbsp;системе PAL/SECAM используют в#nbsp;кодировании цветов так называемый двумерный код Грея. Насколько я#nbsp;помню, там 4×4, 16 цветов. Они разложены именно так, чтобы цвета соседних клеточек были соседними. Это прекрасная защита от#nbsp;помех. У#nbsp;них на#nbsp;16 цветов, а#nbsp;у#nbsp;меня на#nbsp;64, что намного лучше. Учитывая разрядность процессоров, это может хорошо ложиться на#nbsp;операционную систему. Так что это вещь, которая просто просит внедрения.}

^{—#nbsp;Помимо улучшения качества картинки, осталось еще повысить качество самих передач на#nbsp;ТВ. Знаю, что вы#nbsp;занимались не#nbsp;только распознаванием текстов, но#nbsp;и#nbsp;распознаванием пола, возраста человека. Что это за#nbsp;работа?}

^{—#nbsp;Речь идет о#nbsp;работе в#nbsp;«Яндексе», где я#nbsp;был научным консультантом. Мы#nbsp;решали интересную задачу: когда человек ходит по#nbsp;интернету, его маршрут известен, и#nbsp;нужно было распознать, мужчина это или женщина, с#nbsp;целью таргетированной рекламы. Эта задача была решена.}

^{—#nbsp;Каким образом можно понять, мужчина это или женщина?}

^{—#nbsp;У#nbsp;нас есть достаточно большая база данных людей, про которых известно, мужчины это или женщины. Дальше: мы#nbsp;начинаем смотреть, сайт мужской или женский, уже зная, мужчина или женщина его смотрят, сколько женщин и#nbsp;сколько мужчин туда ходят. Ведь для#nbsp;каждого сайта есть статистика#nbsp;— сколько там было женщин и#nbsp;сколько мужчин. И#nbsp;после этого мы#nbsp;начинаем определять. На#nbsp;основании этих данных мы#nbsp;выдаем формулу, определяющую вероятность того, кто это, мужчина или женщина. Чаще всего мы#nbsp;оказывались правы.}

^{—#nbsp;А#nbsp;почему оказалось невозможным определить возраст человека?}

^{—#nbsp;Потому что возрастов не#nbsp;два, а#nbsp;больше. Вся методика, с#nbsp;которой мы#nbsp;работали, опиралась на#nbsp;эти статистики. И#nbsp;оказалось, что можно получить, вычислить, точно определить количество информации о#nbsp;поле или о#nbsp;возрасте, которая содержится в#nbsp;базе данных. Сколько она содержит информации#nbsp;— вычисляется строго математическое понятие. Было известно, сколько нужно, чтобы обеспечить такую точность, потому что задача определения пола была решена так: распознаватель в#nbsp;половине случаев вообще отказывался распознавать, кто это. А#nbsp;в#nbsp;половине, когда соглашался, угадывал правильно с#nbsp;вероятностью 80%. Требовалось что-то в#nbsp;таком роде.}

^{Тут можно посчитать, сколько информации необходимо для#nbsp;данного задания, чтобы обеспечить заданные параметры распознавания, и#nbsp;сколько есть информации в#nbsp;базе данных.}

^{Я#nbsp;сумел это посчитать и#nbsp;показать, что ее#nbsp;не#nbsp;хватает. А#nbsp;чтобы посчитать, нужно было придумать нечто хитрое. Проблема тут заключается в#nbsp;большом количестве сайтов с#nbsp;малой статистикой. Например, сайт посетил один человек, и#nbsp;все. Какая вероятность того, что следующий посетитель того#nbsp;же пола? И#nbsp;я#nbsp;придумал такой трюк#nbsp;— вторичную статистику. Мы#nbsp;берем эту базу данных и#nbsp;делим ее#nbsp;пополам. Используя только первую половину базы, определяем все сайты с#nbsp;единственным посещением, объединяем и#nbsp;говорим, что это «сайт первого типа». А#nbsp;для объединенного сайта первого типа анализируем уже немалую статистику его посещений из#nbsp;второй половины базы. Эта вторичная статистика и#nbsp;позволяет надежно найти искомые вероятности и#nbsp;аккуратно определить количество информации в#nbsp;базе.}

^{—#nbsp;Как думаете, такие вещи, которые вы#nbsp;придумали, можно использовать для#nbsp;чего-то еще, кроме рекламы, которая уже порядком надоела?}

^{—#nbsp;Да#nbsp;для чего угодно! То, чем мы#nbsp;занимались, это, что называется, Big data. Эти трюки с#nbsp;подсчетом информации, конечно, вещь универсальная. Там еще возможен анализ общего типа, когда мы#nbsp;пытаемся что-то предсказывать. Скажем, поведение. Когда технологии предсказаний развиваются, то#nbsp;мы#nbsp;можем предсказать все что угодно, если, конечно, данные содержат достаточно информации.}

^{—#nbsp;Это хорошо или плохо, когда можно предсказать все что угодно?}

^{—#nbsp;Это не#nbsp;хорошо и#nbsp;не#nbsp;плохо. Это данность. Эта методика работает с#nbsp;большими данными. Данные, с#nbsp;которыми работают в#nbsp;медицине или на#nbsp;бирже, по#nbsp;существу однотипны#nbsp;— это кривые. Кардиограммы и#nbsp;энцефалограммы в#nbsp;медицине или графики изменения биржевых цен, объемов продаж акций. Задача диагностики предынфарктного состояния человека или состояния биржи (канун краха) по#nbsp;существу одинакова. Для#nbsp;всех этих задач используются фрактальные размерности, алгоритмы определения разладки и#nbsp;многое другое. То#nbsp;есть это универсальные методики, которые могут многим спасти жизнь. Так что математика наша вполне прикладная.}

^{Интервью проведено при поддержке Министерства науки и#nbsp;высшего образования#nbsp;РФ и#nbsp;Российской академии наук.}

Беседовала Наталия Лескова. Фотограф Елена Либрик. Оператор Дмитрий Самсонов. Научная Россия

2023-04-30 20:16