Быстрое и бережливое дерево или эвристика сопоставления [1] (в изучении принятия решений ) — это простая графическая структура, которая классифицирует объекты, задавая один вопрос за раз. Эти деревья решений используются в различных областях: психологии , искусственном интеллекте и науке управления . В отличие от других деревьев решений или классификации , таких как CART Лео Бреймана , [2] быстрое и бережливое дерево намеренно простое, как в своей конструкции, так и в своем исполнении, и работает быстро с небольшим количеством информации. По этой причине быстрое и бережливое дерево потенциально привлекательно при проектировании задач с ограниченными ресурсами. [3]
Лаура Мартиньон , Витуш, Такезава и Форстер впервые представили как концепцию, так и термин в 2003 году; [4] подобные эвристики для других задач использовались и ранее, основываясь на формальных моделях, созданных Гердом Гигеренцером и Гербертом А. Саймоном .
В задачах категоризации с двумя вариантами и m сигналами (также известными как признаки или атрибуты), доступными для принятия такого решения, БПФ определяется следующим образом:
Быстрое и экономное дерево — это дерево классификации или решений, которое имеет m+1 выходов, с одним выходом для каждого из первых m −1 сигналов и двумя выходами для последнего сигнала.
Математически быстрые и бережливые деревья можно рассматривать как лексикографические эвристики или как линейные модели классификации с некомпенсаторными весами и порогом. [MKW] Их формальные свойства и конструкция также были проанализированы с использованием теории обнаружения сигналов Луаном, Скулером и Гигеренцером в 2011 году. [5] [LSG]
Базовыми элементами являются сигналы. Сигналы ранжируются, с одним сигналом на каждом уровне дерева и выходным узлом на каждом уровне (за исключением двух выходных узлов для последнего сигнала на последнем уровне дерева). Всякий раз, когда используется сигнал, задается вопрос о ценности сигнала. Ответы на вопросы могут немедленно привести к выходу или они могут привести к следующему вопросу (и в конечном итоге к выходу). Характерным свойством деревьев «быстро и экономно» является то, что для каждого вопроса существует по крайней мере один возможный ответ, который ведет к выходу.
В литературе по быстрым и бережливым деревьям было предложено много различных алгоритмов [4] [MKW] [LSG] [6] для (1) упорядочивания сигналов и (2) принятия решения о том, какой возможный ответ на вопрос о сигнале немедленно приводит к выходу. Быстрое и бережливое дерево полностью определено, если выполнены оба следующих условия. Часто, чтобы сохранить простоту и интуитивность конструкции, алгоритмы используют (1) простые меры «хорошести» сигнала (например, корреляцию между сигналом и категорией, рассматривая каждый сигнал независимо от других сигналов) и (2) делают простой выбор выходов (например, принимают решение о каждом выходе независимо от других выходов), но были предложены и более сложные алгоритмы.
Чтобы использовать быстрое и экономное дерево, начните с корня и проверяйте по одному сигналу за раз. На каждом шаге одним из возможных результатов является узел выхода, который допускает решение (или действие) — если выход достигнут, остановитесь; в противном случае продолжайте, пока не достигнете выхода. Сделайте выход, остановитесь; в противном случае продолжайте и задавайте больше вопросов, пока не достигнете выхода.
На рисунке 1 показано дерево быстрой и экономной классификации пациента как пациента с «высоким риском» сердечного приступа, который, таким образом, должен быть направлен в «коронарное отделение», или как пациента с «низким риском», который, таким образом, должен быть направлен в «обычную палату сестринского ухода» (Грин и Мехр, 1997). [GM]
Рассмотрим трех пациентов: Джона, Мэри и Джека:
Точность и надежность быстрых и экономичных деревьев, как было показано в исследованиях Ласки и Мартиньона (2014), сопоставимы с точностью и надежностью байесовских эталонов. [LM] Также были проведены обширные исследования, сравнивающие производительность быстрых и экономичных деревьев с производительностью алгоритмов классификации, используемых в статистике и машинном обучении, таких как наивный Байес, CART, случайные леса и логистическая регрессия, с использованием десятков реальных наборов данных. [WHM] [MKW] [6]
Быстрые и экономичные деревья используются для выполнения бинарных классификаций или решений. В психологии, медицине и других областях теория обнаружения сигналов (или теория обнаружения ) была классической теорией, в рамках которой анализируются такие задачи.
Теория предполагает, что существует две категории событий или людей (например, люди с проблемами сердца и без них), из которых более релевантная для нас категория называется «сигнал», а другая — «шум». Эти две категории различаются по распределению на шкале наблюдений, которую мы можем назвать «доказательствами», при этом распределение сигнала имеет более высокое среднее значение. Собрав доказательства, можно сделать две возможные классификации, а именно «сигнал» или «шум». Это приводит к четырем возможным результатам: попадание (классифицировать как «сигнал», когда это действительно сигнал), правильное отклонение (классифицировать как «шум», когда это действительно шум), промах (классифицировать как «шум», когда это на самом деле сигнал) и ложная тревога (классифицировать как «сигнал», когда это на самом деле шум). Чтобы максимизировать общую точность или ожидаемое значение классификации, теория утверждает, что нам нужно тщательно выбирать критерий классификации на шкале доказательств, выше которого мы принимаем решение о «сигнале», а ниже которого — о «шуме». В частности, когда цена промаха очень высока (например, классификация пациента с проблемами сердца как нормального), необходимо выбрать более низкий, более «либеральный» критерий (например, ближе к левому краю шкалы доказательств), тогда как когда цена ложной тревоги очень высока (например, классификация невиновного человека как виновного в убийстве), лучше будет более высокий, более «консервативный» критерий. Это подразумевает, что хороший принимающий решения должен быть должным образом предвзятым в большинстве реальных ситуаций; это наиболее важное и актуальное понимание теории обнаружения сигналов для классификации и принятия решений.
В 2011 году Луан, Скулер и Гигеренцер проанализировали характеристики деревьев fast-and-frugal с точки зрения теории обнаружения сигналов. Из этого анализа следует несколько ключевых выводов. Во-первых, выбор структуры выхода дерева fast-and-frugal соответствует установке критерия принятия решения при обнаружении сигналов. В двух словах, чем раньше «выход сигнала» появляется в дереве fast-and-frugal, тем более либерально смещено дерево. Относительные смещения двух деревьев fast-and-frugal определяются первым выходом, в котором они различаются, причем тот, у которого «выход сигнала» — обозначенный как «s», — всегда более либерален, чем тот, у которого «выход шума» — обозначенный как «n» (рисунок 2). Например, FFTsnnn (здесь снова s = «выход сигнала», n = «выход шума») более либерально смещен, чем FFTnsss. Этот принцип называется «смещением лексикографического решения» быстрых и бережливых деревьев.
Во-вторых, серия симуляций показывает, что быстрые и бережливые деревья с разными выходными структурами приведут к разным — иногда радикально разным — ожидаемым значениям решения, когда последствия промаха и ложной тревоги различаются. Поэтому при построении и применении быстрого и бережливого дерева необходимо выбрать выходную структуру, которая хорошо соответствует структуре выигрыша решения задачи.
В-третьих, общая чувствительность дерева fast-and-frugal — то есть насколько хорошо дерево может отличать сигнал от шума и которая может быть измерена с помощью d' или A' из теории обнаружения сигнала — зависит от свойств сигналов, которые составляют дерево, таких как среднее значение и дисперсия чувствительности сигналов и межсигнальные корреляции среди сигналов, но не сильно от выходной структуры дерева. И, наконец, производительность деревьев fast-and-frugal надежна и сопоставима с гораздо более сложными алгоритмами принятия решений, разработанными в теории обнаружения сигнала, включая модель анализа идеального наблюдателя и оптимальную последовательную модель выборки. В контексте прогнозов вне выборки деревья fast-and-frugal работают лучше всего по сравнению с другими моделями, когда размер обучающей выборки относительно невелик (например, менее 80 испытаний).
В 2017 году Филлипс, Неф, Войке и Гайсмайер [PNWG] представили пакет R FFTrees [7] , размещенный на CRAN (с сопутствующим приложением [8] ), который создает, отображает графически и количественно оценивает деревья быстрыми и экономичными способами в удобном для пользователя виде.
Деревья «быстро и бережливо» нашли множество применений как для предписания того, как следует принимать решения, так и для описания того, как люди на самом деле принимают решения. Помимо медицинской сферы, примером их предписывающего применения является обучение солдат, расквартированных в Афганистане, тому, как отличить, кто управляет автомобилем, приближающимся к контрольно-пропускному пункту, от гражданских лиц или потенциальных террористов-смертников; [9] [KK] дерево показано на рисунке 3. Два примера описательного использования деревьев «быстро и бережливо» показаны на рисунке 4. Деревья слева и справа описывают, соответственно, как человек решает, прощать ли другого человека за правонарушение, совершенное последним во время социальных взаимодействий [TLK], и как британские судьи принимают решение об освобождении под залог или тюремном заключении. [D] В целом, деревья «быстро и бережливо» можно применять для помощи или моделирования любых бинарных процессов принятия решений, включающих несколько сигналов.
A] дерево быстрого и бережливого ('соответствующая эвристика')[.]