Реклама на сайте (разместить):



Реклама и пожертвования позволяют нам быть независимыми!

Теория свидетельств Демпстера-Шафера

Материал из Викизнание
Перейти к: навигация, поиск
Эвентология
Открытый Helgus~µастер~Kласс — H~µ~K
Это незавершённая статья из области эвентологии и её применений, редактируемая при участии Мастера

Демпстера-Шафера теория - это математическая теория свидетельств, основанная на функции доверия (belief functions) и функции правдоподобия (plausible reasoning), которые используются, чтобы скомбинировать отдельные части информации (свидетельства) для вычисления вероятности события. Теория была развита Артуром П. Демпстером (Arthur P. Dempster) и Гленном Шафером (Glenn Shafer).

Consider two possible gambles[править]

The first gamble is that we bet on a head turning up when we toss a coin that is known to be fair. Now consider the second gamble, in which we bet on the outcome of a fight between the world's greatest boxer and the world's greatest wrestler. Assume we are fairly ignorant about martial arts and would have great difficulty making a choice of who to bet on.

Many people would feel more unsure about taking the second gamble, in which the probabilities are unknown, rather than the first gamble, in which the probabilities are easily seen to be one half for each outcome. Dempster-Shafer theory allows one to consider the confidence one has in the probabilities assigned to the various outcomes.

Рассмотрим две возможные азартные игры[править]

The first gamble is that we bet on a head turning up when we toss a coin that is known to be fair. Now consider the second gamble, in which we bet on the outcome of a fight between the world's greatest boxer and the world's greatest wrestler. Assume we are fairly ignorant about martial arts and would have great difficulty making a choice of who to bet on.

Many people would feel more unsure about taking the second gamble, in which the probabilities are unknown, rather than the first gamble, in which the probabilities are easily seen to be one half for each outcome. In the case of the second gamble, a Bayesian would nevertheless be forced to assign one-half to each outcome, since no information is available which makes one outcome more likely than the other. Dempster-Shafer theory allows one to consider the confidence one has in the probabilities assigned to the various outcomes.

Bayesian theory cannot distinguish between lack of belief and disbelief. It does not allow one to withhold belief from a proposition without according that belief to the negation of the proposition. [SH76]

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

Много людей чувствовали бы себя более неуверенно при второй игре, в которой вероятности неизвестны, в отличие от первой, в которой вероятности каждого исхода, очевидно, равны одной второй. В случае второй игры Bayesian был бы вынужден приписать каждому исходу вероятность одна вторая, т.к. не имеется никакой информации о том, что один из исходов вероятнее другого. Теория Демпстера-Шафера позволяет нам рассматривать доверие испытываемое нами к вероятностям, которые мы приписали к различным исходам событий.

Теория Байеса не различает недостаток доверия и неверие. Она не позволяет отказать в доверии предложению без присвоения доверия отрицанию этого предложения. [SH76]

Формализм[править]

Пусть X\,\!универсальное множество, набор всех рассматриваемых утверждений. Показательное множество, P(X)\,\!, совокупность всех подмножеств множества X\,\!, включая пустое множество, \emptyset . Например, если:

X=\left\{a,b\right\}\,\!

то

P(X)=\left\{\emptyset ,\left\{a\right\},\left\{b\right\},X\right\}\,\!

По определению, масса пустого множества — ноль:

m(\emptyset )=0\,\!

Массы оставшихся элементов показательного множества нормированы на единичную сумму:

1=\sum _{{A\in P(X)}}m(A)\,\!

Масса m(A)\,\! элемента показательного множества, A\,\!, выражает соотношение всех уместных и доступных свидетельств, которые поддерживают утверждение, что определенный элемент X\,\! принадлежит A\,\! но не принадлежит ни одному подмножетсву A\,\!. Величина m(A)\,\! относится только к множеству A\,\! и не создает никаких дополнительных утверждений о других подмножествах A\,\!, каждое из которых, по определению, имеет свою собственную массу.

Исходя из приписаных масс, могут быть определены верхняя и нижняя границы интервала возможностей. Этот интервал содержит точную величину вероятности рассматриваемого подмножетсва (в классическом смысле), и ограничена двумя неаддитивными непрерывными мерами, называеыми доверие (belief) (or поддержка (support)) and правдоподобие (plausibility):

bel(A)\leq P(A)\leq pl(A)\,\!

Доверие bel(A)\,\! к множеству A\,\! определяется как сумма всех масс собственных подмножеств рассматривеаемого множества:

bel(A)=\sum _{{B\mid B\subseteq A}}m(B)

Правдоподобие pl(A)\,\! — это сумма масс всех множеств B\,\! пересекающихся с рассматриваемым множеством A\,\!:

pl(A)=\sum _{{B\mid B\cap A\neq \emptyset }}m(B)

Эти две меры соотносятся между собой следующим образом:

pl(A)=1-bel(\overline {A})\,\!

Из вышенаписанного следует, что достаточно знать хотябы одну из мер (массу, доверие или правдоподобие), чтобы вычислить оставшиеся две.

Рассмотрим проблемму объединения двух независимых множеств приписаных масс. Исходное правило объединения известное как правило умножения Демпстера является обобщением Бейесовского правила. Это правило придает особое значение согласию между многочисленными источниками и игнорирует все конфликтующие свидетельства с помощью нормализации. Правомерность использования этого правила подвергается серьёзным сомнениям в случае значительных несоответствий между источниками информации.

Собственно, объединение (называемое присоединенная маса) вычисляется из двух множеств масс m_{1}\,\! и m_{2}\,\! следующим образом:

m_{{1,2}}(\emptyset )=0\,\!

m_{{1,2}}(A)={\frac  {1}{1-K}}\sum _{{B\cap C=A\neq \emptyset }}m_{1}(B)m_{2}(C)\,\!

где:

K=\sum _{{B\cap C=\emptyset }}m_{1}(B)m_{2}(C)\,\!

K\,\! является мерой конфликта между двумя наборами масс. Нормализирующий множитель, 1-K\,\!, соответствует полному игнорированию несоответствий и приписыванию любой массе, соответствующей конфликту, пустого множества. Следовательно, эта операция приводит к контринтуитивным результатас в случае значительного конфликта при определенных обстоятельствах.

Дискуссия[править]

Dempster-Shafer theory is a generalization of the Bayesian theory of subjective probability; whereas the latter requires probabilities for each question of interest, belief functions base degrees of belief (or confidence, or trust) for one question on the probabilities for a related question. These degrees of belief may or may not have the mathematical properties of probabilities; how much they differ depends on how closely the two questions are related ([SH02]). Put another way, it is a way of representing epistemic plausibilities but it can yield answers which contradict those arrived at using probability theory.

Often used as a method of sensor fusion, Dempster-Shafer theory is based on two ideas: obtaining degrees of belief for one question from subjective probabilities for a related question, and Dempster's rule ([DE68]) for combining such degrees of belief when they are based on independent items of evidence.

In this formalism a degree of belief (also referred to as a mass) is represented as a belief function rather than a Bayesian probability distribution. Probability values are assigned to sets of possibilities rather than single events: their appeal rests on the fact they naturally encode evidence in favor of propositions.

Dempster-Shafer theory assigns its masses to all of the subsets of the entities that comprise a system. Suppose for example that a system has five members, that is to say five independent propositions which can each be true or false. If the original set is called S, then the set of all subsets —the power set— is called 2S. Since you can express each possible subset as a binary vector (describing whether any particular member is present or not by writing a “1” or a “0” for that member's slot), it can be seen that there are 25 subsets possible, ranging from the empty subset (0, 0, 0, 0, 0) to the "everything" subset (1, 1, 1, 1, 1). The empty subset represents "no solution", and is assigned a mass of zero; the remaining masses are normalised so that their total is 1. The "everything" subset is often labelled "unknown" as it represents the state where all elements are present, in the sense that you cannot tell them apart.

Поддержка и правдоподобность[править]

Shafer's framework allows for belief about propositions to be represented as intervals, bounded by two values, support and plausibility:

supportplausibility.

Support for a hypothesis is constituted by the sum of the masses of all sets enclosed by it (i.e. the sum of the masses of all subsets of the hypothesis). It is the amount of belief that directly supports a given hypothesis at least in part, forming a lower bound. Plausibility is 1 minus the sum of the masses of all sets whose intersection with the hypothesis is empty (equivalently, it is the sum of the masses of all sets whose intersection with the hypothesis is not empty). It is an upper bound on the belief that the hypothesis could possibly happen, i.e. it "could possibly happen" up to that value, because there is only so much evidence that contradicts that hypothesis.

For example, suppose we have a support of 0.5 and a plausibility of 0.8 for a proposition, say "the cat in the box is dead." This means that we have evidence that allows us to state strongly that the proposition is true with a confidence of 0.5. However, the evidence contrary to that hypothesis (i.e. "the cat is alive") only has a confidence of 0.2. The remaining mass of 0.3 (the gap between the 0.5 supporting evidence on the one hand, and the 0.2 contrary evidence on the other) is "indeterminate," meaning that the cat could either be dead or alive. This interval represents the level of uncertainty based on the evidence in your system.

Hypothesis Probability Support Plausibility
Null (neither alive nor dead) 0 0 0
Alive 0.2 0.2 0.5
Dead 0.5 0.5 0.8
Both (alive and dead) 0.3 1.0 1.0

The null hypothesis is set to zero by definition (it corresponds to "no solution"). The orthogonal hypotheses "Alive" and "Dead" have probabilities of 0.2 and 0.5, respectively. This could correspond to "Live/Dead Cat Detector" signals, which have respective reliabilities of 0.2 and 0.5. Finally, the all-encompassing "Both" hypothesis (which simply acknowledges there is a cat in the box) picks up the slack so that the sum of the masses is 1. The support for the "Alive" and "Dead" hypotheses matches their corresponding masses because they have no subsets; support for "Both" consists of the sum of all three masses (Both, Alive, and Dead) because "Alive" and "Dead" are each subsets of "Both". The "Alive" plausibility is m(Alive)+m(Both), since only "Both" intersects "Alive". Likewise, the "Dead" plausibility is m(Dead)+m(Both). Finally, the "Both" plausibility sums m(Alive)+m(Dead)+m(Both). The universal hypothesis will always have 100% support and plausibility —it acts as a checksum of sorts.

Here is a somewhat more elaborate example where the behaviour of support and plausibility begins to emerge. We're looking at a faraway object, which can only be coloured in one or more of three colours (red, white, and blue) through a variety of detector modes:

Hypothesis Probability Support Plausibility
Null 0 0 0
Red 0.35 0.35 0.56
White 0.25 0.25 0.45
Blue 0.15 0.15 0.34
Red and white 0.06 0.66 0.85
Red and blue 0.05 0.55 0.75
White and blue 0.04 0.44 0.65
All 0.1 1.0 1.0

Combining probability sets[править]

Beliefs corresponding to independent pieces of information are combined using Dempster's rule of combination which is a generalisation of the special case of Bayes' theorem where events are independent (There is as yet no method of combining non-independent pieces of information). Note that the probability masses from propositions that contradict each other can also be used to obtain a measure of how much conflict there is in a system. This measure has been used as a criterion for clustering multiple pieces of seemingly conflicting evidence around competing hypotheses.

In addition, one of the advantages of the Dempster-Shafer framework is that priors and conditionals need not be specified, unlike Bayesian methods which often use symmetry arguments to assign prior probabilities to random variables (e.g. assigning 0.5 to binary values for which no information is available about which is more likely).

Dempster-Shafer theory allows one to specify a degree of ignorance in this situation instead of being forced to supply prior probabilities which add to unity. This sort of situation, and whether there is a real distinction between risk and ignorance, has been extensively discussed by statisticians and economists. See, for example, the contrasting views of Ellsberg and Howard Raiffa.

Литература[править]

  • [DE68] Dempster, Arthur P.; A generalization of Bayesian inference, Journal of the Royal Statistical Society, Series B, Vol. 30, pp. 205-247, 1968
  • [SH76] Shafer, Glenn; A Mathematical Theory of Evidence, Princeton University Press, 1976
  • [SH02] Shafer, Glenn; Dempster-Shafer theory, 2002

См. также[править]

Ссылки[править]

Статью можно улучшить?
✍ Редактировать 💸 Спонсировать 🔔 Подписаться 📩 Переслать 💬 Обсудить
Позвать друзей
Вам также может быть интересно: