понедельник, 31 августа 2009 г.

Создание алгоритмов и систем эволюцией

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

После просмотра ролика захотелось сделать что-нить подобное (но попроще конечно).

В такой постановке получается, что для реализации нужно выделить такие нетривиальные для нормальных программистов вещи, как:

  • Создание кирпичиков, из которых строится сама эволюционирующая система (в примере элементы маятника) и правил их взаимодействия.
  • Выбор критерия отбора новых систем (кто будет выживать, в примере точность часов).
  • Создание механизмов скрещивания и мутации при создании нового элемента (в примере показано, что только 1/9 мутация и 4/9 от предков).

Может у кого теория найдется по этому вопросу?

Имхо сама задача не такая уж и простая, но зато интересная (; Сейчас думаю уже можно на её основе создавать игровые AI, но вот в серьезных системах вряд ли.. Но вот когда их сложность и эффективность будет сравнима с реальными операторами ЭВМ (лет через 10), то тогда такой метод может дать колоссальный скачок различных аппаратно-программных комплексах.


Магическое число 7 — ОЗУ человека

Посылка

Достаточно часто в литературе и в общении можно встретить утверждение, согласно которому «человек может обрабатывать не более 7 элементов одновременно».

Совсем недавно наткнулся на оригинал научной публикации, откуда все это началось (что-то есть даж в википузии).

В жизни получалось так, что в большинстве случаев происходило следующее. Человек смотрел на что-то, видел что оно слишком сложное, и далее шло заявление: "А вы знаете, что человек не может обрабатывать большое число элементов сразу? а ну давайте упрощайте!". Это достаточно сносное использование "правила 7", но тут отсутствует во-первых его понимание (в каких случаях превышена сложность), а во-вторых не описаны способы каким образом уменьшить сложность (или срезается набор функциональности, или просто в лоб повышается вложенность). При таком отношении исходное правило преобразуется в нечто вида "существует некое предельное число объектов, которое превышать нельзя; как только мы ощущаем превышение, необходимо это число урезать". Да, в такой формулировке правило работает, но по сравнению с оригиналом весьма и весьма сносно.

Описание результатов

В работе рассматриваются два типа экспериментов (делал Миллер большинство из них не сам, а использовал результаты других лабораторий; сама же работа была обобщением результатов по описываемому правилу). В первом из которых смысл заключался в том, что испытуемому предоставлялся некий раздражитель, который он должен был различить и выдать ответ, к какому классу из N возможных он принадлежит. Раздражители были разные: размер квадрата, его яркость, цвет, тон звука, громкость звука, интенсивность вибрации на коже, соленость (вкус) и и др.. N менялось в эксперименте, т.е. человеку сначала демонстрировались N эталонов, он должен был запомнить входное значение и выдать ответ как выходное. В результате исследований выяснено, что в любом случае получается так, что до какого-то предела человек свободно различает раздражитель и может сказать какой он был, а после наступления предела начинается резкое увеличение числа ошибок. Для различных стимулов разный, но пропускная способность варьировалась от 1.6 до 3,9 бит (от ~3 до ~15 вариантов для запоминания), среднее число порядка 2.6 бит (~6 вариантов).

Все описанное это одномерный случай. Но особенность человеческого восприятия в том, что когда мы в повседневности работаем с различными раздражителями, то мы используем множество мерностей, особенно для узнавания и запоминания знакомых объектов. Таким образом при проведении исследований было установлено, что пропускная способность канала человека увеличивается при увеличении мерности (но не по максимуму). Например для определения интервала в одномерном случае результат предела 3.25 (~9.5 вариантов), а в двумерном (определение места точки в рамках квадрата) составлял 4.6 (~24 варианта). Для перехода соленый — соленый+сладкий соотношение составляет 1.9 — 2.3. При чем та же зависимость прослеживается в случае, если мерность происходит между независимыми величинами (например цвет и размер). Т.е. чем больше различных типов раздражителей используется, тем шире пропускная способность канала.

И теперь второй, более существенный по теме, тип эксперимента. Это эксперименты в таком варианте, когда на вход дается N раздражителей различного простого класса (двоичная цифра, цифра, несложное английское слово), испытуемый должен запомнить эти раздражители и через некоторое время назвать их. Таким образом ему необходимо было запомнить/оперировать одновременно заданным числом объектов. В результате предельное число (число, при превышении которого начинался лавинообразный поток ошибок) составляло 9 двоичных цифр, 8 обычных цифр, 5 английских слов.

Кроме того психология не стоит на месте. И в этом вопросе в том числе. Например по более поздним исследованиям выяснена зависимость магического числа от связи объектов с долгосрочной памятью. Т.е. если человек не может увязать объект со своим опытом, то число 7 падает вплоть до 1 (!). Эксперименты Миллера заключались в обработке простых объектов (различающихся по цвету, разным буквам/словам, известным звукам и т.д.). Если же посадить европейца и дать ему множество иероглифов на вход, то получим снижение магического числа 7, а вот с представителем родного языка иероглифов такое не произойдет. Таким образом, если человек работает с указателями на долгосрочную память, то кол-во элементов запоминания и обработки составляет порядка 7, если элементы ему малознакомы, то это число может резко падать.

Свое резюме

  • Само число 7 не является константой и панацеей. Оно может варьироваться в достаточно широких пределах. В наших интересах эти пределы по возможности расширять и всегда вписываться в них. Сам же предел определяется только в конкретной задаче.
  • Само число это не только количество элементов, которыми оперируем, но и число порогов узнаваемости. Т.е. число классов, на которые можно разбить незнакомые элементы сходу по одному знакомому признаку (измерению) и внятно с ними работать.
  • Чем более знакомые элементы, тем они проще классифицируются и разбиваются.
  • Чем больше мы используем признаков (мерностей), тем больше элементов можем классифицировать.
  • Если мы часто используем некоторые элементы (например меню оператора ЭВМ), то их число может быть намного больше 7 (того первичного числа, в котором вначале сложно ориентироваться). Если мы редко используем элементы, то этот 7-предел лучше не нарушать. Например, работаем с кодом, и при постоянной работе 7-предел может расшириться. Но если забыть про него на пару недель-месяцев-лет, то ориентироваться в нем будет сложно и получим синдром швейцарского ножа (хотя во время глубокой разработки мы его не замечали).
  • Сами элементы по возможности лучше блочно перекодировать на такие, которые несут больше бит информации, но вписываются в заданное число элементов. Например E5 7C запомнить намного проще, чем 11100101 01111100. Или 375 29 64 51 143 намного проще, чем сплошняком, при чем из этих блоков первые 2 хранятся в долгосрочной памяти (375 тел код РБ, 29 тоже стандарт).
  • Информацию записывать или предоставлять в виде последовательной ленты (такое легче запоминается — особенность человеческого мозга (см. например Human Mind)).

Обновление фото

После очередной ревизии обновились и дополнились несколько альбомов:

  1. Схватка — сюда теперь только избранное. Ресурс гугла по памяти ограничен как никак (; А все остальное скопом уйдет на EN.
  2. Фотографии Гомеля — штук 15 в конце.
  3. Воздушные змеи — после испытаний перед подготовкой CX157. И этот альбом совсем недавно стал доступным (из-за секретности подготовки уровня).
  4. Лыжи 2008/2009.

четверг, 27 августа 2009 г.

Парадокс МЖ

Когда-то давно мне пришел в голову нижеследующий парадокс. Совсем недавно (пару мес назад) я его вспомнил и думал, что нашел разрешение. Но оказывается что не все так просто — только попытка поставить эксперимент и получить реальную модель обернула все наобормот и привела к совершенно другим выводам. Но обо всем по порядку.

Парадокс чисто интуитивный. Имеем мужчин (М) и женщин (Ж). Известно, что М рождается больше, чем Ж (если мне не изменяет память, 115 к 100). Если не происходит войн и пр. факторов убивания М до детородного возраста, то как получается (или можно получить) так, что Ж хватает всем М и ещё остается? (т.к. по статистике на 10 девчёнок 9 ребят).


Мое разрешение было простое и сходу может и непонятное. Заключается оно в том, что М должны быть старше своих Ж (и соответственно Ж младше своих М). Т.е. в результате Ж рожала в меньшем возрасте, чем М, и оборот женского пола шел быстрее.

В таком убеждении я был пару месяцев, и на днях попробовал смоделить пример. И на нем получилось обратное:

В скобках возраст, первое число - год; М в брак вступает в 40 лет, Ж в 20:

  • 0: М(0), Ж(0), М(20)
  • 20: М(20), Ж(20), М(40), М(0), Ж(0); пара
  • 40: М(20), Ж(40), М(60), Ж(20), М(40)

на 40-м ситуация повторяется с шагом 20 лет.

Т.е. для ситуации 9/10 при пропорции 50/50 кто-то обязательно должен оставаться за бортом. Или естественной смертью, или просто по возрасту.

Ещё ситуация 10/9 может быть выполнена с соблюдением условий задачи и решением по возрасту в случае, когда население постоянно растет.

Если М старше Ж в паре, то у М больший риск не дожить до возраста вступления в брак.

К этому всему можно приплюсовать плановый процент потерь живой силы на учениях, составляющий 2% (с) SD

И когда-то давно мне объясняли на уроках географии, что число М и Ж уравниваются к 16 лет. Потому что М более любознательные/рискованные/..., потому не доживают до детородного возраста.

Интересными получились результат и порядок развития событий. С разными отношениями в системах, подобных М-Ж встречался, и сейчас оказался сюрприз (;


суббота, 15 августа 2009 г.

ICQ Traffic Rating

Сезонное обновление..

Сейчас уже не показаны те, у кого не было траффика за последний период.