Обобщая «среднюю уловку» для более высоких измерений?

22

Для рандомизированных алгоритмов A принимающих реальные значения, «срединный трюк» - это простой способ уменьшить вероятность отказа до любого порогового значения δ>0 , за счет только мультипликативного t=O(log1δ)накладные расходы. А именно, еслиAВыход «сек падает в„хороший диапазон“I=[a,b]с вероятностью (по крайней мере)2/3,затем выполняется независимые копии1,...,ти принимая медиану их выходовa1,,atприведет к падению значенияIс вероятностью не менее1-δпо границам Черноффа / Хеффдинга.A1,,Ata1,,atI1δ

Есть ли какое-либо обобщение этого «трюка» для более высоких измерений, скажем, Rd , где хорошим диапазоном является теперь выпуклое множество (или шар, или любое достаточно хорошее и структурированное множество)? То есть, дано рандомизированное алгоритм вывода значения в R д , и «хороший набор» S R d такие , что Р г { А ( х , г ) S } 2 / 3 для всех х , как можно импульс вероятность успеха до 1 - δARdSRdPr{A(x,r)S}2/3x1δтолько с логарифмической стоимостью в ?1/δ

(По-разному: задано фиксированное, произвольное с гарантией того, что не менее 2 ta1,,atRd изaiпринадлежатS, существует ли процедура вывода значения изS? Если так, есть ли эффективный?)2t3aiSS

И каков минимальный набор допущений, необходимых для чтобы вышеперечисленное было достижимым?S

Извините, если это окажется тривиальным - я не смог найти ссылку на этот вопрос ...

Климент С.
источник
3
В особом случае, когда - кубоид, работает ли он, если вы используете медианный трюк в каждом измерении индивидуально? Итак, выберите группу точек, затем возьмите медиану их координат в измерении 1, 2, ..., d, и затем вы получите точку в R d . Может быть, вам понадобятся O ( log ( d / ϵ ) ) сэмплов с этой стратегией? SRdO(log(d/ϵ))
Робин Котари
1
В одномерном случае обычно вы знаете но не точный интервал (хотя даже если вы не знаете b - a, медианный трюк все еще работает). Должны ли мы предполагать, что знаем S, но только до перевода? До перевода и масштабирования? babaS
Сашо Николов
@SashoNikolov Я считаю, что это было бы самым «общим обобщением» (например, мы знаем только, что - «хороший шарик диаметра ε »). Sε
Клемент С.
1
Ну, то, что Томас написал в своем ответе, является еще более общим: он предполагает, что ( G в его ответе) является неизвестным выпуклым множеством. SG
Сашо Николов

Ответы:

17

То, что вы ищете, - это почти такая же устойчивая центральная тенденция : способ сокращения облака точек данных до одной точки, такой, что если многие точки данных близки к некоторой «основной истине», но остальные как угодно далеко, тогда ваш вывод также будет близок к истине. «Точка разрушения» такого метода - это доля произвольно плохих выбросов, которые он может терпеть. Разница в том, что в вашем случае вы хотите заменить «близко к» на «внутри выпуклой оболочки».

Один из способов уловить это с помощью понятия глубины Тьюки. Точка имеет глубину Тьюки (относительно заданного набора из n точек данных), если каждое полупространство, содержащее данную точку, также содержит по меньшей мере p n точек данных. Если есть хорошее выпуклое подпространство, внутри которого вы хотите находиться, то точка с глубиной Тьюки p будет внутри него, пока есть хотя быpnpnp точек данных. Таким образом, точка разрыва этого метода является наибольшим значением p, которое вы можете получить.(1p)np

К сожалению, эта точка разбивки равна , а не близко к 1/2, как для глубины Тьюки, так и для вашей проблемы. И вот почему: если ваши данные сгруппированы около вершин d + 1 симплекса, то до тех пор, пока меньше 1 / ( d + 11/(d+1)d+1их доля ) является выбросами (но вы не знаете, какие именно), тогда любая точка в Симплекс безопасен в выборе, так как он всегда будет в выпуклой оболочке не-выбросов. Но если больше 1 / ( д + 1 )1/(d+1)1/(d+1) из точек могут быть выбросы, нигде не может быть безопасно выбирать: какую бы точку в симплексе вы ни выбрали, выбросы могут быть всеми точками из ближайшей симплекс-вершины, и вы будете вне корпуса останцы.

Если вы готовы терпеть худшую точку разбивки, больше похоже на , есть рандомизированный метод для нахождения глубокой точки, полиномиальной как по n, так и по d : см. Мою статьюO(1/d2)nd

Аппроксимирующие центральные точки с повторяющимися точками Радона, К. Кларксон, Д. Эппштейн, Г. Л. Миллер, С. Стуртивант и С.-Х. Тенг, 9-й симпозиум ACM Комп. Геом. Сан-Диего, 1993, стр. 91–98, Int. J. Comp. Геом. & Appl. 6 (3): 357–377, 1996, http://kenclarkson.org/center/p.pdf

Дэвид Эппштейн
источник
Ага. Кроме того, я хотел бы упомянуть, что можно использовать eps-приближения eps-сетей и их различных друзей как способ получить небольшую выборку, которая хорошо приближается к таким мерам глубины. Вы не получаете ни единого очка, но вы получаете гораздо больше информации.
Сариэль Хар-Пелед
С терминологией вашей статьи, есть ли эффективный способ проверить заявленный -центр для рациональных чисел βββ?
Если под «эффективным» вы подразумеваете многочлен в измерении, то я не знаю такого результата. Моя статья находит только одну точку, она не дает вам больше информации о пространственном распределении глубины (о чем Сариэль упоминает выше).
Дэвид Эппштейн
Спасибо! Если оставить в стороне соображения эффективности (на данный момент), то это похоже на утверждение о том, что для общего случая произвольных выпуклых множеств нет способа повысить постоянную вероятность до произвольной вероятности? (поскольку доля хороших баллов должна быть больше ? (или я что-то упустил - оглядываясь назад, мне кажется, что вторая формулировка, которую я представляю, не отражает идею «независимых повторений», когда у нас в руках было бынескольконаборов точек, каждый из которых имел бы по крайней мере2/3часть хороших точек).11d+12/3
Климент С.
1
Одна точка, несколько точек или нет, если все, что вы знаете, это то, что существует выпуклое множество, но не там, где оно есть, и вы хотите иметь возможность повысить вероятность нахождения в правильном наборе лучше, чем d / (d + 1), тогда доля хороших точек должна составлять не менее d / (d + 1), чтобы обойти симплексный пример. В противном случае противник может предоставить вам данные в форме симплекса и выбрать случайным образом эпсилон-окрестность одной грани симплекса в качестве выпуклого множества; даже если вы случайно угадаете точку вблизи вершины симплекса, у вас будет как минимум 1 / (d + 1) вероятность ошибочного выбора.
Дэвид Эппштейн
14

Это аккуратный вопрос, и я думал об этом раньше. Вот что мы придумали:

Вы запускаете свой алгоритм раз , чтобы получить выходы х 1 , , х пR D , и вы знаете , что с большой долей вероятности большая часть х я с падения в некоторый хороший набор G . Вы не знаете, что такое G , просто оно выпуклое. Хорошей новостью является то, что есть способ получить точку в G без дополнительной информации об этом. Назовите эту точку f ( x 1 , , x n )nx1,,xnRdxiGGGf(x1,,xn) .

Теорема. Для всех натуральных чисел и d существует функция f : ( R d ) nR d такая, что имеет место следующее. Пусть х 1 . , , x nR d, и пусть G R d - выпуклое множество, удовлетворяющее 1ndf:(Rd)nRdx1...xnRdGRdТогдаF(х1,...,Хп)G. Кроме того,fвычислимо по полиному по времени отnd.
1n|{i[n]:xiG}|>dd+1.
f(x1,...,xn)Gfnd

Обратите внимание, что для мы можем установить f в качестве медианы. Так что это показывает, как обобщить медиану для d > 1 .d=1fd>1

Прежде чем доказывать этот результат, обратите внимание, что он жесткий: пусть и пусть x 1 , , x d будут стандартными базисными элементами и x d + 1 = 0 . Любое подмножество d точек содержится в аффинном пространстве G размерности d - 1 (которое однозначно определяется этими точками). Но во всех этих аффинных пространствах нет смысла. Следовательно, существует некоторая выпуклая G , содержащая n d / ( d +n=d+1x1,,xdxd+1=0dGd1G очков, но не содержит f ( x 1 , , x n )nd/(d+1)=df(x1,,xn) , какое бы значение оно ни приняло.

Доказательство.Мы используем следующий результат.

Теорема Хелли. Пусть - выпуклые подмножества R d . Предположим, что пересечение любого d + 1 K i s непусто. Тогда пересечение всех K яK1...KmRdd+1 KiKi непусто.

Нажмите здесь для доказательства теоремы Хелли.

Теперь докажем нашу теорему:

Пусть будет верхняя граница числа точек не в G . Рассмотрим все замкнутые полупространства K 1 . , , K mR d, содержащее не менее n - k точек, а их граница содержит множество точек максимального ранга (это конечное число полупространств, поскольку каждый K i определяется как d + 1k<n/(d+1)GK1...KmRdnkKid+1 точкой на своей границе).

Дополнение каждого содержит не более k точек. По границе объединения пересечение любых d + 1 K i s содержит не менее n - k ( d + 1 ) > 0 точек. По теореме Хелли (так как полупространства выпуклые), есть точка пересечения всех K я S . Пусть функция f вычисляет произвольную точку на пересечении K iKikd+1 Kink(d+1)KisfKi s.

Осталось только показать, что пересечение содержится в GKiG .

Без ограничения общности является выпуклой оболочкой подмножества точек с полным рангом. То есть мы можем заменить G выпуклой оболочкой из точек, которые она содержит. Если это не имеет полного ранга, мы можем просто применить нашу теорему в более низком измерении.GG

Каждая грань определяет полупространство, где G - пересечение этих полупространств. Каждое из этих полупространств содержит G и, следовательно, содержит не менее n - k точек. Граница одного из этих полупространств содержит грань группы G и, следовательно, содержит множество точек максимального ранга. Таким образом, каждое из этих полупространств представляет собой K i . Таким образом, пересечение всех K i содержится в G , как требуется.GGGnkGKiKiG

To compute f, set up a linear program where the linear constraints correspond to Kis and a feasible solution corresponds to a point in the intersection of all the Kis. Q.E.D.

Unfortunately, this result is not very practical in the high-dimensional setting. A good question is whether we can compute f more efficiently:

Open Problem. Prove the above theorem with the additional conclusion that f can be computed in time polynomial in n and d.

Aside: We can also change the problem to get an efficient solution: If x1,,xn have the property that strictly more than half of them lie in a ball B(y,ε), then we can find a point z that lies in B(y,3ε) in time polynomial in n and d. In particular, we can set z=xi for an arbitrary i such that strictly more than half of the points are in B(z,2ε).

Thomas supports Monica
источник
I think you basically reinvented Tukey depth as David Eppstein outlines below :)
Suresh Venkat
7

There is a notion of the median of a set of points in high-dimensions and general norms which is known under various names. It is just the point that minimizes the sum of distances to all the points in the set. It is known to have a similar confidence amplification property as the usual median with a small multiplicative increase in the distance. You can find the details in Theorem 3.1 of this paper: http://arxiv.org/pdf/1308.1334.pdf

One nice thing that this paper shows is that the factor by which the distance increases can be made any constant >1 if you can amplify from arbitrarily high (but constant < 1) confidence.

Edit: there is another recent paper on the topic by Hsu and Sabato http://arxiv.org/pdf/1307.1827v6.pdf It mostly analyzes and applies the procedure in which the point in the set with the smallest median distance to the rest of the points is used. This procedure can be used with any metric but only gives an approximation factor of 3.

Vitaly
источник
Thanks, this looks nice! I only skimmed it so far, but (unless I'm mistaken or skipped too fast over it), it deals with the specific case of S being a p-ball; is that correct?
Clement C.
1
Not really. The result is stated for all Banach spaces. For any body that is origin-centered and symmetric around its center there is a corresponding norm in which this body is the unit ball. Since for the purposes of your question we can assume without loss of generality that the convex body is origin-centered we get the result holds for every centrally symmetric convex body. Perhaps with some mild effort the result can be extended to general convex bodies.
Vitaly
1
You need to know the norm in order to compute the minimizer for that norm, though — if you know only that there is a norm but not what it is, you're out of luck.
David Eppstein
1
You are right, David. You need to know the norm. (This translates to knowing the convex body up to the center and scaling).
Vitaly
I was thinking of this approach, but then thought of this counterexample for arbitrary convex sets. How does it play in to these results? Let X be distributed in the plane as follows: with probability 0.9, uniform on (1,0) and (+1,0), with probability 0.1, equal to (0,0.0001). The convex "good" set is the line from (1,0) to (1,0). But if we take many samples, then the generalized median will be one of the sampled points located at (0,0.0001). Generalize this easily to higher dimensions using a hyperplane and a point slightly offset.
usul