Быстрые и бережливые деревья

Быстрое и экономичное дерево или эвристика сопоставления (при изучении принятия решений ) представляет собой простую графическую структуру, которая классифицирует объекты, задавая по одному вопросу за раз. Эти деревья решений используются в различных областях: психологии , искусственном интеллекте и науке управления . В отличие от других решений или классификации деревьев , таких как Лео Бреймана , CART Быстрые и бережливые деревья намеренно просты как по конструкции, так и по исполнению, и работают быстро, имея мало информации. По этой причине быстрые и бережливые деревья потенциально привлекательны при разработке задач с ограниченными ресурсами.

Лаура Мартиньон , Витуш, Такезава и Форстер впервые представили концепцию и термин в 2003 году; аналогичные эвристики для других задач использовались и раньше, основываясь на формальных моделях, созданных Гердом Гигеренцером и Гербертом А. Саймоном .

В задачах категоризации с двумя вариантами и m -подсказками, также известными как функции или атрибуты, доступными для принятия такого решения, БПФ определяется следующим образом:

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

С математической точки зрения деревья «быстро и экономно» можно рассматривать как лексикографические эвристики или модели линейной классификации с некомпенсационными весами и порогом. ^[МКВ] Их формальные свойства и конструкция также были проанализированы с использованием теории обнаружения сигналов Луаном, Скулером и Гигеренцером в 2011 году. ^[МСУ]

Основная организация

Строительство

Базовыми элементами являются сигналы. Сигналы ранжированы: по одному сигналу на каждом уровне дерева и выходному узлу на каждом уровне (за исключением двух выходных узлов для последнего сигнала на последнем уровне дерева). Всякий раз, когда используется реплика, задается вопрос о ее ценности. Ответы на вопросы могут привести к немедленному выходу или к следующему вопросу (и, в конечном итоге, к выходу). Характерным свойством деревьев быстрого и экономного является то, что на каждый вопрос существует хотя бы один возможный ответ, ведущий к выходу.

В литературе по быстрым и экономным деревьям было предложено множество различных алгоритмов. ^{[МКВ] [МСУ]} для (1) упорядочивания сигналов и (2) решения, какой из возможных ответов на вопрос о сигнале немедленно приведет к выходу. Дерево «быстро и экономно» полностью определено, если выполняются оба следующих условия. Часто, чтобы сохранить простоту и интуитивность построения, алгоритмы используют (1) простые меры «хорошести» сигнала (например, корреляция между сигналом и категорией, рассматривая каждый сигнал независимо от других сигналов) и (2) делают простой выбор относительно выходов (например, решение о каждом выходе независимо от других выходов), но были предложены и более сложные алгоритмы.

Исполнение

Чтобы использовать дерево «быстро и экономно», начните с корня и проверяйте по одному сигналу за раз. На каждом этапе одним из возможных результатов является выходной узел, который позволяет принять решение (или действие) — если выход достигнут, остановиться; в противном случае продолжайте, пока не будет достигнут выход. Выйдите, остановитесь; в противном случае продолжайте и задавайте больше вопросов, пока не будет достигнут выход.

Рисунок 1. Быстрое и экономичное дерево, которое помогает врачам отделения неотложной помощи решить, следует ли отправить пациента в обычную койку для медсестер или в отделение коронарной терапии (Green & Mehr, 1997). ^[ГМ]

Рисунок 1 иллюстрирует дерево быстрого и экономичного способа классификации пациента как пациента с «высоким риском» сердечного инсульта и, следовательно, его необходимо отправить в «отделение коронарной терапии», или как пациента с «низким риском» и, следовательно, его необходимо отправить в «обычная койка для кормления» (Green & Mehr, 1997). ^[ГМ]

Рассмотрим трех пациентов: Джона, Мэри и Джека:

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

Производительность

В исследованиях Ласки и Мартинньона (2014) было показано, что точность и надежность быстрых и бережливых деревьев сопоставимы с точностью и надежностью байесовских эталонов. ^[ЛМ] Обширные исследования, сравнивающие производительность быстрых и экономичных деревьев с производительностью алгоритмов классификации, используемых в статистике и машинном обучении, таких как наивный Байес, CART, случайные леса и логистическая регрессия, также были проведены с использованием десятков реальных алгоритмов. наборы данных. ^{[ШГМ] [МКВ]}

Анализ обнаружения сигнала

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

Теория предполагает, что существуют две категории событий или людей (например, люди с проблемами сердца и без них), из которых более актуальная для нас категория называется «сигналом», а другая — «шумом». Они различаются распределением по шкале наблюдения, которую мы можем назвать «доказательствами», при этом распределение сигналов имеет более высокое среднее значение. Собрав доказательства, можно сделать две возможные классификации, а именно «сигнал» и «шум». Это приводит к четырем возможным результатам: попадание (классифицировать как «сигнал», когда это действительно сигнал), правильное отклонение (классифицировать как «шум», когда это действительно шум), промах (классифицировать как «шум», когда это действительно шум). сигнал) и ложная тревога (классифицируется как «сигнал», когда на самом деле это шум). Чтобы максимизировать общую точность или ожидаемую ценность классификации, теория утверждает, что нам необходимо тщательно выбирать критерий классификации на шкале доказательств, выше которого мы принимаем «сигнальное» решение, а ниже которого — «шум». В частности, когда цена промаха очень высока (т. е. классификация пациента с сердечными заболеваниями как нормального), необходимо выбрать более низкий, более «либеральный» критерий (т. е. влево по шкале доказательности), тогда как, когда Цена ложной тревоги очень высока (например, признание невиновного человека виновным в убийстве), поэтому лучше использовать более высокий и «консервативный» критерий. Это означает, что хороший человек, принимающий решения, должен быть должным образом предвзятым в большинстве реальных ситуаций; это наиболее важный и актуальный вывод теории обнаружения сигналов о классификации и принятии решений.

Рисунок 2. Верхняя часть рисунка иллюстрирует предположения теории обнаружения сигналов в задаче принятия двоичного решения. Три вертикальные линии представляют три критерия принятия решения, которые могут принять агент и лицо, принимающее решение. Нижний раздел иллюстрирует четыре возможных БПФ, которые можно построить, если рассматривать три функции в фиксированном порядке. На основании классификаций, на которые указывают первые два выхода, деревья именуются слева направо FFTss, FFTsn, FFTns и FFTnn. Стрелки, соединяющие части рисунка, примерно указывают расположение критериев решения четырех БПФ, когда они используются для классификации или принятия решения по двоичному сигналу и шуму (для сигнала и шума соответственно). Среди четырех, FFTss имеет самый либеральный критерий принятия решения, а FFTnn — самый консервативный. Критерии принятия решений FFTsn и FFTns менее крайние, чем два других, причем FFTsn более либеральны, чем FFTns.

В 2011 году Луан, Скулер и Гигеренцер проанализировали характеристики быстрых и экономных деревьев с точки зрения теории обнаружения сигналов. Из этого анализа можно сделать несколько ключевых выводов. Во-первых, выбор структуры выхода быстрого и экономичного дерева соответствует установке критерия решения при обнаружении сигнала. Короче говоря, чем раньше в дереве быстрых и бережливых действий появляется «выход сигнала», тем более либерально предвзятым является дерево. Относительные смещения двух быстрых и бережливых деревьев определяются первым выходом, в котором они различаются, при этом тот, который имеет «сигнальный выход», обозначаемый буквой «s», всегда более либерален, чем тот, который имеет «шумовой выход». выход» – обозначается буквой «n» (рисунок 2). Например, FFTsnnn (здесь снова s = «Выход сигнала», n = «Выход шума») более предвзят, чем FFTnsss. Этот принцип называется «лексикографической предвзятостью решений» деревьев быстрых и бережливых вычислений.

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

В-третьих, общая чувствительность быстрого и экономичного дерева, то есть то, насколько хорошо дерево может отличать сигнал от шума и которую можно измерить с помощью d' или A' из теории обнаружения сигналов , зависит от свойств дерева. сигналы, составляющие дерево, такие как среднее значение и дисперсия чувствительности сигналов, а также корреляции между сигналами между сигналами, но не в значительной степени из-за структуры выхода дерева. И, наконец, производительность быстрых и экономичных деревьев надежна и сравнима с гораздо более сложными алгоритмами принятия решений, разработанными в теории обнаружения сигналов, включая модель анализа идеального наблюдателя и модель оптимальной последовательной выборки. В контексте прогнозов вне выборки «быстрые и экономные» деревья работают лучше всего по сравнению с другими моделями, когда размер обучающей выборки относительно невелик (например, менее 80 испытаний).

Рисунок 3. Быстрое и экономичное дерево, которое может помочь солдатам, дислоцированным в Афганистане, отличить, управляется ли автомобилем, приближающимся к контрольно-пропускному пункту, гражданские лица или потенциальные террористы-смертники (Keller & Katsikopoulos, 2016). ^[КК]

Рисунок 4. Деревья «быстрости и бережливости», описывающие, как человек решает, простить ли другого человека за оскорбление, совершенное последним во время социального взаимодействия (слева; Тан, Луан и Кацикопулос, 2017). ^[ТЛК] и как британские судьи решают, следует ли выносить решение об освобождении под залог (Right. Dhami, 2003). ^[Д]

Компьютерная поддержка

В 2017 году Филлипс, Нет, Войке и Гайсмайер ^[ПНРГ] представил пакет R FFTrees, размещено на CRAN (с сопутствующим приложением) ), который конструирует, графически изображает и количественно оценивает быстрые и экономичные деревья удобным для пользователя способом.

Еще примеры

Деревья быстрого и бережливого подхода нашли множество применений как для описания того, как следует принимать решения, так и для описания того, как люди на самом деле принимают решения. Помимо медицинской сферы, примером их предписывающего применения является обучение солдат, дислоцированных в Афганистане, как отличить автомобиль, приближающийся к контрольно-пропускному пункту, за рулем гражданских лиц или потенциальных террористов-смертников; ^[КК] дерево показано на рисунке 3. Два примера описательного использования деревьев быстрого и бережливого поведения показаны на рисунке 4. Деревья слева и справа описывают, соответственно, как человек решает, простить ли другому человеку обиду или нет. последнее совершено во время социальных взаимодействий ^[ТЛК] и как британские судьи принимают решение об освобождении под залог или тюремном заключении. ^[Д] В общем, деревья быстрого и экономичного подхода можно применять для помощи или моделирования любых бинарных процессов принятия решений, включающих множество сигналов.

Похожие статьи и другие источники

ГМ.

Грин и Мехр, 1997 г. Грин Л. и Мехр Д.Р. (1997). Что меняет решения врачей о госпитализации в отделение коронарной терапии? Журнал семейной практики, 45 (3), 219–226.

МХ.

Мартинньон и Хоффраже 2002 Быстро, экономно и удобно: простая эвристика для парного сравнения

И.

Дхами, М.К., и Эйтон, П. 2001. Освобождение под залог и заключение под стражу быстрым и бережным способом. Журнал принятия поведенческих решений, 14 (2), 141–168.

ДХ.

Дхами и Харрис, 2001 г. Быстрые и экономные модели человеческого суждения в сравнении с регрессионными моделями. Мышление и рассуждение, 7 (1), 5–27.

ФЗБМ.

Фишер, Штайнер, Зукол, Бергер, Мартинньон. Использование простых эвристик для назначения макролидов детям с внебольничной пневмонией. Архив педиатрии и подростковой медицины, 156 (10), 1005–1008.

МКВ.

Мартинньон, Кацикопулос и Войке, 2008 г. Категоризация с ограниченными ресурсами: семейство простых эвристик.

Д.

Дхами, МК (2003). Психологические модели принятия профессиональных решений. Психологическая наука, 14, 175–180.

МСУ.

Луан, Скулер и Гигеренцер, 2011 г. Анализ обнаружения сигналов быстрых и экономных деревьев.

ЛМ.

Ласки и Мартинньон, 2014 г. Сравнение быстрых и бережливых деревьев и байесовских сетей для оценки рисков.

КК.

Келлер Н. и Кацикопулос К.В. (2016) – О роли психологической эвристики в операционных исследованиях; и демонстрация операций по обеспечению военной стабильности. Европейский журнал операционных исследований, 249, 1063–1073.

ТЛК.

Тан Дж. Х., Луан С. и Кацикопулос К. В. (2017). Подход к моделированию решений о прощении, основанный на обнаружении сигналов. Эволюция и поведение человека, 38, 21–38.

УХМ.

Войке, Хоффраж и Мартинньон, 2017 г. – Интеграция и тестирование естественных частот, наивного Байеса и быстрых и экономных деревьев.

ПНРГ.

Филлипс, Нет, Войке и Гайсмайер, 2017. FFTrees: набор инструментов для создания, визуализации и оценки деревьев принятия быстрых и экономичных решений. Суждение и принятие решений, 12 (4), 344–368.