Этот учебник рассказывает о главных преимуществах функций ИНДЕКС и ПОИСКПОЗ в Excel, которые делают их более привлекательными по сравнению с ВПР . Вы увидите несколько примеров формул, которые помогут Вам легко справиться со многими сложными задачами, перед которыми функция ВПР бессильна.
В нескольких недавних статьях мы приложили все усилия, чтобы разъяснить начинающим пользователям основы функции ВПР и показать примеры более сложных формул для продвинутых пользователей. Теперь мы попытаемся, если не отговорить Вас от использования ВПР , то хотя бы показать альтернативные способы реализации вертикального поиска в Excel.
Зачем нам это? – спросите Вы. Да, потому что ВПР – это не единственная функция поиска в Excel, и её многочисленные ограничения могут помешать Вам получить желаемый результат во многих ситуациях. С другой стороны, функции ИНДЕКС и ПОИСКПОЗ – более гибкие и имеют ряд особенностей, которые делают их более привлекательными, по сравнению с ВПР .
Так как задача этого учебника – показать возможности функций ИНДЕКС и ПОИСКПОЗ для реализации вертикального поиска в Excel, мы не будем задерживаться на их синтаксисе и применении.
Приведём здесь необходимый минимум для понимания сути, а затем разберём подробно примеры формул, которые показывают преимущества использования ИНДЕКС и ПОИСКПОЗ вместо ВПР .
Функция INDEX (ИНДЕКС) в Excel возвращает значение из массива по заданным номерам строки и столбца. Функция имеет вот такой синтаксис:
Каждый аргумент имеет очень простое объяснение:
Если указаны оба аргумента, то функция ИНДЕКС возвращает значение из ячейки, находящейся на пересечении указанных строки и столбца.
Вот простейший пример функции INDEX (ИНДЕКС):
INDEX(A1:C10,2,3)
=ИНДЕКС(A1:C10;2;3)
Формула выполняет поиск в диапазоне A1:C10 и возвращает значение ячейки во 2-й строке и 3-м столбце, то есть из ячейки C2 .
Очень просто, правда? Однако, на практике Вы далеко не всегда знаете, какие строка и столбец Вам нужны, и поэтому требуется помощь функции ПОИСКПОЗ .
Функция MATCH (ПОИСКПОЗ) в Excel ищет указанное значение в диапазоне ячеек и возвращает относительную позицию этого значения в диапазоне.
Например, если в диапазоне B1:B3 содержатся значения New-York, Paris, London, тогда следующая формула возвратит цифру 3 , поскольку “London” – это третий элемент в списке.
MATCH("London",B1:B3,0)
=ПОИСКПОЗ("London";B1:B3;0)
Функция MATCH (ПОИСКПОЗ) имеет вот такой синтаксис:
MATCH(lookup_value,lookup_array,)
ПОИСКПОЗ(искомое_значение;просматриваемый_массив;[тип_сопоставления])
На первый взгляд, польза от функции ПОИСКПОЗ вызывает сомнение. Кому нужно знать положение элемента в диапазоне? Мы хотим знать значение этого элемента!
Позвольте напомнить, что относительное положение искомого значения (т.е. номер строки и/или столбца) – это как раз то, что мы должны указать для аргументов row_num (номер_строки) и/или column_num (номер_столбца) функции INDEX (ИНДЕКС). Как Вы помните, функция ИНДЕКС может возвратить значение, находящееся на пересечении заданных строки и столбца, но она не может определить, какие именно строка и столбец нас интересуют.
Теперь, когда Вам известна базовая информация об этих двух функциях, полагаю, что уже становится понятно, как функции ПОИСКПОЗ и ИНДЕКС могут работать вместе. ПОИСКПОЗ определяет относительную позицию искомого значения в заданном диапазоне ячеек, а ИНДЕКС использует это число (или числа) и возвращает результат из соответствующей ячейки.
Ещё не совсем понятно? Представьте функции ИНДЕКС и ПОИСКПОЗ в таком виде:
INDEX(,(MATCH (искомое значение
,столбец в котором ищем
,0))
=ИНДЕКС(столбец из которого извлекаем
;(ПОИСКПОЗ(искомое значение
;столбец в котором ищем
;0))
Думаю, ещё проще будет понять на примере. Предположим, у Вас есть вот такой список столиц государств:
Давайте найдём население одной из столиц, например, Японии, используя следующую формулу:
INDEX($D$2:$D$10,MATCH("Japan",$B$2:$B$10,0))
=ИНДЕКС($D$2:$D$10;ПОИСКПОЗ("Japan";$B$2:$B$10;0))
Теперь давайте разберем, что делает каждый элемент этой формулы:
INDEX($D$2:$D$10,3)
=ИНДЕКС($D$2:$D$10;3)
Формула говорит примерно следующее: ищи в ячейках от D2 до D10 и извлеки значение из третьей строки, то есть из ячейки D4 , так как счёт начинается со второй строки.
Вот такой результат получится в Excel:
Важно! Количество строк и столбцов в массиве, который использует функция INDEX (ИНДЕКС), должно соответствовать значениям аргументов row_num (номер_строки) и column_num (номер_столбца) функции MATCH (ПОИСКПОЗ). Иначе результат формулы будет ошибочным.
Стоп, стоп… почему мы не можем просто использовать функцию VLOOKUP (ВПР)? Есть ли смысл тратить время, пытаясь разобраться в лабиринтах ПОИСКПОЗ и ИНДЕКС ?
VLOOKUP("Japan",$B$2:$D$2,3)
=ВПР("Japan";$B$2:$D$2;3)
В данном случае – смысла нет! Цель этого примера – исключительно демонстрационная, чтобы Вы могли понять, как функции ПОИСКПОЗ и ИНДЕКС работают в паре. Последующие примеры покажут Вам истинную мощь связки ИНДЕКС и ПОИСКПОЗ , которая легко справляется с многими сложными ситуациями, когда ВПР оказывается в тупике.
Решая, какую формулу использовать для вертикального поиска, большинство гуру Excel считают, что ИНДЕКС /ПОИСКПОЗ намного лучше, чем ВПР . Однако, многие пользователи Excel по-прежнему прибегают к использованию ВПР , т.к. эта функция гораздо проще. Так происходит, потому что очень немногие люди до конца понимают все преимущества перехода с ВПР на связку ИНДЕКС и ПОИСКПОЗ , а тратить время на изучение более сложной формулы никто не хочет.
1. Поиск справа налево. Как известно любому грамотному пользователю Excel, ВПР не может смотреть влево, а это значит, что искомое значение должно обязательно находиться в крайнем левом столбце исследуемого диапазона. В случае с ПОИСКПОЗ /ИНДЕКС , столбец поиска может быть, как в левой, так и в правой части диапазона поиска. Пример: покажет эту возможность в действии.
2. Безопасное добавление или удаление столбцов. Формулы с функцией ВПР перестают работать или возвращают ошибочные значения, если удалить или добавить столбец в таблицу поиска. Для функции ВПР любой вставленный или удалённый столбец изменит результат формулы, поскольку синтаксис ВПР требует указывать весь диапазон и конкретный номер столбца, из которого нужно извлечь данные.
Например, если у Вас есть таблица A1:C10 , и требуется извлечь данные из столбца B , то нужно задать значение 2 для аргумента col_index_num (номер_столбца) функции ВПР , вот так:
VLOOKUP("lookup value",A1:C10,2)
=ВПР("lookup value";A1:C10;2)
Если позднее Вы вставите новый столбец между столбцами A и B , то значение аргумента придется изменить с 2 на 3 , иначе формула возвратит результат из только что вставленного столбца.
Используя ПОИСКПОЗ /ИНДЕКС , Вы можете удалять или добавлять столбцы к исследуемому диапазону, не искажая результат, так как определен непосредственно столбец, содержащий нужное значение. Действительно, это большое преимущество, особенно когда работать приходится с большими объёмами данных. Вы можете добавлять и удалять столбцы, не беспокоясь о том, что нужно будет исправлять каждую используемую функцию ВПР .
3. Нет ограничения на размер искомого значения. Используя ВПР , помните об ограничении на длину искомого значения в 255 символов, иначе рискуете получить ошибку #VALUE! (#ЗНАЧ!). Итак, если таблица содержит длинные строки, единственное действующее решение – это использовать ИНДЕКС /ПОИСКПОЗ .
Предположим, Вы используете вот такую формулу с ВПР , которая ищет в ячейках от B5 до D10 значение, указанное в ячейке A2 :
VLOOKUP(A2,B5:D10,3,FALSE)
=ВПР(A2;B5:D10;3;ЛОЖЬ)
Формула не будет работать, если значение в ячейке A2 длиннее 255 символов. Вместо неё Вам нужно использовать аналогичную формулу ИНДЕКС /ПОИСКПОЗ :
INDEX(D5:D10,MATCH(TRUE,INDEX(B5:B10=A2,0),0))
=ИНДЕКС(D5:D10;ПОИСКПОЗ(ИСТИНА;ИНДЕКС(B5:B10=A2;0);0))
4. Более высокая скорость работы. Если Вы работаете с небольшими таблицами, то разница в быстродействии Excel будет, скорее всего, не заметная, особенно в последних версиях. Если же Вы работаете с большими таблицами, которые содержат тысячи строк и сотни формул поиска, Excel будет работать значительно быстрее, при использовании ПОИСКПОЗ и ИНДЕКС вместо ВПР . В целом, такая замена увеличивает скорость работы Excel на 13% .
Влияние ВПР на производительность Excel особенно заметно, если рабочая книга содержит сотни сложных формул массива, таких как ВПР+СУММ . Дело в том, что проверка каждого значения в массиве требует отдельного вызова функции ВПР . Поэтому, чем больше значений содержит массив и чем больше формул массива содержит Ваша таблица, тем медленнее работает Excel.
С другой стороны, формула с функциями ПОИСКПОЗ и ИНДЕКС просто совершает поиск и возвращает результат, выполняя аналогичную работу заметно быстрее.
Теперь, когда Вы понимаете причины, из-за которых стоит изучать функции ПОИСКПОЗ и ИНДЕКС , давайте перейдём к самому интересному и увидим, как можно применить теоретические знания на практике.
Любой учебник по ВПР твердит, что эта функция не может смотреть влево. Т.е. если просматриваемый столбец не является крайним левым в диапазоне поиска, то нет шансов получить от ВПР желаемый результат.
Функции ПОИСКПОЗ и ИНДЕКС в Excel гораздо более гибкие, и им все-равно, где находится столбец со значением, которое нужно извлечь. Для примера, снова вернёмся к таблице со столицами государств и населением. На этот раз запишем формулу ПОИСКПОЗ /ИНДЕКС , которая покажет, какое место по населению занимает столица России (Москва).
Как видно на рисунке ниже, формула отлично справляется с этой задачей:
INDEX($A$2:$A$10,MATCH("Russia",$B$2:$B$10,0))
Теперь у Вас не должно возникать проблем с пониманием, как работает эта формула:
MATCH("Russia",$B$2:$B$10,0))
=ПОИСКПОЗ("Russia";$B$2:$B$10;0))
INDEX($A$2:$A$10;MATCH("Russia";$B$2:$B$10;0))
=ИНДЕКС($A$2:$A$10;ПОИСКПОЗ("Russia";$B$2:$B$10;0))
Подсказка: Правильным решением будет всегда использовать абсолютные ссылки для ИНДЕКС и ПОИСКПОЗ , чтобы диапазоны поиска не сбились при копировании формулы в другие ячейки.
Вы можете вкладывать другие функции Excel в ИНДЕКС и ПОИСКПОЗ , например, чтобы найти минимальное, максимальное или ближайшее к среднему значение. Вот несколько вариантов формул, применительно к таблице из :
1. MAX (МАКС). Формула находит максимум в столбце D C той же строки:
INDEX($C$2:$C$10,MATCH(MAX($D$2:I$10),$D$2:D$10,0))
=ИНДЕКС($C$2:$C$10;ПОИСКПОЗ(МАКС($D$2:I$10);$D$2:D$10;0))
Результат: Beijing
2. MIN (МИН). Формула находит минимум в столбце D и возвращает значение из столбца C той же строки:
INDEX($C$2:$C$10,MATCH(MIN($D$2:I$10),$D$2:D$10,0))
=ИНДЕКС($C$2:$C$10;ПОИСКПОЗ(МИН($D$2:I$10);$D$2:D$10;0))
Результат: Lima
3. AVERAGE (СРЗНАЧ). Формула вычисляет среднее в диапазоне D2:D10 , затем находит ближайшее к нему и возвращает значение из столбца C той же строки:
INDEX($C$2:$C$10,MATCH(AVERAGE($D$2:D$10),$D$2:D$10,1))
=ИНДЕКС($C$2:$C$10;ПОИСКПОЗ(СРЗНАЧ($D$2:D$10);$D$2:D$10;1))
Результат: Moscow
Используя функцию СРЗНАЧ в комбинации с ИНДЕКС и ПОИСКПОЗ , в качестве третьего аргумента функции ПОИСКПОЗ чаще всего нужно будет указывать 1 или -1 в случае, если Вы не уверены, что просматриваемый диапазон содержит значение, равное среднему. Если же Вы уверены, что такое значение есть, – ставьте 0 для поиска точного совпадения.
В нашем примере значения в столбце D упорядочены по возрастанию, поэтому мы используем тип сопоставления 1 . Формула ИНДЕКС /ПОИСКПО З возвращает “Moscow”, поскольку величина населения города Москва – ближайшее меньшее к среднему значению (12 269 006).
Эта формула эквивалентна двумерному поиску ВПР и позволяет найти значение на пересечении определённой строки и столбца.
В этом примере формула ИНДЕКС /ПОИСКПОЗ будет очень похожа на формулы, которые мы уже обсуждали в этом уроке, с одним лишь отличием. Угадайте каким?
Как Вы помните, синтаксис функции INDEX (ИНДЕКС) позволяет использовать три аргумента:
INDEX(array,row_num,)
ИНДЕКС(массив;номер_строки;[номер_столбца])
И я поздравляю тех из Вас, кто догадался!
Начнём с того, что запишем шаблон формулы. Для этого возьмём уже знакомую нам формулу ИНДЕКС /ПОИСКПОЗ и добавим в неё ещё одну функцию ПОИСКПОЗ , которая будет возвращать номер столбца.
INDEX(Ваша таблица
,(MATCH(,столбец, в котором искать
,0)),(MATCH(,строка в которой искать
,0))
=ИНДЕКС(Ваша таблица
,(MATCH(значение для вертикального поиска
,столбец, в котором искать
,0)),(MATCH(значение для горизонтального поиска
,строка в которой искать
,0))
Обратите внимание, что для двумерного поиска нужно указать всю таблицу в аргументе array (массив) функции INDEX (ИНДЕКС).
А теперь давайте испытаем этот шаблон на практике. Ниже Вы видите список самых населённых стран мира. Предположим, наша задача узнать население США в 2015 году.
Хорошо, давайте запишем формулу. Когда мне нужно создать сложную формулу в Excel с вложенными функциями, то я сначала каждую вложенную записываю отдельно.
Итак, начнём с двух функций ПОИСКПОЗ , которые будут возвращать номера строки и столбца для функции ИНДЕКС :
MATCH($H$2,$B$1:$B$11,0)
=ПОИСКПОЗ($H$2;$B$1:$B$11;0)
4 , поскольку “USA” – это 4-ый элемент списка в столбце B (включая заголовок).
MATCH($H$3,$A$1:$E$1,0)
=ПОИСКПОЗ($H$3;$A$1:$E$1;0)
Результатом этой формулы будет 5 , поскольку “2015” находится в 5-ом столбце.
Теперь вставляем эти формулы в функцию ИНДЕКС и вуаля:
INDEX($A$1:$E$11,MATCH($H$2,$B$1:$B$11,0),MATCH($H$3,$A$1:$E$1,0))
=ИНДЕКС($A$1:$E$11;ПОИСКПОЗ($H$2;$B$1:$B$11;0);ПОИСКПОЗ($H$3;$A$1:$E$1;0))
Если заменить функции ПОИСКПОЗ на значения, которые они возвращают, формула станет легкой и понятной:
INDEX($A$1:$E$11,4,5))
=ИНДЕКС($A$1:$E$11;4;5))
Эта формула возвращает значение на пересечении 4-ой строки и 5-го столбца в диапазоне A1:E11 , то есть значение ячейки E4 . Просто? Да!
В учебнике по ВПР мы показывали пример формулы с функцией ВПР для поиска по нескольким критериям . Однако, существенным ограничением такого решения была необходимость добавлять вспомогательный столбец. Хорошая новость: формула ИНДЕКС /ПОИСКПОЗ может искать по значениям в двух столбцах, без необходимости создания вспомогательного столбца!
Предположим, у нас есть список заказов, и мы хотим найти сумму по двум критериям – имя покупателя (Customer) и продукт (Product). Дело усложняется тем, что один покупатель может купить сразу несколько разных продуктов, и имена покупателей в таблице на листе Lookup table расположены в произвольном порядке.
Вот такая формула ИНДЕКС /ПОИСКПОЗ решает задачу:
{=INDEX("Lookup table"!$A$2:$C$13,MATCH(1,(A2="Lookup table"!$A$2:$A$13)*
(B2="Lookup table"!$B$2:$B$13),0),3)}
{=ИНДЕКС("Lookup table"!$A$2:$C$13;ПОИСКПОЗ(1;(A2="Lookup table"!$A$2:$A$13)*
(B2="Lookup table"!$B$2:$B$13);0);3)}
Эта формула сложнее других, которые мы обсуждали ранее, но вооруженные знанием функций ИНДЕКС и ПОИСКПОЗ Вы одолеете ее. Самая сложная часть – это функция ПОИСКПОЗ , думаю, её нужно объяснить первой.
MATCH(1,(A2="Lookup table"!$A$2:$A$13),0)*(B2="Lookup table"!$B$2:$B$13)
ПОИСКПОЗ(1;(A2="Lookup table"!$A$2:$A$13);0)*(B2="Lookup table"!$B$2:$B$13)
В формуле, показанной выше, искомое значение – это 1 , а массив поиска – это результат умножения. Хорошо, что же мы должны перемножить и почему? Давайте разберем все по порядку:
Теперь понимаете, почему мы задали 1 , как искомое значение? Правильно, чтобы функция ПОИСКПОЗ возвращала позицию только, когда оба критерия выполняются.
Обратите внимание: В этом случае необходимо использовать третий не обязательный аргумент функции ИНДЕКС . Он необходим, т.к. в первом аргументе мы задаем всю таблицу и должны указать функции, из какого столбца нужно извлечь значение. В нашем случае это столбец C (Sum), и поэтому мы ввели 3 .
И, наконец, т.к. нам нужно проверить каждую ячейку в массиве, эта формула должна быть формулой массива. Вы можете видеть это по фигурным скобкам, в которые она заключена. Поэтому, когда закончите вводить формулу, не забудьте нажать Ctrl+Shift+Enter .
Если всё сделано верно, Вы получите результат как на рисунке ниже:
Как Вы, вероятно, уже заметили (и не раз), если вводить некорректное значение, например, которого нет в просматриваемом массиве, формула ИНДЕКС /ПОИСКПОЗ сообщает об ошибке #N/A (#Н/Д) или #VALUE! (#ЗНАЧ!). Если Вы хотите заменить такое сообщение на что-то более понятное, то можете вставить формулу с ИНДЕКС и ПОИСКПОЗ в функцию ЕСЛИОШИБКА .
Синтаксис функции ЕСЛИОШИБКА очень прост:
IFERROR(value,value_if_error)
ЕСЛИОШИБКА(значение;значение_если_ошибка)
Где аргумент value (значение) – это значение, проверяемое на предмет наличия ошибки (в нашем случае – результат формулы ИНДЕКС /ПОИСКПОЗ ); а аргумент value_if_error (значение_если_ошибка) – это значение, которое нужно возвратить, если формула выдаст ошибку.
Например, Вы можете вставить в функцию ЕСЛИОШИБКА вот таким образом:
IFERROR(INDEX($A$1:$E$11,MATCH($G$2,$B$1:$B$11,0),MATCH($G$3,$A$1:$E$1,0)),
"Совпадений не найдено. Попробуйте еще раз!") =ЕСЛИОШИБКА(ИНДЕКС($A$1:$E$11;ПОИСКПОЗ($G$2;$B$1:$B$11;0);ПОИСКПОЗ($G$3;$A$1:$E$1;0));
"Совпадений не найдено. Попробуйте еще раз!")
И теперь, если кто-нибудь введет ошибочное значение, формула выдаст вот такой результат:
Если Вы предпочитаете в случае ошибки оставить ячейку пустой, то можете использовать кавычки (“”), как значение второго аргумента функции ЕСЛИОШИБКА . Вот так:
IFERROR(INDEX(массив,MATCH(искомое_значение,просматриваемый_массив,0),"")
ЕСЛИОШИБКА(ИНДЕКС(массив;ПОИСКПОЗ(искомое_значение;просматриваемый_массив;0);"")
Надеюсь, что хотя бы одна формула, описанная в этом учебнике, показалась Вам полезной. Если Вы сталкивались с другими задачами поиска, для которых не смогли найти подходящее решение среди информации в этом уроке, смело опишите свою проблему в комментариях, и мы все вместе постараемся решить её.
Для борьбы с комбинаторным взрывом требуется «комбинаторный лом». Есть два инструмента, позволяющие на практике решать сложные комбинаторные задачи. Первый – это массовое распараллеливание вычислений. И тут важно не только иметь большое количество параллельных процессоров, но и подобрать такой алгоритм, который позволяет распараллелить задачу и загрузить все доступные вычислительные мощности.
Второй инструмент – это принцип ограниченности. Основной метод, использующий принцип ограниченности – это метод «случайных подпространств» . Иногда комбинаторные задачи допускают сильное ограничение исходных условий и при этом сохраняют надежду, что и после этих ограничений в данных сохранится достаточно информации, чтобы можно было найти требуемое решение. Вариантов того, как можно ограничить исходные условия, может быть много. Не все из них могут быть удачными. Но если, все же, вероятность, что удачные варианты ограничений есть, то тогда сложная задача может быть разбита на большое количество ограниченных задач, каждая из которых решается значительно проще исходной.
Комбинируя эти два принципа, можно построить решение и нашей задачи.
В чем смысл этого пространства? Мы предполагаем, что входной сигнал не случаен, а содержит определенные закономерности. Закономерности могут быть двух основных типов. Что-то во входном описании может появляться несколько чаще чем другое. Например, в нашем случае отдельные буквы появляются чаще чем их сочетания. При битовом кодировании это означает, что определенные комбинации битов встречаются, чаще чем другие.
Другой тип закономерностей – это когда кроме входного сигнала есть сопутствующий ему сигнал обучения и что-то, содержащееся во входном сигнале, оказывается связано с чем-то, что содержится в сигнале обучения. В нашем случае активные выходные биты – это реакция на комбинацию определенных входных битов.
Если искать закономерности «в лоб», то есть глядя на весь входной и весь выходной векторы, то не очень понятно, что делать и куда двигаться. Если начинать строить гипотезы на предмет того, что от чего может зависеть, то моментально наступает комбинаторный взрыв. Количество возможных гипотез оказывается чудовищно.
Классический метод, широко используемый в нейронных сетях, - градиентный спуск. Для него важно понять, в какую сторону двигаться. Обычно это несложно, когда выходная цель одна. Например, если мы хотим обучить нейронную сеть написанию цифр, мы показываем ей изображения цифр и указываем, что за цифру она при этом видит. Сети понятно «как и куда спускаться». Если мы будем показывать картинки сразу с несколькими цифрами и называть все эти цифры одновременно, не указывая, где что, то ситуация становится значительно сложнее.
Когда создаются точки комбинаторного пространства с сильно ограниченным «обзором» (случайные подпространства), то оказывается, что некоторым точкам может повезти и они увидят закономерность если не совсем чистой, то, по крайней мере, в значительно очищенном виде. Такой ограниченный взгляд позволит, например, провести градиентный спуск и получить уже чистую закономерность. Вероятность для отдельной точки наткнуться на закономерность может быть не очень высока, но всегда можно подобрать такое количество точек, чтобы гарантировать себе, что всякая закономерность «где-то да всплывет».
Конечно, если делать размеры точек слишком узкими, то есть количество битов в точках выбирать приблизительно равным тому, сколько битов ожидается в закономерности, то размеры комбинаторного пространства начнут стремиться к количеству вариантов полного перебора возможных гипотез, что возвращает нас к комбинаторному взрыву. Но, к счастью, можно увеличивать обзор точек, снижая их общее количество. Это снижение не дается бесплатно, комбинаторика «переносится в точки», но до определенного момента это не смертельно.
Создадим выходной вектор. Просто сведем в каждый бит выхода несколько точек комбинаторного пространства. Какие это будут точки выберем случайным образом. Количество точек, попадающих в один бит, будет соответствовать тому, во сколько раз мы хотим уменьшить комбинаторное пространство. Такой вектор выхода будет хэш-функцией для вектора состояния комбинаторного пространства. О том, как это состояние считается, мы поговорим чуть позже.
В общем случае, например, как показано на рисунке выше, размер входа и выхода могут быть различны. В нашем примере с перекодированием строк эти размеры совпадают.
Будем называть запись номера одного бита рецептором к этому биту. Это подразумевает, что рецептор следит за состоянием соответствующего бита входного вектора и реагирует, когда там появляется единица.
Набор рецепторов будем называть кластером рецепторов или рецептивным кластером. Когда предъявляется входной вектор, рецепторы кластера реагируют, если в соответствующих позициях вектора стоят единицы. Для кластера можно подсчитать количество сработавших рецепторов.
Так как информация у нас кодируется не отдельными битами, а кодом, то от того, сколько битов мы возьмем в кластер, зависит точность, с которой мы сформулируем гипотезу. К статье приложен текст программы, решающий задачу с перекодировкой строк. По умолчанию в программе заданы следующие настройки:
При таких настройках практически каждый бит, который есть в коде одной буквы, повторяется в коде другой буквы, а то и в кодах нескольких букв. Поэтому одиночный рецептор не может надежно указать на закономерность. Два рецептора указывают на букву значительно лучше, но и они могут указывать на сочетание совсем других букв. Можно ввести некий порог длины, начиная с которого можно достаточно достоверно судить о том, есть ли в кластере нужный нам фрагмент кода.
Введем минимальный порог по количеству рецепторов, необходимых для формирования гипотезы (в примере он равен 6). Приступим к обучению. Будем подавать исходный код и код, который мы хотим получить на выходе. Для исходного кода легко подсчитать, сколько активных битов попадает в каждую из точек комбинаторного пространства. Выберем только те точки, которые подключены к активным битам выходного кода и у которых количество попавших в нее активных битов входного кода окажется не меньше порога создания кластера. В таких точках создадим кластеры рецепторов с соответствующими наборами битов. Сохраним эти кластеры именно в тех точках, где они были созданы. Чтобы не создавать дубликаты, предварительно проверим, что эти кластеры уникальны для этих точек и точки еще не содержат точно таких же кластеров.
Скажем то же другими словами. По выходному вектору мы знаем, какие биты должны быть активны. Соответственно, мы можем выбрать связанные с ними точки комбинаторного пространства. Для каждой такой точки мы можем сформулировать гипотезу о том, что то, что она сейчас видит на входном векторе, – это и есть закономерность, которая отвечает за активность того бита, к которому эта точка подключена. Мы не можем сказать по одному примеру, верна или нет эта гипотеза, но выдвинуть предположение нам никто не мешает.
Возможны разные подходы к решению поставленной задачи. Опишу один из них, не утверждая, что он лучший. Я перебрал множество вариантов, этот подкупил меня качеством работы и простотой, но это не значит, что его нельзя улучшить.
Удобно воспринимать кластеры, как автономные вычислители. Если каждый кластер может проверять свою гипотезу и принимать решения независимо от остальных, то это очень хорошо для потенциального распараллеливания вычислений. Каждый кластер рецепторов после создания начинает самостоятельную жизнь. Он следит за поступающими сигналами, накапливает опыт, меняет себя и принимает если необходимо решение о самоликвидации.
Кластер – это набор битов, про который мы предположили, что внутри него сидит закономерность, связанная со срабатыванием того выходного бита, к которому подключена точка, содержащая этот кластер. Если закономерность есть, то скорее всего она затрагивает только часть битов, причем мы заранее не знаем, какую. Поэтому будем фиксировать все моменты, когда в кластере срабатывает существенное количество рецепторов (в примере не менее 4). Возможно, что в эти моменты закономерность, если она есть, проявляет себя. Когда накопится определенная статистика, мы сможем попробовать определить, есть ли в таких частичных срабатываниях кластера что-то закономерное или нет.
Пример статистики показан на рисунке ниже. Плюс в начале строки показывает, что в момент частичного срабатывания кластера выходной бит также был активен. Биты кластера сформированы из соответствующих битов входного вектора.
Что нас должно интересовать в этой статистике? Нам важно, какие биты чаще других срабатывают совместно. Не спутайте это с самыми частыми битами. Если посчитать для каждого бита частоту его появления и взять самые распространенные биты, то это будет усреднение, которое совсем не то, что нам надо. Если в точке сошлись несколько устойчивых закономерностей, то при усреднении получится средняя между ними «не закономерность». В нашем примере, видно, что 1,2 и 4 строки похожи между собой, также похожи 3,4 и 6 строки. Нам надо выбрать одну из этих закономерностей, желательно самую сильную, и очистить ее от лишних битов.
Наиболее распространенная комбинация, которая проявляется как совместное срабатывание определенных битов, является для этой статистики . Чтобы вычислить главную компоненту, можно воспользоваться фильтром Хебба. Для этого можно задать вектор с единичными начальными весами. Затем получать активность кластера, перемножая вектор весов на текущее состояние кластера. А затем сдвигать веса в сторону текущего состояния тем сильнее, чем выше эта активность. Чтобы веса не росли бесконтрольно, после изменения весов их надо нормировать, например, на максимальное значение из вектора весов.
Такая процедура повторяется для всех имеющихся примеров. В результате вектор весов все больше приближается к главной компоненте. Если тех примеров, что есть, не хватает, чтобы сойтись, то можно несколько раз повторить процесс на тех же примерах, постепенно уменьшая скорость обучения.
Основная идея в том, что по мере приближения к главной компоненте кластер начинает все сильнее реагировать на образцы, похожие на нее и все меньше на остальные, за счет этого обучение в нужную сторону идет быстрее, чем «плохие» примеры пытаются его испортить. Результат работы такого алгоритма после нескольких итераций показан ниже.
Если теперь подрезать кластер, то есть оставить только те рецепторы, у которых высокие веса (например, выше 0.75), то мы получим закономерность, очищенную от лишних шумовых битов. Эту процедуру можно повторить несколько раз по мере накопления статистики. В результате можно понять, есть ли в кластере какая-либо закономерность, или мы собрали вместе случайный набор битов. Если закономерности нет, то в результате подрезания кластера останется слишком короткий фрагмент. В этом случае такой кластер можно удалить как несостоявшуюся гипотезу.
Кроме подрезки кластера надо следить за тем, чтобы была поймана именно нужная закономерность. В исходной строке смешаны коды нескольких букв, каждый из них является закономерностью. Любой из этих кодов может быть «пойман» кластером. Но нас интересует код только той буквы, которая влияет на формирование выходного бита. По этой причине большинство гипотез будут ложными и их необходимо отвергнуть. Это можно сделать по тем критериям, что частичное или даже полное срабатывание кластера слишком часто будет не совпадать с активностью нужного выходного бита. Такие кластеры подлежат удалению. Процесс такого контроля и удаления лишних кластеров вместе с их «подрезкой» можно назвать консолидацией памяти.
Процесс накопления новых кластеров достаточно быстрый, каждый новый опыт формирует несколько тысяч новых кластеров-гипотез. Обучение целесообразно проводить этапами с перерывом на «сон». Когда кластеров создается критически много, требуется перейти в режим «холостой» работы. В этом режиме прокручивается ранее запомненный опыт. Но при этом не создается новых гипотез, а только идет проверка старых. В результате «сна» удается удалить огромный процент ложных гипотез и оставить только гипотезы, прошедшие проверку. После «сна» комбинаторное пространство не только оказывается очищено и готово к приему новой информации, но и гораздо увереннее ориентируется в том, что было выучено «вчера».
Далее из этой активности сформируем выход как хеш комбинаторного пространства. При этом будем учитывать, что чем длиннее кластер, тем выше шанс, что мы поймали закономерность. Для коротких кластеров есть вероятность, что сочетание битов возникло случайно как комбинация других понятий. Для повышения помехоустойчивости воспользуемся идеей бустинга, то есть будем требовать, чтобы для коротких кластеров активация выходного бита происходила только когда таких срабатываний будет несколько. В случае же длинных кластеров будем считать, что достаточно и единичного срабатывания. Это можно представить через потенциал, который возникает при срабатывании кластеров. Этот потенциал тем выше, чем длиннее кластер. Потенциалы точек, подключенных к одному выходному биту, складываются. Если итоговый потенциал превышает определенный порог, то бит активируется.
После некоторого обучения на выходе начинает воспроизводиться часть, совпадающая с тем, что мы хотим получить (рисунок ниже).
Постепенно выход комбинаторного пространства начинает все лучше воспроизводить требуемый код выхода. После нескольких тысяч шагов обучения выход воспроизводится с достаточно высокой точностью (рисунок ниже).
Чтобы наглядно представить, как это все работает, я записал видео с процессом обучения. Кроме того, возможно, мои пояснения помогут лучше разобраться во всей этой кухне.
Несложно придумать правила проверки тормозных гипотез и запустить консолидацию тормозных рецептивных кластеров.
Так как тормозные кластеры создаются в конкретных точках, то они влияют не на блокировку выходного бита вообще, а на блокировку его срабатывания от правил, обнаруженных именно в этой точке. Можно усложнить архитектуру связей и ввести тормозные правила, общие для группы точек или для всех точек, подключенных к выходному биту. Похоже, что можно придумать еще много чего интересного, но пока остановимся на описанной простой модели.
Этот метод начинается с идеи «случайных подпространств» . Если в исходных данных слишком много переменных и эти переменные слабо, но коррелированы, то на полном объеме данных становится трудно вычленить отдельные закономерности. В таком случае можно создать подпространства, в которых будут ограничены как используемые переменные, так и обучающие примеры. То есть каждое подпространство будет содержать только часть входных данных, и эти данные будут представлены не всеми переменными, а их случайным ограниченным набором. Для некоторых из этих подпространств шансы обнаружить закономерность, плохо видимую на полном объеме данных, значительно повышаются.
Затем в каждом подпространстве на ограниченном наборе переменных и обучающих примеров производится обучение решающего дерева . Решающее дерево – это древовидная структура (рисунок ниже), в узлах которой происходит проверка входных переменных (атрибутов). По результатам проверки условий в узлах определяется путь от вершины к терминальному узлу, который принято называть листом дерева. В листе дерева находится результат, который может быть значением какой-либо величины или номером класса.
Для решающих деревьев существуют различные алгоритмы обучения, которые позволяют построить дерево с более-менее оптимальными атрибутами в его узлах.
На завершающем этапе применяется идея бустинга . Решающие деревья формируют комитет для голосования. На основании коллективного мнения создается наиболее правдоподобный ответ. Главное достоинство бустинга – это возможность при объединении множества «плохих» алгоритмов (результат которых лишь немного лучше случайного) получить сколь угодно «хороший» итоговый результат.
В нашем алгоритме, эксплуатирующем комбинаторное пространство и кластеры рецепторов, используются те же фундаментальные идеи, что и в методе случайного леса. Поэтому нет ничего удивительного, что наш алгоритм работает и выдает неплохой результат.
На мембране нейрона располагается множество различных рецепторов. Большинство этих рецепторов находится в «свободном плавании». Мембрана создает для рецепторов среду, в которой они могут свободно перемещаться, легко меняя свое положение на поверхности нейрона (Sheng, M., Nakagawa, T., 2002) (Tovar K. R.,Westbrook G. L., 2002).
В классическом подходе на причинах такой «свободы» рецепторов обычно акцент не делается. Когда синапс усиливает свою чувствительность, это сопровождается перемещением рецепторов из внесинаптического пространства в синаптическую щель (Malenka R.C., Nicoll R.A., 1999). Этот факт негласно воспринимается как оправдание подвижности рецепторов.
В нашей модели можно предположить, что основная причина подвижности рецепторов – это необходимость «на лету» формировать из них кластеры. То есть картина выглядит следующим образом. По мембране свободно дрейфуют самые разные рецепторы, чувствительные к различным нейромедиаторам. Информационный сигнал, возникший в миниколонке, вызывает выброс нейромедиаторов аксонными окончаниями нейронов и астроцитами. В каждом синапсе, где испускаются нейромедиаторы, кроме основного нейромедиатора присутствует своя уникальная добавка, которая идентифицирует именно этот синапс. Нейромедиаторы выплескиваются из синаптических щелей в окружающее пространство, за счет чего в каждом месте дендрита (точках комбинаторного пространства) возникает специфический коктейль нейромедиаторов (ингредиенты коктейля указывают на биты, попадающие в точку). Те свободно блуждающие рецепторы, которые находят в этот момент свой нейромедиатор в этом коктейле (рецепторы конкретных битов входного сигнала), переходят в новое состояние – состояние поиска. В этом состоянии у них есть небольшое время (до того момента, пока не наступит следующий такт), за которое они могут встретить другие «активные» рецепторы и создать общий кластер (кластер рецепторов, чувствительных к определенному сочетанию битов).
Метаботропные рецепторы, а речь идет о них, имеют достаточно сложную форму (рисунок ниже). Они состоят из семи трансмембранных доменов, которые соединены петлями. Кроме того, у них есть два свободных конца. За счет разных по знаку электростатических зарядов свободные концы могут через мембрану «залипать» друг на друга. За счет таких соединений рецепторы и объединяются в кластеры.
После объединения начинается совместная жизнь рецепторов в кластере. Можно предположить, что положение рецепторов относительно друг друга может меняться в широких пределах и кластер может принимать причудливые формы. Если допустить, что рецепторы, срабатывающие совместно, будут стремиться занять место ближе друг к другу, например, за счет электростатических сил, то получится интересное следствие. Чем ближе будут оказываться такие «совместные» рецепторы, тем сильнее будет их совместное притяжение. Сблизившись они начнут усиливать влияние друг друга. Такое поведение воспроизводит поведение фильтра Хебба, который выделяет первую главную компоненту. Чем точнее фильтр настраивается на главную компоненту, тем сильнее оказывается его реакция, когда она появляется в примере. Таким образом, если после ряда итераций совместно срабатывающие рецепторы окажутся вместе в условном «центре» кластера, а «лишние» рецепторы на удалении, на его краях, то, в принципе, такие «лишние» рецепторы могут в какой-то момент самоликвидироваться, то есть просто оторваться от кластера. И тогда мы получим поведение кластера, аналогичное тому, что описано выше в нашей вычислительной модели.
Кластеры, которые прошли консолидацию, могут переместиться куда-нибудь «в тихую гавань», например, в синаптическую щель. Там существует постсинаптическое уплотнение, за которое кластеры рецепторов могут якориться, теряя уже ненужную им подвижность. Поблизости от них будут находиться ионные каналы, которыми они смогут управлять через G-белки. Теперь эти рецепторы начнут влиять на формирование локального постсинаптического потенциала (потенциала точки).
Локальный потенциал складывается из совместного влияния расположенных рядом активирующих и тормозящих рецепторов. В нашем подходе активирующие отвечают за узнавание закономерностей, призывающих активировать выходной бит, тормозящие за определение закономерностей, которые блокируют действие локальных правил.
Синапсы (точки) расположены на дендритном дереве. Если где-то на этом дереве находится место, где на небольшом участке срабатывает сразу несколько активирующих рецепторов и это не блокируется тормозными рецепторами, то возникает дендритный спайк, который распространяется до тела нейрона и, дойдя до аксонного холмика, вызывает спайк самого нейрона. Дендритное дерево объединяет множество синапсов, замыкая их на один нейрон, что очень похоже на формирование выходного бита комбинаторного пространства.
Объединение сигналов с разных синапсов одного дендритного дерева может быть не простым логическим сложением, а быть сложнее и реализовывать какой-нибудь алгоритм хитрого бустинга.
Напомню, что базовый элемент коры – это кортикальная миниколонка. В миниколонке около ста нейронов расположены друг под другом. При этом они плотно окутаны связями, которые гораздо обильнее внутри миниколонки, чем связи, идущие к соседним миниколонкам. Вся кора мозга – это пространство таких миниколонок. Один нейрон миниколонки может соответствовать одному выходному биту, все нейроны одной кортикальной миниколонки могут быть аналогом выходного бинарного вектора.
Кластеры рецепторов, описанные в этой главе, создают память, ответственную за поиск закономерностей. Ранее мы описывали, как с помощью кластеров рецепторов создать голографическую событийную память. Это два разных типа памяти, выполняющие разные функции, хотя и основанные на общих механизмах.
Можно предположить, что во сне происходит основная работа по расчистке кластеров рецепторов, накопившихся за день. В вычислительной модели мы описали процедуру «холостого» обучения. Старый опыт предъявляется мозгу, не вызывая формирования новых кластеров. Цель – проверка уже существующих гипотез. Такая проверка состоит из двух этапов. Первый - вычисление главной компоненты закономерности и проверка того, что количество битов, отвечающих за нее, достаточно для четкой идентификации. Второй – проверка истинности гипотезы, то есть того, что закономерность оказалась в нужной точке, связанной с нужным выходным битом. Можно предположить, что часть стадий ночного сна связана с такими процедурами.
Все процессы, связанные с изменениями в клетках, сопровождаются экспрессией определенных белков и транскрипционных факторов . Есть белки и факторы про которые показано, что они участвут в формировании нового опыта. Так вот, оказывается, что их количество сильно увеличивается во время бодрствования и резко уменьшается во время сна.
Увидеть и оценить концентрацию белков можно через окрашивание среза мозговой ткани красителем, избирательно реагирующим на требуемый белок. Подобные наблюдения показали, что наиболее масштабные изменения для белков, связанных с памятью, происходят именно во время сна (Chiara Cirelli, Giulio Tononi, 1998) (Cirelli, 2002) (рисунки ниже).
В такие рассуждения о роли сна хорошо укладывается известная каждому особенность – «утро вечера мудренее». Утром мы гораздо лучше ориентируемся в том, что еще вчера было не особо понятно. Все становится четче и очевиднее. Возможно, что этим мы обязаны именно масштабной расчистке кластеров рецепторов, произошедшей во время сна. Удаляются ложные и сомнительные гипотезы, достоверные проходят консолидацию и начинают активнее участвовать в информационных процессах.
При моделировании было видно, что количество ложных гипотез во многие тысячи раз превышает количество истинных. Так как отличить одни от других можно только временем и опытом, то мозгу не остается ничего другого, кроме как копить всю эту информационную руду в надежде найти в ней со временем граммы радия. При получении нового опыта количество кластеров с гипотезами, требующими проверки, постоянно растет. Количество кластеров, формирующихся за день и содержащих руду, которую еще предстоит обработать, может превышать количество кластеров, отвечающих за кодирование накопленного за всю предыдущую жизнь проверенного опыта. Ресурс мозга по хранению сырых гипотез, требующих проверки должен быть ограничен. Похоже, что за 16 часов дневного бодрствования кластерами рецепторов практически полностью забивается все доступное пространство. Когда наступает этот момент, мозг начинает принуждать нас перейти в режим сна, чтобы позволить ему выполнить консолидацию и расчистить свободное место. Видимо, процесс полной расчистки занимает около 8 часов. Если разбудить нас раньше, то часть кластеров останется необработанной. Отсюда происходит феномен того, что усталость накапливается. Если несколько дней недосыпать, то потом придется наверстывать упущенный сон. В противном случае мозг начинает «аварийно» удалять кластеры, что ни к чему хорошему не приводит, так как лишает нас возможности почерпнуть знания из полученного опыта. Событийная память скорее всего сохранится, но закономерности останутся невыявленными.
Кстати, мой личный совет: не пренебрегайте качественным сном, особенно если вы учитесь. Не пытайтесь сэкономить на сне, чтобы больше успеть. Сон не менее важен в обучении, чем посещение лекций и повтор материала на практических занятиях. Недаром дети в те периоды развития, когда накопление и обобщение информации идет наиболее активно, большую часть времени проводят во сне.
Теперь можно предположить, что каждый кластер рецепторов может работать как автономный вычислительный элемент, выполняя весь цикл вычислений по проверке своей гипотезы. Таких кластеров в одной только кортикальной колонке может быть сотни миллионов. Это значит, что, хотя частоты, с которыми работает мозг, далеки от частот, на которых работают современные компьютеры, тревожиться о быстродействии мозга не стоит. Сотни миллионов кластеров рецепторов, работающих параллельно в каждой миниколонке коры, позволяют успешно решать сложные задачи, находящиеся на границе с комбинаторным взрывом. Чудес не бывет. Но можно научиться ходить по грани.
Допустим ваш отчет содержит таблицу с большим количеством данных на множество столбцов. Проводить визуальный анализ таких таблиц крайне сложно. А одним из заданий по работе с отчетом является – анализ данных относительно заголовков строк и столбцов касающихся определенного месяца. На первый взгляд это весьма простое задание, но его нельзя решить, используя одну стандартную функцию. Да, конечно можно воспользоваться инструментом: «ГЛАВНАЯ»-«Редактирование»-«Найти» CTRL+F, чтобы вызвать окно поиска значений на листе Excel. Или же создать для таблицы правило условного форматирования. Но тогда нельзя будет выполнить дальнейших вычислений с полученными результатами. Поэтому необходимо создать и правильно применить соответствующую формулу.
Схема решения задания выглядит примерно таким образом:
Фактически необходимо выполнить поиск координат в Excel. Для чего это нужно? Достаточно часто нам нужно получить координаты таблицы по значению. Немного напоминает обратный анализ матрицы. Конкретный пример в двух словах выглядит примерно так. Поставленная цель в цифрах является исходным значением, нужно определить кто и когда наиболее приближен к этой цели. Для примера используем простую матрицу данных с отчетом по количеству проданных товаров за три квартала, как показано ниже на рисунке. Важно, чтобы все числовые показатели совпадали. Если нет желания вручную создавать и заполнять таблицу Excel с чистого листа, то в конце статьи можно скачать уже с готовым примером.
Последовательно рассмотрим варианты решения разной сложности, а в конце статьи – финальный результат.
Сначала научимся получать заголовки столбцов таблицы по значению. Для этого выполните следующие действия:
Теперь получим номер строки для этого же значения (5277). Для этого в ячейку C3 введите следующую формулу:
После ввода формулы для подтверждения снова нажимаем комбинацию клавиш CTRL+SHIFT+Enter и получаем результат:
Формула вернула номер 9 – нашла заголовок строки листа по соответствующему значению таблицы. В результате мы имеем полный адрес значения D9.
Теперь научимся получать по значению координаты не целого листа, а текущей таблицы. Одним словом, нам нужно найти по значению 5277 вместо D9 получить заголовки:
Чтобы решить данную задачу будем использовать формулу с уже полученными значениями в ячейках C2 и C3. Для этого делаем так:
В результате получены внутренние координаты таблицы по значению – Март; Товар 4:
Чтобы проконтролировать наличие дубликатов среди значений таблицы создадим формулу, которая сможет информировать нас о наличии дубликатов и подсчитывать их количество. Для этого в ячейку E2 вводим формулу:
Более того для диапазона табличной части создадим правило условного форматирования:
Как видно при наличии дубликатов формула для заголовков берет заголовок с первого дубликата по горизонтали (с лева на право). А формула для получения названия (номера) строки берет номер с первого дубликата по вертикали (сверху вниз). Для исправления данного решения есть 2 пути:
В данном случаи изменяем формулы либо одну либо другую, но не две сразу. Стоит напомнить о том, что в ячейке С3 должна оставаться старая формула:
Здесь правильно отображаются координаты первого дубликата по вертикали (с верха в низ) – I7 для листа и Август; Товар2 для таблицы. Оставим такой вариант для следующего завершающего примера.
Данная таблица все еще не совершенна. Ведь при анализе нужно точно знать все ее значения. Если введенное число в ячейку B1 формула не находит в таблице, тогда возвращается ошибка – #ЗНАЧ! Идеально было-бы чтобы формула при отсутствии в таблице исходного числа сама подбирала ближайшее значение, которое содержит таблица. Чтобы создать такую программу для анализа таблиц в ячейку F1 введите новую формулу:
После чего следует во всех остальных формулах изменить ссылку вместо B1 должно быть F1! Так же нужно изменить ссылку в условном форматировании. Выберите: «ГЛАВНАЯ»-«Стили»-«Условное форматирование»-«Управление правилами»-«Изменить правило». И здесь в параметрах укажите F1 вместо B1 . Чтобы проверить работу программы, введите в ячейку B1 число которого нет в таблице, например: 8000. Это приведет к завершающему результату:
Теперь можно вводить любое исходное значение, а программа сама подберет ближайшее число, которое содержит таблица. После чего выводит заголовок столбца и название строки для текущего значения. Например, если ввести число 5000 получаем новый результат:
Наша программа в Excel нашла наиболее близкое значение 4965 для исходного – 5000. Такая программа может пригодится для автоматического решения разных аналитических задач при бизнес-планировании, постановки целей, поиска рационального решения и т.п. А полученные строки и столбцы позволяют дальше расширять вычислительные возможности такого рода отчетов с помощью новых формул Excel.
По функциональному программированию, который проводится под эгидой Фонда Поддержки Функционального Программирования ФП(ФП). Традиционно я хотел бы подвести итоги конкурса и рассказать о решении конкурсной задачи при помощи языка программирования Haskell. Так что всех заинтересованных я приглашаю ознакомиться с этой небольшой заметкой.
В качестве задачи на конкурс была предложена задача по поиску закономерностей в ряду проявлений казалось бы «случайного» события. Но как и всё в этом мире чисто случайными являются, видимо, результаты измерения квантовых состояний, так что во всём другом можно найти какие-то закономерности. Так и здесь. Был дан список дат, когда произошло некоторое событие, и предлагалось дать ответы на два вопроса:
Только два конкурсанта смогли предоставить решения. Впрочем, оба они были неправильными, поскольку правильным ответом на первый вопрос является число 24. А вот вторая задача будет обработана в конце года, когда будет явлена статистика по проявлениям событий. Так что приз за первый вопрос остался неразыгранным, а приз за второй вопрос будет предоставлен тому конкурсанту, прогноз которого наберёт больше очков, в следующем году.
Ну а здесь остаётся рассмотреть решение этих задач на языке программирования Haskell.
Прежде всего был определён список проявлений события:
Dates:: dates = ["27.09.2013", "06.10.2013", "23.10.2013", "06.11.2013", "26.11.2013", "27.11.2013", "21.12.2013", "30.12.2013", "06.01.2014", "16.01.2014", "17.01.2014", "21.01.2014", "25.01.2014", "26.01.2014", "05.02.2014", "11.02.2014", "21.02.2014", "02.03.2014", "07.03.2014", "30.03.2014", "08.04.2014", "18.04.2014", "23.04.2014", "27.04.2014", "02.05.2014", "15.05.2014", "17.05.2014", "18.05.2014", "19.05.2014", "20.05.2014", "25.05.2014", "26.05.2014", "28.05.2014"]
Даже беглый взгляд покажет, что в этом списке нет явных закономерностей. Но вот медитирование над ним несколько дней кряду может выявить что-то. Чтобы не предаваться бессмысленной трате времени на медитации, как раз и решено было написать программу для поиска закономерностей в периодах различной длины. Начнём писать эту программу, как это обычно бывает в разработке на функциональных языках программирования, сверху вниз. Вот главная функция программы:
Main:: IO () main = do putStrLn ("В последовательности дат обнаружены " ++ "закономерности в минимальном периоде длиной " ++ show (length findMinimalPeriod) ++ " дней.") revealSequences findMinimalPeriod
Здесь есть вызов двух функций, которые мы рассмотрим далее. Первая, findMinimalPeriod , возвращает период минимальной длины для заданного порога вероятности. Внимательный читатель заметит, что ей не передаётся никаких аргументов, поэтому порог вероятности определён где-то в виде константы. В общем-то, это порочная практика для парадигмы функционального программирования, но иногда в исследовательских целях это помогает быстро достичь результатов. Так что вот определение:
Significance:: Int significance = 5 lowProbability:: Float lowProbability = 0.5 findMinimalPeriod:: [(Int, Float)] findMinimalPeriod = head $ filter (l -> maximum (map snd l) >= lowProbability) $ map process
Константа significance определяет минимальную «высоту» цилиндра, на который наматывается шкала времени (ведь для того, чтобы найти периоды, можно отметить даты проявления события на длинной ленте, которую потом намотать спиралью на цилиндр с заданной длиной окружности, которая определяет период; соответственно закономерности будут выглядеть как вертикальные линии). Ну а константа lowProbability задаёт минимальный порог вероятности проявления события. Сама же функция findMinimalPeriod берёт голову списка, полученного после фильтрации списка на наличие вероятности не менее заданного порога, который (список) получен при помощи обработки (функция process) чисел от 1 до некоторой верхней границы.
Верхняя граница определяется при помощи функции interval , определение которой следующее:
Interval:: Int interval = finish - start where start = stringToDayOfYear $ head dates finish = 365 + stringToDayOfYear (last dates)
Как видно, здесь мы считаем длину интервала, в котором заданы даты проявлений события. Вычитаем из последней даты первую (возможно, что надо было бы прибавить 1). Эта функция не очень хороша, поскольку в ней есть число 365, а это значит, что она не универсальна. Ну да ладно. К тому же, предыдущая функция (findMinimalPeriod) вообще написана из рук вон плохо и может выбросить ошибку времени исполнения из-за отсутствия проверки на пустоту списка, передаваемого в функцию head .
Теперь перейдём к определению функции process:
Process:: Fractional a => Int -> [(Int, a)] process p = map (l -> (fst $ head l, ((/) `on` fromInteger) (sum $ map snd l) (toEnum $ length l))) $ groupBy ((==) `on` fst) $ sortBy (comparing fst) $ map (first (`mod` p) . i -> if i `elem` ds3 then (i, 1) else (i, 0)) where ds1 = map stringToDayOfYear dates ds2 = uncurry (++) $ second (map (+ 365)) $ span (>= head ds1) ds1 ds3 = map (subtract (head ds2)) ds2
Функция получает на вход длину периода, а возвращает список пар (гистограмму), в которых первым элементом является номер дня в периоде, а вторым - частотная вероятность проявления события в этот день. При помощи локальных определений ds1 , ds2 и ds3 строится список последовательных номеров дней проявления события, начиная от первого дня в списке dates . Далее этот список подвергается такой процедуре. Для всех номеров от 1 до номера последней даты проявления события ищется остаток от деления на длину периода. Для всех таких остатков ставится флаг 0, если в соответствующий день проявления события не было, и флаг 1 - если было. Затем список остатков с флагами группируется по остаткам, после чего группы схлопываются в пары вида (номер дня в периоде, вероятность проявления события). Всё.
Тут надо рассмотреть ещё две сервисные функции:
Double:: a -> (a, a) double x = (x, x) stringToDayOfYear:: String -> Int stringToDayOfYear = uncurry (monthAndDayToDayOfYear False) . (read . take 2 . drop 3 *** read . take 2) . double
Про первую и говорить нечего (странно только то, что её определения нет в стандартном модуле Prelude ; хотя это и понятно, поскольку оно настолько тривиально). Вторая функция переводит дату из строкового представления "DD.MM.YYYY" в числовое, принятое в модуле Data.Time.Calendar.MonthDay , при помощи которого обрабатываются даты.
Наконец, определим функцию revealSequences:
RevealSequences:: [(Int, Float)] -> IO () revealSequences ps = do let l = length ps (d1, p1) = maximumBy (comparing snd) ps (d2, p2) = maximumBy (comparing snd) $ delete (d1, p1) ps putStrLn ("Максимальное проявление события (вероятность: " ++ show p1 ++ ") происходит на " ++ show (d1 + 1) ++ "-й день " ++ show l ++ "-дневного периода.") putStrLn ("Второй максимум (вероятность: " ++ show p2 ++ ") происходит на " ++ show (d2 + 1) ++ "-й день.")
Как видно, она просто находит и выводит на экран два пика проявления события в заданном списке (гистограмме). Эта функция реализована исключительно для удобства исследования и уже не имеет отношения к решению поставленной в конкурсе задачи.
Теперь перейдём ко второму вопросу конкурса - прогнозированию дат проявления события до конца года. Надо отметить, что вообще задача прогнозирования является делом неблагодарным. Один вопрос, когда у нас есть чёткая закономерность (хотя бы даже и вероятностная), и можно более или менее применить детерминированную формулу. Совсем другое дело, когда есть некоторое (совсем небольшое) количество значений, на основании которых надо построить возможное будущее. Точек бифуркаций мириады, так что даже допуски и интервальная арифметика не помогут. Тем не менее, можно придумать какой-нибудь метод и попробовать оценить его применимость уже задним умом, когда пройдёт определённый период времени, и мы сможем сравнить навангованные значения с фактически произошедшими.
Поступим здесь именно таким образом. В качестве метода можно предложить такой. Рассмотрим все возможные периоды, начиная от минимального найденного на предыдущем этапе (меньшие него, честно говоря, не вызывают доверия с точки зрения статистической правдоподобности) и заканчивая длиной известного периода наблюдений, делённой на норму допуска («толщину», как мы её назвали ранее). Для каждого из таких периодов получим вероятности проявления событий в каждый день периода, как мы уже научились делать это при помощи функции process . Далее просто найдём среднюю вероятность для каждого дня по всем вероятностям, найденным для каждого рассматриваемого периода.
Именно этот метод реализует следующая функция:
Forecast:: FilePath -> String -> String -> IO () forecast fp sd fd = do let (b, e) = (length findMinimalPeriod, interval `div` significance) writeFile fp $ unlines $ map (((n, q) -> let (m, d) = dayOfYearToMonthAndDay False (n - 365) in prettyShowInt d ++ "." ++ prettyShowInt m ++ ".2014: " ++ prettyShowFloat q) . second (/ toEnum (e - b + 1))) $ foldr1 (zipWith ((d, q1) (_, q2) -> (d, q1 + q2))) $ map getProbabilities where getProbabilities p = let ds = stringToDayOfYear $ head dates fs = 365 + stringToDayOfYear (last dates) d1 = 365 + stringToDayOfYear sd d2 = 365 + stringToDayOfYear fd in drop (interval + (d1 - fs)) $ zipWith (x (_, q) -> (x, q)) $ cycle $ process p leadingZero:: String -> String leadingZero [c] = "0" : [c] leadingZero c = c prettyShowInt i = leadingZero $ show i prettyShowFloat f = let (d, r) = span (/= ".") $ show (f * 100) in leadingZero d ++ take 5 (r ++ cycle "0")
Её определение выглядит несколько монструозно, но ядром вычислений является локальное определение getProbabilities (из названия должно быть понятно, какому шагу метода оно соответствует). Остальное - всего лишь обвязка для вывода полученных значений в файл в заданном условиями конкурса формате.
В общем-то, всё. Теперь осталось только дождаться конца года и сравнить прогноз с фактом.
Руководство пользователя.
NatClass
Наименование операции
Построение классификации и анализа геномных последовательностей.
Условия, при соблюдении которых возможно выполнение операции
Основные действия в требуемой последовательности.
1.
Входными данными для программы являются две выборки последовательностей в формате FASTA : Positive Sequences (выборки геномных последовательностей, Negative Sequences (выборка случайных последовательностей, или контрастных геномных последовательностей).
Для загрузки обучающих данных используется команда меню Source -> Add Positive Sequences (Рис. 1) или кнопка панели инструментов. На экране появляется мастер и предлагает указать имя файла с позитивной/негативной выборкой последовательностей.
В качестве входных данных могут служить файлы проектов, сохраненные ранее с помощью данной программы. В таких файлах проекта могут быть сохранены все данные, которые были загружены или получены на момент сохранения.
2.Установка параметров программы. Запуск процесса генерации закономерностей.
На первой закладке, “ Rules ”, находятся элементы поиска закономерностей (рис. 2). Необходимо задать параметры поиска закономерностей и нажать кнопку “Пуск”.
Параметрами поиска являются:
Confidence interval : минимальный уровень условной вероятности;
Min . Level of CP : порог для значения критерия Фишера;
Size of finish Buffer : количество обнаруженных закономерностей;
Size of Sub Buffers : размер вспомогательного буфера закономерностей.
Также выбирается режим работы: фиксированные позиции (Fixed positions ) или режим скользящего окна (Shift positions ). Последний используется для распознавания вдоль длинной геномной последовательности и требует указать размер окна (Width of scanning frame )
Программа позволяет приостановить процесс генерации закономерностей (нажатием кнопки “Пауза”), или остановить процесс (нажатием кнопки “Стоп”).
Рис. 2. Закладка элементов поиска закономерностей.
По окончании процесса поиска закономерностей программа выдаёт сообщение “Процесс поиска закономерностей успешно завершен”. В итоге найденные закономерности представлены пользователю в порядке их обнаружения (Рис. 3).
Рис. 3 Обнаруженные закономерности.
3. Построение идеальных объектов классов.
Кроме обнаруженных закономерностей, выходными данными программы NatClass так же являются идеальные представители классов. Для их построения служит закладка “ Objects ” программы (рис. 4). Идеальные объекты могут строиться либо по начальным объектам из позитивной обучающей выборки (опция “ original objects ”), либо по закономерностям (“ regularities ”). Также можно выбрать один из трех вариантов алгоритма построения (idealization type ), задавая приоритеты между удалением и добавлением признаков. После построения идеальных объектов, программа соответственно относит объекты обучения к одному из обнаруженных классов, или распознаёт их как принадлежащие к новому классу “ New ”. По аналогии с процессом генерации закономерностей, процесс идеализации можно приостановить (нажатием кнопки “Пауза”), или остановить (нажатием кнопки “Стоп”).
Рис. 4. Закладка элементов построения идеальных объектов.
По окончании процесса поиска закономерностей программа выдаёт сообщение “Процесс идеализации успешно завершен”.
4. Применение полученных закономерностей. Вычисление ошибок распознавания.
Закладка Classes содержит функции обработки полученных выходных данных (Рис. 5).
Здесь доступны следующие функции для анализа результатов счета: классификация контрольных выборок (“ Classification ”), распознавание относительно имеющихся классов (“ Recognition Control Data ”), подсчет ошибок распознавания (“ Recognition Errors Count ”), процедура Bootstrap .
Для загрузки контрольных последовательностей используется команда меню Control -> Add Control Positive .
При подсчете ошибок распознавания программа выдаст оптимальный результат (построит гистограмму), но пользователь может самостоятельно корректировать его, задавая либо порог распознавания (“ Recogn Level ”), либо значение ошибки первого рода (“1 st level error ”).
Рис. 5. Закладка “ Classes ”.
При нажатии правой кнопкой на идеальный объект появляется возможность удалить объект (“ Delete ”, рис. 6), показать объекты класса (“ Show Objects ”, рис. 7), закономерности (“ Show Regularities ”), матрицу предсказания (“ Prediction matrix ”), матрицу распознавания (“ Recognition Matrix ”, рис. 8)
Рис. 6 Операции, производимые программой с идеальным объектом.
Рис. 7 Операция отображения объектов класса “ Show objects ”.
Рис. 8 Операция отображения матрицы распознавания объектов класса “ Recognition Matrix ”.
Результаты распознавания и ошибки сохраняются программой в виде html -таблицы.
Контрольный пример: Построение классификации и анализ сайтов связывания транскрипционного фактора (ССТФ) EGR 1.
1.
На вход программе в качестве позитивной выборки подаются ССТФ EGR 1:
>S1916;
gtccgtgggt
>S4809;
ttgggggcga
>S6067;
gagggggcgg
файл EGR1_pos.seq.
В качестве негативной – случайные последовательности, сгенерированные с теми же нуклеотидными частотами, что и позитивные последовательности:
>S1916;_ N1_H1_W1;
gggtcttggc
>S1916;_ N1_H2_W1;
gggcgtttcg
>S1916;_ N1_H3_W1;
ggtgggctct
файл neg _2200. seq
Для загрузки входных данный см. Руководство пользователя, пункт 1
2.Установка параметров программы. Запуск процесса генерации закономерностей.
Установлены параметры поиска:
Confidence interval: 0,05 ;
Min. Level of CP: 0,8 ;
Size of finish Buffer: 2000;
Size of Sub Buffers: 100.
Программа обнаружила 2000 закономерностей (рис. 9).
Рис. 9 Закономерности, удовлетворяющие параметрам поиска.
3. Построение идеальных объектов классов.
В результате работы программы был обнаружен один класс. Идеальный объект класса и матрица предсказаний приведена на Рис. 10.
Рис. 10. Идеальный объект класса и матрица предсказаний для ССТФ EGR 1.
4. Применение полученных закономерностей. Вычисление ошибок распознавания.
В качестве негативного контроля были взяты последовательности, сгенерированные с той же частотой нуклеотидов, что и позитивные последовательности. Файл control _ neg _1000. seq . Программой была проведена классификация, вычисление веса каждого объекта, и распознавание (рис. 11).
Рис. 11. Классификация и распознавание контрольных объектов для ССТФ EGR 1.
