plakhov: (Default)
Распространено мнение, согласно которому с увеличением программной системы число ошибок в ней обязано расти сверхлинейно (в зависимости от пессимизма носителя встречаются различные конкретизации, от "квадратично" до "экспоненциально"), и этот эффект неотвратим, как закон природы. Это мнение неверно.

Частично оно вызвано тем, что стандартный способ обеспечения отказоустойчивости, воспетый Кларком в "Свидании с Рамой", в софте плохо применим: три копии имеют большую отказоустойчивость, чем одна, только если речь идет об отказах оборудования, и то с оговорками.

Несколько раз я уже писал о том, как обходится этот "закон природы" в частных случаях (1, 2, 3, 4, 5), попробую обобщить.

Кроме abstraction leaks бывают и, назовем их так, abstraction sinks - методы, подсистемы, и алгоритмы, которые умеют "переваривать" ошибки и протечки соседей. К abstraction sink'у всегда можно подключить очередной "черный ящик", реализующий некоторый заранее обговоренный интерфейс. Работа системы в целом будет улучшаться, если этот "черный ящик" работает разумно, и не ухудшаться, если он ошибается (в том числе, если "заранее обговоренный" интерфейс оказывается протекающей абстракцией). После этого конкретные "чёрные ящики" могут писать эскимосские аутсорсеры, умные студенты, эволюционные процедуры, whatever, они могут быть сколь угодно "глючными" - лишь бы хоть иногда преодолевали порог полезности.

Здесь следует считать, что каждый черный ящик работает в собственной песочнице, т.е. не может, например, испортить память, или выбросить "неловимое" исключение. Если он примет управление и "упадет", начнет жутко тормозить, или зависнет, то можно продолжить работу так, как будто его никогда и не было. Как именно этого добиться в боевых условиях - вопрос интересный, но, надеюсь, понятно, что решаемый (если осознанно ставить себе такую задачу). Для простоты можно принять не очень реалистичное допущение, что каждый "черный ящик" запущен на собственном железе, и общается с abstraction sink'ом по сети.

Известно по крайней мере два типа abstraction sink'ов: машинное обучение ("черными ящиками" в этом случае являются отдельные features), и алгоритмы поиска и планирования ("черные ящики" - эвристики выбора "макроходов"). Ни тот, ни другой - не панацея, но их применение позволяет очень долго наращивать сложность системы уже после того, как она перестает помещаться у человека в голове, и оставлять её при этом работающей. Намного дольше, чем в привычных иерархическом или объектно-ориентированном подходах, где недопущение abstraction leak'ов критически важно.

Кое-какие современные задачи иначе и не решаются. Те, которые решаются именно так, по не до конца мне понятному совпадению чаще всего относятся к "искусственному интеллекту".

Для старых друзей: в геймдеве всё это практически не применимо. :)
plakhov: (Default)
Закрадывается подозрение, что "размышлялки" в ЖЖ писать бессмысленно. Нужны или статьи, или lytdybr, или анекдоты (в широком смысле слова). А то вот напишешь, скажем, про десктопный интерфейс. Наивно думаешь, что если кто-нибудь заинтересуется и начнет спорить, то человек этот более-менее как-то что-то понял, и выскажет здравые возражения. Например, что freeform input гораздо лучше подходит для "запросов", а "действиям" нужна предсказуемость. Может быть, скажет слово immutable. Или заметит, что, в отличие от веба, тут сложно накопить критическую массу проиндексированных действий, после которой система начнет срабатывать с необходимой полнотой. Или что необходимой массой, чтобы преодолеть потенциальный барьер, заставив разработчиков десктопного ПО жить по новым правилам, обладает только одна компания, а ей это не нужно. Или даже что-нибудь такое напишет, о чем ты сам не подумал!

Потом почитаешь реальные комментарии - и одно расстройство. Люди всерьез пишут, что freeform input невозможен, потому что вот Скрепка из Офиса всех бесила. А также командной строкой в *nix никто теперь не пользуется, а значит мысль отстой. Обидно как-то спорить на таком уровне, я лучше шоу Бенни Хилла посмотрю.

Нет, не буду сдаваться!
Новая пачка бездоказательных (за недостатком места на полях) размышлений )
plakhov: (Default)
Надоело спорить о вкусах в комментариях к предыдущему посту. Сказать хотелось нечто отличное от "оффлайн не нужен" или "в онлайне лучше". Попытка вторая и последняя.

История древнего мира мне видится так. Ранний Windows "всех победил", поскольку очень вовремя предоставил разработчикам приложений какое-никакое API, с помощью которого можно было быстро создавать современные графические интерфейсы. Похожие друг на друга, и друг с другом совместимые. Поскольку оконно-виджетный интерфейс тогда находился близко к "переднему краю программирования", все дико обрадовались и наполнили свежесозданную ОС "уникальным контентом".

Вообще, значительная часть победивших "платформ" побеждала именно этим способом: предоставляла решение проблемы, которую гораздо правильнее решать "раз и навсегда", а не "каждому по-своему".

С тех пор появился еще один важный тип взаимодействия человека с компьютером. Он выглядит так: как попало описываешь буквами свою задачу (здесь саджест и исправление опечаток). Жмешь Enter. Компьютер или её мгновенно решает, или выдает тебе упорядоченный по релевантности список инструментов и данных, необходимых для её решения.

Сейчас подобный UI имеется только у единичных интернет-поисковиков (я знаю одно исключение, это "Математика", очень нишевый продукт, необходимый код недавно скопипейстивший у младшего онлайнового брата).

Есть большое подозрение, что подобное взаимодействие можно сделать основным и для оболочки операционной системы, после чего захватить мир (в случае, если решение первой предоставит компания на букву M., не дать его перезахватить другим).
plakhov: (Default)
В последние годы всё больше вещей на компьютере делаются онлайн, и всё меньше оффлайн. И некоторые вещи относительно последнего меня всё больше удивляют.

(подразумевается, что всё ниже перечисленное происходит на компьютере с хорошим постоянным подключением к интернету, потому и удивительно; удобно держать в голове аналогию "программа = сайт, операционка = поисковик")

0) Программы нужно инсталлировать! А перед этим - покупать! Мало того, о них нужно откуда-то еще узнать до этого! А если программа тебе не понравилась, её потом нужно специальным образом удалять!
1) Чтобы пользоваться собственным компьютером, нужно знать и помнить гораздо больше, чем для любого нормального места в интернете (да и чем для них для всех вместе взятых). В Сети по сравнению с этим можно жить, не приходя в сознание.
2) Практически нигде автоматически не исправляются опечатки; даже неверную раскладку исправляет разве что какая-то сомнительная сторонняя программа.
3) Саджеста нигде нет. Каждый раз, когда Полина сохраняет рисунок, и пишет в качестве названия что-нибудь вроде "кот и со", я ожидаю, что сейчас в drop-down появится "кот и собака". Не появляется.
4) Там, где саджест есть, он убогий. Не знает, в общем-то, ничего, кроме названий имеющихся на моем компьютере файлов. Диалог открытия файла подсказывает (и потом открывает) файлы только из текущей директории - даже если я уже начал вводить название, а в этой директории нет такого файла! Даже то, что он всё-таки подсказывает, по релевантности не упорядочивается. Не понимает, что "фильмы" - это длинные видеофайлы. Не знает, что "my documents" и "мои документы" - одно и то же.
5) Музыкальный проигрыватель радостно сообщает, что файл Manowar - 01 - Wheels Of Fire.mp3, находящийся в папочке Music/Manowar/1988 - Kings Of Metal исполняет неизвестный исполнитель в неизвестном жанре, альбом неизвестен, и неизвестно зачем это вообще слушать

Дальше я с ходу не сформулирую, но пунктов пятнадцать в том же стиле насчитать можно. При этом интернет-поисковики успешно демонстрируют нам, что все эти пункты поправимы (кроме нулевого, поправимость которого демонстрируют другие люди). По-моему, долго так продолжаться не может.
plakhov: (Default)
Яндекс запустил поиск для программистов. Мне нравится; добавить к официальному посту, кажется, нечего, кроме того, что буква F в официальном названии этого продукта выглядит очень интересно.

Вышел новый Boo (язык программирования для .NET, похожий на типизированный Питон; когда-то давно - мой любимый ЯП "для души"). Чума какая, в 2011 году! Жду теперь еще Lua 5.2 для полного погружения в ретро-нирвану.

C++ 0x

Jan. 12th, 2011 09:02 pm
plakhov: (Default)
Текущий вариант стандарта выглядит гораздо более вменяемым, чем то, что нам показывали пару лет назад. Вместо фантазий на тему "как нам сделать из шаблонов настоящий пацанский compile-time Haskell" видим решения изрядно подзадолбавших проблем и некоторое количество легко имплементируемых и вполне приятных (хотя и совершенно необязательных) бантиков.

Что я точно буду использовать с огромной радостью в повседневном кодировании:(всё это без комментариев; если вы не понимаете, с чего бы такой восторг, то вы вряд ли действующий программист на С++, ну в смысле, такой, который на нем не только в CotPedro участвует, или как там этот конкурс называется, а по эн часов в день какую-нибудь функциональность пишет)

Бантики, которые мне нравятся:
  • enum classes (строгая типизация и долгожданная возможность forward declaration для enum'ов)
  • constexpr (приятно быть уверенным в том, что компилятор тебя понял)
  • делегирующие конструкторы (без комментариев)
  • static_assert - ну, просто приятно, что не нужно будет эту базовую фичу дурным макросошаблоном имитировать
  • nullptr - теперь нельзя будет перепутать и передать нулевой указатель туда, где ожидается int, char, float или bool (особенно частое явление при вызове функций с параметрами по умолчанию, из-за этого мы в московском Вогстере "умолчания" вообще запретили себе использовать)
  • raw string literals, и, конечно, юникодные строки (без комментариев)
  • user-defined literals (красивые, но находятся где-то почти на грани бесполезности)
  • thread-local storage как встроенная фича языка (простановкой одного слова рядом с нужными глобальными и статическими переменными можно превратить значительную часть legacy потоко-небезопасного кода в безопасный)
  • std::array (старый добрый fixed_vector, неужели я больше ни разу не напишу тебя вручную?)
Фишки для метапрограммирования, которые мне нравятся (да, и такие есть!):
  • decltype
  • variadic templates (конечно, редко когда требуется, но уж если потребовалось... в общем, прощайте, безумные александресковские typelist'ы)
Чего я не жду и, скорее всего, особенно использовать не стану:
  • <ересь>лямбды</ересь>
  • std::initializer_list, {}-инициализация (разве что для in-class member initializers)
  • suffix return type syntax (умопомрачительный бред, надеюсь, они все-таки поменяют этот синтаксис на auto)
  • template alias (хоть что-то похожее на возможность его осмысленно использовать я смутно припоминаю раза два за свои 10 лет программирования на плюсах)
  • rvalue-references (в подавляющем большинстве случаев swap'а и/или передачи указателя достаточно; там, где это не так, я хотел бы, чтобы "копирующее" решение синтаксически сильно отличалось от "перемещающего" - не хочется пропускать случайно или злонамеренно написанное первое)
  • extern templates (человек должен писать лишнее, чтобы помочь линкеру и компилятору? вы там не охренели?)
  • версионирование при помощи inline templates (в мире очень много мертворожденных концепций якобы "автоматического" версионирования; вы вообще видели хоть одну, свободную от аналогов dll hell?)
  • всякие очередные смартпоинтеры в STL (можно подумать, их и без того мало)
Непонятности:
  • Треды и примитивы синхронизации в STL. Будет ли это пригодно к использованию, и как это будет сочетаться с legacy кодом - бог весть.
  • regex'ы, random etc - туда же
  • Странная концепция атрибутов, странный синтаксис, странный набор "стандартных" атрибутов (хотите заменить прагмы и declspec - ну так обеспечьте синонимы хотя бы для самых распространенных, хотите compile-time проверку ошибок - добавьте хотя бы override)
  • КАКОГО ХРЕНА ОНИ ТАК И НЕ ПУСТИЛИ В ЯЗЫК VARIABLE SIZE ARRAYS? Оно же в нормальных компиляторах уже сейчас работает? Чем им не угодила возможность писать int array[n] вместо int* array = (int*) alloca(n * sizeof(int))? Что Страуструп под этим своим "thank heaven for small mercies" подразумевает?
  • Назвали hash_map unordered_map'ом. Очень мило. В namespace положить нельзя было никак?
Очень, очень жаль, что они так и не догадались сделать implicit variadic templates, итерация в которых происходит по всем параметрам заданной функции или по всем видимым членам заданного класса. А получилось бы красивое и унифицированное решение проблемы сериализации, "далеких вызовов" a la com/corba и т.п.

В общем, надо бы еще <ересь>отпилить лямбды</ересь>, и можно стандарт выпускать.

Вы-то сами на этот счет что думаете?
plakhov: (Default)
Запустили систему, над которой я работал последний год. За это время я успел её сначала полюбить, а потом возненавидеть (не переставая любить).

Технология "Спектр"

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

Система исследует запросы всех пользователей Яндекса и выделяет в них различные объекты
Тут произошла интересная вещь. Самым мощным источником информации для построения этой онтологии оказываются результаты выделения в массе поисковых запросов типичных "контекстов" и "концептов". Позже я ознакомился с работами A.Clark и некоторых других авторов, и оказалось, что этот сигнал неспроста. Подобный "парсинг" представляет собой некоторое (естественно, пока что крайне примитивное) приближение к тому, как человеческие существа учатся разговаривать на естественных языках. Такие вот 2017-дела.

Естественно! поверх всего этого работает много ручных правил всяких, фикслистов ("бензопила такая-то это не автомобиль" и т.п.), хаков, "чтение" википедии происходит по совершенно другим правилам, производится финальный проход совсем уж прямо алгоритмом Ахо-Корасик по заголовкам и снипетам готовых результатов в поисках спамоглупостей, и т.д. и т.п. Но все равно интересно, что из этого всего может выйти в прекрасном далёком.

поиск Яндекса максимизирует вероятность того, что человек найдет именно то, что искал
Это предложение описывает не столько результат, каким его хотелось бы видеть :), сколько процесс: используется честная вероятностная модель пользователя и его поведения, и выдача составляется таким образом, чтобы максимизировать некоторое матожидание в этой модели. Если обозначить количество url'ов на первой странице выдачи за N, то сложность этой процедуры экспоненциально растет с увеличением N (задача является NP-сложной, кроме шуток). К счастью, N, как правило, равно 10, к тому же простой "жадный" алгоритм для неё работает хорошо.

Эта вероятностная модель схожа с яндексовской метрикой pfound, о которой и Паша Карпович, и Илья Сегалович уже рассказывали в разных местах, и даже называется похоже. Она используется не только в текущем запуске, но и во многих других местах, где приходится иметь дело с тем, что разные пользователи хотят видеть в выдаче разные вещи (например, хоть как-то приближает к пониманию того, как определить, насколько уместны русскоязычные результаты в результатах украинского поиска). Я не могу сказать, что прямо изобрёл её (после некоторого количества размышлений такая модель кажется самоочевидной, так что её не раз переизобретали, а "о чем-то таком" в отделе качества поиска думали, наверное, вообще все), но всё-таки довел её до состояния named entity и популяризовал внутри компании.

И про название. Практически "всю дорогу" технология называлась "Разнообразием" ("Diversity"). Переименовать решили ближе к концу, когда после анонса во внутренней рассылке выяснилось, что "разнообразие" люди склонны понимать слишком буквально, и ожидают увидеть выдачу не сбалансированную по потребностям пользователей, а именно что максимально разнообразную. А "Спектром" при этом внутри называли совсем другую штуку. Ну что, всё как всегда.

Upd. Огромное спасибо прекрасной [livejournal.com profile] petsen, которая героически менеджила проект всё это время, проводила со мной ликбез насчёт всяких лингвистических тонкостей, уговаривала меня оставить одни безумные идеи и всерьез рассмотреть другие, ну и вообще подымала боевой дух. И Грише привет! :)
plakhov: (Default)
[livejournal.com profile] dabino напомнил про subj.
Искренне завидую тем, кто найдет время поучаствовать. Игра простая (чтобы понять правила, достаточно посмотреть демонстрационное видео), интересная (про межпланетные войны), неглупая. Пошаговая, с полной информацией, но классический минимаксный перебор не пройдет: на каждый "полуход" придется перебрать очень много разных возможных действий.

Я вот прямо об этом защищал диссертацию, которую никто нигде не применяет, к сожалению, потому что Россия что-то передумала готовиться к атомной войне с участием Скайнета, Периметра и ОБЧР.

В контесте я бы воспользовался плодами науки, и сделал бы вот что.
Borg cube своими руками )

Сим победиши
plakhov: (Default)
Есть таблица, в которой 3 миллиарда записей, каждая из которых содержит Идентификатор (строку заранее неизвестной длины), плюс к нему еще какие-то данные.
Есть вторая таблица, в ней 500 тысяч Префиксов. Префикс - тоже строка.

Требуется: для каждой записи из первой таблицы найти Префикс максимальной длины, с которого начинается её Идентификатор (потом по этим префиксам как-то нужно будет агрегировать, но это неважно). Всё это за какое-то разумное время, естественно.

На MapReduce задача очевидная. Ну что такое 500К строк, в самом деле? Давайте тупо сделаем из них trie; как бы плохо мы ни писали, этот самый трай поместится в пару мегабайт, а значит, его можно просто считать входным параметром для Map-операции, применяемой к первой таблице. Один проход по данным; если у нас первая табличка лежит, скажем, на 300 машинках, то на каждой из них нужно всего-то 10 млн раз прогнать строку через trie. Итого имеем: одна банальная операция, скорость выполнения которой ограничена только скоростью input-output, т.е., фактически, потоковой записи на диск.

Реляционные БД. Ммммммм нуууу...
По-моему, это адская головоломка для старшего специалиста с семью дипломами и тремя сертификатами. И когда он это таки напишет, реализация все равно будет работать за время О(3млрд * 500К * скорость матчинга wildcard'ов). И будет тонко заточена под конкретный диалект SQL и под особенности конкретной реализации, если еще не под конфигурацию БД. Ведь, чтобы она работала за приемлемое время, её придется "параллелить" и "оптимизировать" вручную.

Правильно? Или я совсем не знаю, как с современными реляционными БД работают, и все эти ужасы сам из головы себе придумал? По-моему, нет.

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

А вы говорите.

Задачу я не выдумал, это у жены на работе реально такое.
plakhov: (Default)
Пост посвящается программистам, которые отфренживают, руководствуясь мотивами вида "АААА ПАНИКА ПАНИКА ТЕПЕРЬ ПЛАХОВ ВСЕ ВРЕМЯ БУДЕТ ПИСАТЬ О вставьте название дисциплины, которая кажется им скучной".

По мотивам записей [livejournal.com profile] fregimus'а и [livejournal.com profile] timur0 (1, 2).

Под катом - программа на самом крутом в мире эзотерическом чисто функциональном языке программирования. Решает числовые ребусы (демонстрация на одном конкретном примере, "УДАР + УДАР = ДРАКА").

На С++. В compile-time. )

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

Четвертый gcc компилирует данный brainfuck на ура, msvc бесконечно долго думает, после чего рожает internal compiler error. Неудачник.

В процессе написания подобной программы быдлокодер вроде меня за какой-то час может получить кучу дополнительного понимания того, зачем на самом деле нужна хвостовая рекурсия, где лучше ленивые вычисления, а где "трудолюбивые", чем компиляторы отличаются друг от друга, почему темплейты все-таки не полноценный ФЯП, хоть и Тьюринг-полны, и т.д. и т.п.

Естественно, код можно улучшать дальше хоть до бесконечности; например, отказаться от макросов NUMx и DIFFERx, заменив их на темплейты, специфицированные для IntList'ов; убрать десятикратное копирование в середине; обобщить до случая, когда решение не единственно, сделав тип Answer'а не int'ом, а IntList'ом, и т.д. и т.п.

Под катом - мысли насчет того, насколько всё это красиво, важно и интересно )
plakhov: (Default)
Прочитал в закладках у aruslan'а про индексы в TokuDB.
Это просто поразительно, что в мире реляционных баз данных до сих пор придумывают все новые и новые способы хранения и индексирования этих самых баз. Мне кажется, это лишний раз свидетельствует о том, что сама исходная абстракция - ужасно протекающая, и ей пора на свалку (но, конечно, она там окажется ну никак не раньше, чем будет написана последняя программа на Коболе, то есть никогда).
Впрочем, если отвлечься от троллинга, сама структура данных, описанная на слайдах, милая и приятная (и наверняка была придумана где-нибудь гораздо раньше).
plakhov: (Default)
Ничего не хочется писать. Про SIGIR текст получается скучный, как сама конференция, зачем такой? Про P-NP без меня все уже написали.

Вот вспомнилось C++ное. Я думал, что этот язык меня уже ничем не удивит (особенно в хорошем смысле), однако же ему это иногда удается.

Дело было так. Яндекс использует собственную реализацию строк, частично пересекающуюся с std::string по методам и операторам, но называющуюся по-другому (да и работающую чуть иначе). Но одна кавайная технология, которую начинал [livejournal.com profile] _foreseer, а сейчас пишет аж целая группа во главе с Монстром, олдскульно использует строки из стандартной библиотеки. [livejournal.com profile] pg это слегка злило, и примерно год-полтора назад он недрогнувшей рукой закоммитил имплицитные конструкторы одного от другого (и наоборот тоже!) с целью потихоньку от std::string избавляться. Я оставил своё мнение насчет данной операции при себе, и злорадно ждал, когда же всё навернется.

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

Non-explicit конструкторы, оказывается, не такое уж зло, каким я его привык считать. Семантически схожие штуковины друг из друга создавать не страшно.
plakhov: (Default)
В очередном неинтересном апдейте в RSS Джоэля внезапно заметил дивный кусок: Need to hire a really great programmer? Want a job that doesn't drive you crazy?

Это правда? Дорамериканцы, у вас там надежды-мечты работников и работодателей действительно соотносятся именно так? Неужели рынок настолько перекошен?
plakhov: (Default)
код генерации случайных слов, перекашивающих slavk'е монитор )
Крайне тупо и просто; тем удивительнее, что в итоге получаются вполне человеческие слова. Почти к каждому возникают какие-нибудь ассоциации, иногда даже "узнаёшь перевод".

Давно такой ерундой не баловался, еще с мехмата, наверное. Сейчас это для тестирования; нужны были сотни тысяч "слов", на которых можно было бы при этом как-то дебажиться - запоминать их, отличать друг от друга и т.п.

antilamer

Apr. 16th, 2010 08:20 pm
plakhov: (Default)
Один из компонентов достижения цели "писать хороший код и не писать плохой" - таков: Писать так, чтобы при прочтении любопытство вызывали только действительно нетривиальные участки.

И под этим, и вообще под всем текстом записи готов подписаться (что для меня редкость в случае с Женей). И отдельный зачет за точность формулировок.
plakhov: (Default)
Результатом встречи является action list. Action list - это 1..N action item'ов. Каждый action item имеет вид "какой артефакт появится в ближайшее время, кто его подготовит, к какому сроку, кого об этом известит". Результирующий action list должен быть отправлен организатором встречи всем заинтересованным лицам (как минимум, всем участникам встречи).

А. Банальность
B+. Хорошее policy, надо бы внедрить
B-. Плохое policy, у нас гораздо лучше
C. Плахов стебется над менеджерами
D. Это же Гитлер Дилберт!
E. This poll sucks
F. This is not a poll

(Кто уже знает ответ, пожалуйста, молчите).
plakhov: (Default)
Ну что, развлеклись? Теперь за работу.

До начала этого года я был уверен, что человеческий интеллект с точки зрения теории вычислительной сложности является какой-то неразрешимой загадкой. Люди практически непрерывно решают задачи построения когнитивных моделей по большому набору входов большой размерности, что выглядит подозрительно похожим на решение NP-полных задач. Я даже было думал, что все эти тысячи теоретиков что-то проглядели, и пытался, опираясь на работы Leslie Valiant'а, решить Monotone Parity-P за полином малой размерности. Какие-то интересные штуки я даже придумал, но все это получилось не особенно практично. Похоже, на халяву решать произвольные NP-полные задачи таки невозможно, и лет через 30 алгебраические геометры нам расскажут, почему.

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

Для начала определимся с целями.
"Слабый" AI - это общее название для набора технологий (как уже существующих, так и находящихся в разработке), имитирующих те или иные аспекты умственной деятельности человека. Это размытая область, она различным пересекается с machine learning, статистикой, теорией оптимального управления, робототехникой, статистической лингвистикой, и т.д и т.п. Современные поисковики - самый типичный пример технологий этого класса.

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

Переход сразу от первого ко второму выглядит подозрительно и похож на чудо. Должен быть правдоподобный промежуточный этап.

Таким этапом предлагается считать появление вычислительно приемлемых алгоритмов unsupervised learning, единообразно и в режиме реального времени решающих следующие задачи:
- парсинг естественного языка
- распознавание объектов на изображениях и видео
- распознавание речи
- установление структурированных ассоциативных связей в "сенситивной каше", состоящей из всего вышеперечисленного
Этого недостаточно, чтобы клепать автоматических Платонов, Невтонов и прочих Перельманов, но вполне достаточно для того, чтобы сделать типичного "тупого робота" из классической фантастики, которому можно доверить водить автомобили, поезда и танки, который сможет полностью заменить людей на производстве (за исключением инженеров-технологов), а также собирать урожай, доить коров и встречаться со стиральной машиной. Назовем это, скажем, medium AI.

Но создание алгоритмов подобного класса - это все равно звучит фантастически, правда? А вот неправда. Оказывается, всё (хорошо, почти всё) уже придумано без нас, остается это свести воедино.

1) Были концептуальные трудности, связанные с тем, что не существует "единственно верного способа" ни поделить единый сенсорный поток на разные "объекты", ни понять, что перед нами один и тот же объект. Схожие проблемы неединственности и нечеткости возникают и с понятиями "синонимов", с таксономиями, и т.д. и т.п. Судя по всему, они благополучно разрешены при помощи структуры, называющейся lattice-ordered monoid of concepts (далее LOMoC). В работах А. Кларка (не Артура, а Александра, прошу заметить) эти идеи развиваются для парсинга естественных языков. К сожалению, в его статьях описывается странноватая модель обучения, в которой нужен учитель, ученик может выполнять вычислительно крайне громоздкие операции (что-то типа O(n7), где n - количество известных ему примеров фраз языка), да и объем коммуникаций "учителя" с "учеником" тоже нездорово большой. Тем не менее, уже сейчас это на вид сильно лучше и иерархии Хомского, и подавляющего большинства других языковых моделей. Читать можно начинать с Cla10 (pdf)

LOMoC серьезно использует тот факт, что мы работаем именно со строками, т.е. "топология" входа линейна, а не 0-мерна (вход - множество или мультимножество), не двумерна (изображение), и тем более не является экзотической (скажем, когда вход - совокупность последовательных двумерных изображений, которые иногда аннотированы строками или множествами тэгов).

Но аналогичные структуры можно по аналогии построить и для других топологий, заменив операцию свертки строки и контекста соответствующей операцией конкатенации связного подмножества входа и его локального контекста. Вот только степени полиномов станут совсем кошмарными. Тем не менее, давайте пофантазируем (пока что) и представим себе, что это сделано. Какую генеративную модель "естественных изображений" смогла бы "понять" такая система? (здесь и далее, чтобы понять, откуда я взял дальнейшее, вам придется прочитать Кларка и, главное, понять его; а если так, то с вероятностью по меньшей мере 25% вы сидите слева от меня за соседним компьютером)

Неплохую. Например, с одной стороны, она поймет, что бывают "глаза", "рты" и "уши", поймет, что "лицо" - это правильно расположенная совокупность оных, поймет на произвольном изображении "лица", где там что (не зная, как что называется, а просто выделив соответствующие концепты). В то же время она будет знать, что Мона Лиза - это не только "лицо", но и "картина" (в смысле принадлежности к соответствующему concept class), а также что это та же самая картина, что и на входе номер 1358 (в смысле принадлежности к еще более узкому концепту). По картинке разным, частично пересекающимся или включающим друг друга ее подмножествам она сопоставит разные концепты. Сможет, например, парсить детские рисунки, правильно понимая, на какой объект реального мира это похоже, или отличать фото человека от фото портрета этого человека, висящего на стене.

2) Ну а как же нам свести размерность полинома к необходимой нам для поточных realtime алгоритмов сложности expected O(n1+epsilon), и заодно избавиться от необходимости в явном "учителе"? Для этого нам придется вспомнить, что есть такая чудесная штука, как locality sensitive hashes. В web search с их помощью, в частности, ищут плотные двудольные подграфы в ориентированных графах "кто на кого ссылается", и таким образом вычисляют спам. Это уже успешно решенная задача, и решается она за О(числа вершин). Посмотри теперь на другой граф, а именно вот какой. Он двудольный, в нем вершины - это контексты и подмножества входов, а ребра отвечают на вопрос "какие подвходы встретились в каких контекстах". Что такое плотный двудольный подграф в нем? Ой, да это же и есть "концепт" Кларка!

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

Вот в общем-то и все. Пора писать medium AI.

Сейчас я активно мониторю новые статьи про locality sensitive hashing (см. вчерашнюю запись в этом же журнале), и занимаюсь на работе чем-то максимально близким, что нашлось - semi-supervised извлечением и классификацией объектов из пользовательских запросов по их контекстам. Естественно, я пользуюсь при этом гораздо более "прикладными" методами, но, тем не менее, эта вся идея работает, черт возьми, я это вижу глазами.

Тем не менее, парсить естественные языки, кажется, для первого этапа сложновато. Начать нужно, скажем, с распознавания изображений общего назначения по этой схеме. По изображению искать "смысловые" near duplicates для его частей в имеющейся базе. Не знаю, буду ли я этим заниматься, но это неважно. Не я так кто-нибудь еще, не к 2017, так к 2025-му.
plakhov: (Default)
Про распознавание, кластеризацию и machine learning.
(Если какие-то ссылки перестанут открываться, ищите в интернете по названию статьи)

Длинный дайджест с кучей ссылок на статьи )

Я еще много чего перечитал, но остальное не так интересно. А зачем это все, я завтра расскажу, первого апреля.
plakhov: (Default)
Уважаемый коллективный разум, посоветуйте, пожалуйста, книги (или обзорные тексты) по темам, которые сложно изучать "вразбивку".

1) Распознавание объектов на изображениях. Интересует прежде всего хороший обзор: что уже сделано, какие основные области применения, соответствующие им классы алгоритмов, какие признаки (features) и сигнатуры существуют и когда применяются.

2) Теория категорий (применительно к программированию). Википедию и заветы тов. Ганди я осилил, но сколько-нибудь стройной картины так и не получил. Ну то есть понятно, какие штуки бывают, но про многие совершенно непонятно, зачем. При этом довольно очевидно, что смысл в ее изучении есть, поскольку некоторые вполне жизненные наблюдения с использованием слов вида чтотоморфизм выражаются намного короче и универсальнее. В этом смысле тк похожа на алгебру.

Русский язык предпочтительнее - на нем читать получается вдвое-втрое быстрее; английский тоже ок.
plakhov: (Default)
функционального программирования, теории категорий, и прочая матана. Подскажите, какие существуют средства, пригодные для проверки того, что бинарная операция является ассоциативной (не обязательно имеющие доказательную силу, лишь бы работали). Про операцию известно "вообще всё" (грубо говоря, можно изучать ее код, если это потребуется). Придумано ли что-нибудь лучше, чем "проверить на имеющихся данных"?

Тот же вопрос про унарную операцию и идемпотентность.
Page generated Sep. 22nd, 2017 02:32 am
Powered by Dreamwidth Studios