EduTranslator

Научные работы со всего мира

EduTranslator

Рубрика: Математика

Ханойская башня: Несколько способов решить головоломку

Статью можно найти на сайте um.edu.mt

Автор Ярослав Скленар
Отставной адъюнкт-профессор
Департамента статистики и исследований операций
Факультета Науки, Университет Мальты

Вступление

Ханойская башня – это хорошо известная игра (головоломка), обычно используемая для объяснения и демонстрации силы рекурсии. Есть много вебсайтов, где предлагается ее подробное объяснение, например:

http://en.wikipedia.org/wiki/Tower_of_Hanoi

http://hanoitower.mkolar.org/

http://www.cut-the-knot.org/recurrence/hanoi.shtml

http://mathworld.wolfram.com/TowerofHanoi.html

и другие. Головоломка также подходит для демонстрации возможностей динамического программирования. Узнать об этом больше можно в статье Моше Снедовича: http://archive.ite.journal.informs.org/Vol3No1/Sniedovich/. Он использует этот подход, чтобы найти длину самого короткого решения, длину почти проигнорированного самого длинного решения и многое другое. Мы тоже используем особенности динамического программирования, но чтобы найти количество различных решений проблемы.

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

Теория

Я предполагаю, что читатель знаком с головоломкой, поэтому просто кратко резюмирую:

Есть три платформы (полюса) – левый (L), центральный (C) и правый (R).

Башня – это коллекция дисков (колец), расположенных один над другим таким образом, что диск меньшего размера всегда помещается на диск побольше. Изначально есть башня высотой n, состоящая из дисков 1…n увеличивающегося размера, где 1 – верхний самый маленький диск, расположенный на платформе L.

Правила: при перемещении дисков мы должны соблюдать следующие правила:

  • можно передвигать только один диск за раз;
  • диск можно положить или на пустую платформу, или на диск большего размера.

Задание: мы хотим переместить башню из дисков 1…n с платформы L на платформу R, следуя правилам.

Состояние задания определяется тремя взаимоисключающими наборами.

, а именно: . Вероятное состояние – это состояние, которого можно достичь, следуя правилам. Оно также гарантирует, что наборы либо являются башнями, либо могут быть пустыми. Начальное состояние выглядит как , а финальное – .

Решение представляет собой последовательность ходов (или последовательность состояний, обусловленных этими ходами), которая решает вышеуказанное задание, следуя правилам. Мы рассматриваем только решения без циклов, где каждое состояние появляется в основном один раз.

Пусть F (n, a, b, c) – общее количество различных решений головоломки с перемещением башни высотой n с платформы a на платформу b и использованием платформы c. Поскольку между платформами нет никакой разницы, обозначенной правилами, мы можем использовать F (n) для краткого обозначения.

Теорема: F(n) можно вычислить по рекурсивной формуле:

Доказательство: Очевидно, что для n = 1 есть два решения без циклов: переместить диск из L в R или переместить диск из L в C, а затем из C в R. Чтобы достичь конечного состояния, самый большой диск n необходимо переместить с L на R. Это можно сделать (всегда без циклов) двумя различными способами, которые рассмотрим отдельно.

1) Переместить башню (n-1) с L на C, переместить диск n с L на R, переместить башню (n-1) с C на R. Существует F(n-1) способов переместить башню (n-1) с L на C, точно так же как и F(n-1) способов переместить башню (n-1) с C на R. Эти два пути передвижения башен высотой (n-1) независимы, поэтому в первом случае получаем F(n-1)2 возможных решений.

2) Переместить башню (n-1) с L на R, переместить диск n с L на C, переместить башню (n-1) с R на L, переместить диск n с C на R, переместить башню (n-1) с L на R. Как видим, существует три независимых движения башни (n-1), поэтому общее количество решений в этом случае составит F(n-1)3.

Поскольку случаи 1) и 2) являются взаимоисключающими, мы получаем общее количество различных решений, предусмотренных формулой теоремы.

Легенды

Существует легенда, вероятно придуманная французским математиком Эдуардом Лукасом в 1883 году вместе с самой головоломкой:

«Легенда гласит, что группа восточных монахов является хранителями трех башен, состоящих из 64 золотых колец. Первоначально все 64 кольца были сложены на одной башне, каждое верхнее меньше кольца, расположенного под ним. Монахи должны перемещать кольца из первой башни в третью по одному, но никогда не перемещать большее кольцо поверх меньшего. Как только порядок 64 колец будет нарушен, миру придет конец».

(Больше о легенде можно узнать в источнике: http://hanoitower.mkolar.org).

Хорошо известно, что для оптимального решения головоломки с башнями требуется 2n-1 ходов. Предполагая, что один ход занимает 1 секунду, с помощью простых вычислений приходим к результату, что решение для n = 64 занимает около 585×109 лет.

Можем предложить другую легенду:

«Возьмите только 5 колец и попробуйте все возможные решения. После этого Вселенной придет конец».

Если мы примем во внимание это (нереалистичное) предположение и то, что каждое решение (их длительность отличается) в среднем занимает всего 1 секунду, потребуется около 89.67×1020 лет, чтобы перепробовать все. Достаточно времени, чтобы завершить дела перед большим взрывом.

И еще одна легенда:

«Возьмите только 4 кольца и позвольте каждому человеку на Земле решать головоломку по-своему. Когда все возможные решения закончатся, Вселенной придет конец».

В прошлом удавалось избежать конца Вселенной, но теперь условия немного изменились. Тем не менее, у нас есть одно решение почти для каждого человека.

Результаты

Вот несколько способов увеличить высоту башни:

F(1) = 2

F(2) = 12

F(3) =  1872

F(4) =  6,563,711,232

F(5) ≈  2.827798101718050e+029

Ниже приведены все решения для башен высотой 1,2 и 3 (выдержка). Каждая строка содержит одно решение, которое начинается с его номера. Движения, разделенные пробелами, имеют формат:

    kAB

где k – номер диска, который мы перемещаем с платформы A на платформу B. Обратите внимание, что первое решение является самым коротким с 2n-1 ходами, а последнее – самым длинным с 3n-1 ходами.

1 (высота башни)

2 (количество сгенерированных решений)

    1 1LR

    2 1LC 1CR

    2 (высота башни)

12 (количество сгенерированных решений)

1 1LC 2LR 1CR

2 1LC 2LR 1CL 1LR

3 1LR 1RC 2LR 1CR

4 1LR 1RC 2LR 1CL 1LR

5 1LR 2LC 1RL 2CR 1LR

6 1LR 2LC 1RL 2CR 1LC 1CR

7 1LR 2LC 1RC 1CL 2CR 1LR

8 1LR 2LC 1RC 1CL 2CR 1LC 1CR

9 1LC 1CR 2LC 1RL 2CR 1LR

10 1LC 1CR 2LC 1RL 2CR 1LC 1CR

11 1LC 1CR 2LC 1RC 1CL 2CR 1LR

12 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1C

 3 (высота башни)

 1872 (количество сгенерированных решений)

1 1LR 2LC 1RC 3LR 1CL 2CR 1LR

2 1LR 2LC 1RC 3LR 1CL 2CR 1LC 1CR

3 1LR 2LC 1RC 3LR 1CR 1RL 2CR 1LR

4 1LR 2LC 1RC 3LR 1CR 1RL 2CR 1LC 1CR

5 1LR 2LC 1RC 3LR 1CR 2CL 1RC 2LR 1CR

6 1LR 2LC 1RC 3LR 1CR 2CL 1RC 2LR 1CL 1LR

7 1LR 2LC 1RC 3LR 1CR 2CL 1RL 1LC 2LR 1CR

8 1LR 2LC 1RC 3LR 1CR 2CL 1RL 1LC 2LR 1CL 1LR

9 1LR 2LC 1RC 3LR 1CL 1LR 2CL 1RC 2LR 1CR

10 1LR 2LC 1RC 3LR 1CL 1LR 2CL 1RC 2LR 1CL 1LR

11 1LR 2LC 1RC 3LR 1CL 1LR 2CL 1RL 1LC 2LR 1CR

12 1LR 2LC 1RC 3LR 1CL 1LR 2CL 1RL 1LC 2LR 1CL 1LR

13 1LR 2LC 1RL 1LC 3LR 1CL 2CR 1LR

14 1LR 2LC 1RL 1LC 3LR 1CL 2CR 1LC 1CR

15 1LR 2LC 1RL 1LC 3LR 1CR 1RL 2CR 1LR

16 1LR 2LC 1RL 1LC 3LR 1CR 1RL 2CR 1LC 1CR

17 1LR 2LC 1RL 1LC 3LR 1CR 2CL 1RC 2LR 1CR

18 1LR 2LC 1RL 1LC 3LR 1CR 2CL 1RC 2LR 1CL 1LR

19 1LR 2LC 1RL 1LC 3LR 1CR 2CL 1RL 1LC 2LR 1CR

20 1LR 2LC 1RL 1LC 3LR 1CR 2CL 1RL 1LC 2LR 1CL 1LR

      . . .

 1865 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL  1RC 1CL 3CR 1LR 2LC 1RL 2CR 1LR

 1866 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LR 2LC 1RL 2CR 1LC 1CR

 1867 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LR 2LC 1RC 1CL 2CR 1LR

 1868 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LR 2LC 1RC 1CL 2CR 1LC 1CR

 1869 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LC 1CR 2LC 1RL 2CR 1LR

 1870 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LC 1CR 2LC 1RL 2CR 1LC 1CR

 1871 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LC 1CR 2LC 1RC 1CL 2CR 1LR

 1872 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR

Вы можете скачать текстовый файл со всеми решениями для башни высотой 3.

Количество различных решений даже для небольших башен впечатляет. Чтобы проверить формулу, я написал программы в Turbo Pascal 7, которые генерируют решения в текстовом файле в вышеуказанном формате. Проверьте, все ли варианты уникальны, затем смоделируйте, чтобы проверить. Эту формулу можно использовать и для демонстрации решений вручную. Если хотите, можете скачать эти программы. Все должно быть понятно из комментариев в исходных файлах.

Предисловие

Оригинал доступен на сайте www-users.math.umn.edu/~olver/

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

Книга по понятным причинам делится на четыре взаимосвязанные части. Первая, включающая главы 1-3, составляет алгебро-геометрическую базу рассматриваемого нами предмета. В первой главе дается быстрый обзор основных фактов дифференциальной геометрии, включая многообразия, векторные поля и дифференциальные формы. Главы 2 и 3 могли бы — при условии наличия еще некоторых подробностей — стать базовым курсом по группам Ли и теории представлений. Основными упущениями являются обстоятельная теория структуры групп Ли и алгебр, теория классификации неприводимых представлений — ни одна из них не играет существенной роли в наших практических применениях. Во второй части, включающей главы 4-7, осуществляется углубленное изучение применений метода симметрии к дифференциальным уравнениям. Мы начнем с обсуждения пространства потоков, где системы дифференциальных уравнений свободно реализуются в качестве геометрических подмножествах, и подведем итоги обсуждением контактных преобразований. Следующие три главы посвящены построению и классификации дифференциальных инвариантов с практическим применением к дифференциальным уравнениям и вариационным задачам. Мое предыдущее пособие может подкрепить этот материал множеством дополнительных вариантов применения. В третьей части — главы 8-12 — акцент смещается на проблемы эквивалентности и картановский подход в их решении. В деталях рассмотрены и приведены примеры широкого применения различных возможных вариантов, возникающих при применении картановского метода эквивалентности. В последних трех главах исследуются соответствующие результаты теории уравнений в частных производных и дифференциальных систем. В частности, мы описываем доказательства теории Фробениуса, а также Картана и Калера, которые лежат в основе всех методов.

Мне стоит упомянуть, что расположение глав несколько непривычно относительно последовательности их развития. Наиболее фундаментальный материал — теоремы существования для систем уравнений в частных производных — появляется в последних трех главах. Метод кореперов применяется при анализе симметрии дифференциальных уравнений, в частности, при построении дифференциальных инвариантов, которые используются для классификации уравнений, допускающих заданные группы симметрии. Тем не менее, я выбрал более педагогическую схему, чтобы вначале не отпугнуть потенциального читателя чрезмерно формальными темами. Таким образом, книга начинается с более легко усваиваемых методов из теории групп Ли, затем переходит к более сложному подходу Картана, основанному на дифференциальных формах, и завершает повторный анализ трудным анализом на десерт. Я надеюсь, что читатель, обладающий более логическим мышлением, не будет слишком смущен таким выбором подачи.

В математической литературе существует множество связанных между собой материалов, и одной из самых сложных задач было выбрать, какие результаты и приложения включить, а какие опустить из-за нехватки места. Например, раздел о классической теории инвариантов я когда-то представлял себе как гораздо более содержательный; однако, к сожалению, его понадобилось значительно сократить для окончательной версии (я надеюсь в ближайшем будущем использовать этот дополнительный материал в качестве основы для вводного текста по классической теории инвариантов и ее применению). Эксперты по любому из вопросов, затронутых в книге, несомненно, найдут, что многие из их любимых теоретических разработок или применений опущены, либо же прокомментированы слишком кратко. Во многих случаях это было необходимо из-за нехватки места и необходимости выбирать сведения, которые были бы особенно репрезентативными, интересными и/или междисциплинарными.  Я надеюсь, что упущения никому не помешают насладиться тем, что я наконец решил включить.

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

Хотя значительная часть книги охватывает результаты, которые хорошо известны последователям Ли и Картана, сегодняшняя целесообразность этих методов иллюстрируется удивительным разнообразием новых применений. Большая часть Главы 5, посвященной теории дифференциальных инвариантов, является новой и, кроме того, что она не была рассмотрена в материалах конференции, она еще и не встречалась в литературе ранее. Некоторые из результатов классификации для дифференциальных уравнений и вариационных задач, основанных на симметрии, также являются новыми, а другие только недавно появились в литературе. Некоторые из результатов классификации для дифференциальных уравнений и вариационных задач, основанных на симметрии, также являются новыми, а другие представлены в разброс в специальной литературе. Применение дифференциальных инвариантов к машинному распознаванию является результатом недавнего сотрудничества с Алленом Танненбаумом и Гильермо Сапиро. Интеграция уравнения Чази с использованием продолжения и симметрии появляется в совместной работе с Питером Кларксоном. Множество из применений эквивалентности Картана основаны на моем давнем сотрудничестве с Ники Кямраном. Акцент на классификационных многообразиях в решении проблемы эквивалентности для кореперов является новым и дает существенное преимущество по сравнению с традиционным подходом классифицирующей функции. Результаты касающиеся глобальной эквивалентности и неассоциативных групп Ли изложены впервые здесь. Применения классической теории инвариантов появляются в различных контекстах и ​​переформулируются в более последовательном виде; в частности, связь решения Картана с задачей эквивалентности вариационного исчисления основана на более ранней работе.

Основной предпосылкой для книги являются мультивариативные исчисления — в частности, теоремы о неявной и обратной функции и теорема о дивергенции (базовая тензорная и внешняя алгебра, а также — поверхностно — теория групп). Результаты элементарной линейной алгебры и комплексного анализа, а также основные теоремы существования для обыкновенных дифференциальных уравнений используются без комментариев. Многие стандартные результаты, ввиду нехватки места, оставлены недоказанными, хотя приводится многочисленные ссылки. Есть надежда, что книга станет основой продвинутого курса для выпускников по проблемам симметрии и эквивалентности. Я включил большое количество упражнений, которые варьируются по сложности от откровенно очевидных до довольно фундаментальных. Приводятся ссылки на решения более сложных упражнений.

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

Квантові обчислення: інструкції

Оригінал доступний на сайті www-users.cs.york.ac.uk

Самуель Л. Браунштайн

Анотація:

Уявіть собі комп’ютер, пам’ять якого істотно більша, ніж його видимий фізичний розмір; комп’ютер, який може одночасно керувати експоненціальним набором початкових даних; комп’ютер, який здійснює обчислення в проміжній сфері гільбертового простору. Що вам спало б на думку, так це квантовий комп’ютер. Щоб втілити в життя квантові комп’ютери необхідно відносно небагато понять з квантової механіки, які, до того ж, є не надто складними. Питання полягало в тому, щоб навчитися користуватися цими поняттями. Чи є поява такого комп’ютера невідворотною та наскільки складно буде його створити?

У цій статті ми наводимо інструкцію щодо того, яким чином можна використовувати квантову механіку для покращення обчислень. Виклик, що перед нами постав: вирішення задачі, яка для звичайного комп’ютера експоненційно складна, наприклад факторизація великих чисел. В якості вступу ми розглянемо звичні засоби для обчислення, універсальний логічний елемент і механізми. Потім ці ідеї застосуємо спочатку до класичних комп’ютерів, а потім до квантових. Схематична модель квантового комп’ютера описана в тій же мірі, як і деякі тонкощі його програмування. Для ефективної факторизації чисел на квантовому комп’ютері алгоритм Шора [1,2] представлений у двох частинах: квантовій процедурі в алгоритмі та класичному алгоритмі, який викликає квантову процедуру. Обговорюється математична структура факторизації, що робить можливим застосування алгоритму Шора. Ми доходимо висновку щодо доцільності та перспектив квантових обчислень у найближчі роки.

Почнемо з опису наявної задачі: факторизація числа N на його прості множники (наприклад, число 51688 може бути розкладене як 23 х 7 х 13 х 71). Зручним способом кількісного визначення того, наскільки швидко конкретний алгоритм може вирішити задачу, буде поставити питання про те, як кількість кроків для виконання алгоритму співвідноситься з величиною заданого “вихідного” алгоритму. У випадку факторизації цими вихідними даними є лише число N, яке ми хочемо обчислити; отже, довжина вихідних даних — це log N (основа логарифма визначається нашою системою нумерації. Таким чином, основа 2 подається в двійковій формі, а основа 10 — в десятковій). “Раціональні” алгоритми є такими, що масштабуються як деякий поліном незначного ступеня в розмірі початкових даних (вірогідно зі ступенем 2 або 3).

На звичайних комп’ютерах найвідоміший алгоритм факторизації виконується в O(exp[(64/9)1/3(ln N)1/3(ln ln N)2/3]) кроків [3]. Таким чином, вказаний алгоритм масштабується експоненціально з початковою величиною log N. Наприклад, у 1994 році 129-значне число (відоме як RSA129 [3′]) було успішно факторизовано за допомогою використання цього алгоритму на приблизно 1600 робочих точках, розкиданих по всьому світу; вся факторизація тривала вісім місяців [4]. Зваживши на це з метою оцінки префактора вищезгаданого експоненційного масштабування, ми виявимо, що потрібно близько 800 000 років, щоб обчислити 250-значне число, якщо використовувати комп’ютер такої ж потужності; аналогічно, на 1000-значне число знадобиться 1025 років (значно довше, ніж вік Всесвіту). Складність факторизації великих чисел має вирішальне значення для криптосистем з відкритим ключем, таких які використовуються банками. В даному випадку такі коди покладаються на складність факторизації чисел, які є десь 250-значними.

Нещодавно був розроблений алгоритм для факторизації чисел на квантовому комп’ютері, який виконується в O((log N)2+є) кроків, де є — незначне [1]. Це приблизне квадратичне значення початкових даних, тому факторизація 1000-значного числа з таким алгоритмом потребує лише декількох мільйонів кроків. Це означає, що криптосистеми відкритого ключа, засновані на факторизації, можна зламати.

Щоб дати вам уявлення про те, яким чином можливе це експоненціальне поліпшення, ми розглядаємо елементарний квантовомеханічний експеримент, який демонструє, де така сила може бути прихована [5]. Експеримент з двома щілинами є прототипом для спостереження за квантовими процесами: джерело випромінює фотони, електрони або інші частинки, які надходять до двох щілин. Ці частинки зазнають однакового впливу і, зрештою, вимірювання. Ми бачимо інтерференційну картину, коли обидві щілини відкриваються, але цей ефект повністю зникає, якщо закрита будь-яка із щілин. У певному сенсі, частинки проходять через обидві щілини паралельно. Якщо такий однаковий вплив показати в вигляді обчислень (або як дію в обчисленнях), то квантова система виконувала б обчислення паралельно. Квантовий паралелізм здійснювався б без додаткових зусиль. Результати обчислень даної системи будуть отримані за допомогою конструктивного втручання до паралельних обчислень.

 

Атрибуты для получения обратной связи от классификатора

Оригинал доступен по ссылке cc.gatech.edu

Люди

Аннотация

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

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

Доклады

Амар Паркаш, Деви Парих.
Атрибуты для получения обратной связи от классификатора.
На Европейской конференции по автоматическому распознаванию образов (ECCV), 2012 (устный).
PDF bibtex

Ариджит Бисвас, Деви Парих.
Одновременное активное изучение классификаторов и атрибутов посредством относительной обратной связи.
На конференции IEEE по автоматическому распознаванию образов и паттернов (CVPR), 2013.
PDF bibtex

Презентации

ECCV 2012 Устная презентация:
Слайды Лекция (видео)

Стендовая презентация CVPR 2013:
Стенд

Набор данных

Мы подготовили набор данных относительных атрибутов по 60 категориям лиц и 29 атрибутам (выборка PubFig) используя Amazon Mechanical Turk. Для каждой пары категорий мы демонстрируем пример изображений 10 пользователям с помощью Amazon Mechanical Turk и спрашиваем их, у какой из категорий более всего выражен каждый из атрибутов. Мы также подготовили предикторы относительных атрибутов для указанных 29 изображений. Набор данных, включающий аннотации, подготовленные предикторы атрибутов, а также выходные данные предикторов в количестве 1800 изображений можно загрузить здесь: Набор данных с относительными атрибутами лиц.

Если вы используете этот набор данных, то пожалуйста, сделайте ссылку на bibtex

Демонстрация

Мы предоставили демонстрацию данной работы на CVPR 2013. Ее можно найти здесь.

С комментариями, вопросами обращаться к Ариджиту Бисвасу