ile_eli

Понятно, что чем больше, тем лучше. Я к тому, что тысяча - мне кажется очень мало для 100-мерного кубика. Скажем, если кто-то скажет, что по трем случайным точкам может довольно точно посчитать среднее значение функции на отрезке, я много чего смогу сказать про то, как выглядит эта функция.
Для смеха взял сейчас функцию x_1*x_2*...x_100 на кубе [0 2] (чтоб среднее было 1 и чтоб численных проблем не было) и разыграл 1000 точек. Получил среднее ~0.002. Разыграл 10^7 точек, получил ~0.3. Разыграл 10^8 точек, получил 3.18. Причем до 87-го миллиона оно держалось где-то на уровне 0.5, потом скакнуло до 3.6 и опять начало снижаться.

From:

Не понимаю, при чём тут размерность куба. Предположим, что ты вообще ничего не знаешь о параметрах функции: есть какая-то величина, скажем температура какая-то, которая зависит сложным и неизвестным тебе образом от миллиона неизвестных тебе параметров; т.е. случайная переменная в чистом виде. У тебя будет проблема посчитать среднее для 1000 значений, и сказать, что это близко к её среднему? С практической точки зрения, ни у кого проблемы не будет. (Хотя с точки зрения философии, непонятно, что здесь происходит - но мы же не философы). Получается, меньше знаешь, лучше спишь?

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

From:

Не знаю. Но если, скажем, размерность куба >1000, то все наши точки лежат на одной гиперплоскости. И что, погуляв по одной гиперплоскости мы можем получить хоть какое-то представление о том, что делается в остальном кубе?

From:

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

From:

Видать, слабо зависит от импульсов в мозгах ближних :)

From:

a-shen.livejournal.com

1) если гиперплоскость случайна, то да. (Среднее по случайной гиперплоскости равно среднему по всему пространству, если отвлечься от того, что плоскости разного размера, и рассматривать всё над конечным полем, например)

2) проблема с твоим примером в том, что функция очень велика: скорость сходимости среднего по выборке к среднему по всему пространству оценивается через максимальное значение функции, обычно это называют Chernoff bound, я могу написать подробнее

3) но в целом, если пытаться понять причину происходящего - тебя же не удивляет, что при проведении опросов (забудем о всех других проблемах, с ними связанными) точность опроса определяется размером выборки, а общее количество людей не важно?

From:

прочел, что такое Chernoff bound, но не понял, как он здесь помогает.
С опросами - там все-таки совсем другая ситуация. Они меряют какую-то случайную величину (в случае выборов - более ли мменее бинарную), при этом считают, что вероятность зависит от малого числа параметров (возраст, пол, место жительства, доход). При этом они не просто выбирают опрошенных и усредняют результаты, а пытаются нормализовать по этим самым параметрам. Правда, когда тыкаешь точку, она и так нормализована по всем параметрам.
Но, скажем, определить средний доход (пример Талеба) по таким опросам не удастся. Правда, как ты и сказал, это связано с тем, что максимальное значение функции очень большое.

From:

a-shen.livejournal.com

Chernoff bound касается сходимости среднего по выборке к среднему по распределению, если известен максимум и минимум (они входят в формулу так, что чем больше между ними разница, тем хуже оценка). Опросы, как ты описываешь - это заменитель идеально случайного опроса, который делается так: берётся список всех жителей, и случайно выбирается некоторое подмножество, тогда с большой вероятностью среднее по подмножеству будет близко к среднему по всему множеству (отклонение больше с\sqrt{n} с вероятностью порядка exp(-c^2), если совсем грубо)

From:

Понял, спасибо. Там максимум и минимум можно оценить (скорее, ограничить) из физических соображений, так что все работает.

From:

lpauzner.livejournal.com

Вспомнилось про Константиновскую "кошечку", где ускорение было ограничено сверху, и потому все движения казались естественными. )

From:

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

Значит даны квадратичные формы на 100, 1000, 10000 и т.д. переменных, и коэффициенты выбраны так, что максимум функций на кубе одинаков. И ты считаешь их среднее с заданной точностью, выбирая N случайных значений на кубе. Будет ли зависеть требуемое N от количества переменных? Кажется, вовсе нет - функция распадается на члены, для которых среднее сходится без проблем. Хотя форма графика квадратичной формы на 1000 переменных может быть очень сложной - никакого понятия, что делается в какой части куба, у тебя не будет.

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

From:

zlyuk.livejournal.com

а что значит "как выглядит"? как вы со знакомыми инженерами рисуете 101-мерный график?
если речь идёт только о распределении значений (при униформном распределении х), то как выше сказано, вполне возможно что 1000-точечная выборка даёт гистограмму близкую к распределению значений.
а может быть, что они выбирают х-ы не независимо? скажем, если это какая-то feature картинок 10 на 10, то она может зависеть от подбора картинок, и её статистики - сответственно.

From:

Нет, выборка случайная. "как выглядит" - ну, скажем, может быть ответ, что она зависит только от очень маленького числа переменных (или, что примерно то же самое, но точнее, от очень маленького числа линейных (?) комбинаций переменных), а от всего остального почти не зависит. А про 1000-точечную выборку я выше ответил. Мне кажется, что 1000 - это очень маленькое число для 100-мерного куба.

From:

А как задана эта функция? Её можно посчитать для любой точки в 100-мерном кубе, или она определена на каком-то облаке точек (пусть очень большом)? И что значит среднее - среднее во всём [-1,1]^100 без взвешивания? Это мне кажется проблемой, т.к. в 100-мерном кубе, почти весь объём находится в углах (объём единичной сферы - 2.4*10^-40, на минуточку), и для большинства физических задач, где одновременное крайнее значение всех параметров маловероятно, ты посчитаешь среднее значение в регионах, где на самом деле никогда не будешь. Но если действительно считать, что все точки в [-1,1]^100 равновероятны, то я не вижу, что они могут сделать по-другому. Точки должны выбираться последовательностью Соболя, конечно.

Если же что-то известно о распределении параметров этой функции, то это задача о sampling from a multivariate distribution. Точки из распределения выбираются алгоритмом Метрополиса или каким-то другим, в зависимости от того что известно, и на них уже вычисляется статистика.

From:

Ну да, её можно посчитать для любой точки в 100-мерном кубе. А среднее - в обычном смысле - интеграл делить на объем. Т.е. предел среднего при выборке, стремящейся к бесконечности. Точки они тыкали по-моему просто как придется (rand). Вопрос не в том, что делать, а ~~кто виноват~~ что мы можем сказать о функции, зная, что она обладает таким интересным свойством.

From:

Свойство, по-моему, самое обычное: среднее подборки приближается к среднему значению случайной переменной. Про функцию, скорее всего, можно сказать, что она не имеет зависимости высокой степени от параметров, вроде твоей х_1*х_2*...х_100, или просто х_1^100.

Но если все точки в кубе равновероятны и rand() действительно даёт случайную подборку значений, то я в упор не вижу, при чём здесь вообще размерность этого куба; да будет она хоть миллион. Ты получаешь 1000 значений некой случайной величины, и на основании этого, делаешь выводы о среднем, дисперсии, и т.п. С полностью абстрактной точки зрения, это, наверное, нонсенс: у тебя среднее подборки 0.5, а следующее значение может быть 100 гуголов, и тогда что? Но ты же не задаёшься этим вопросом, получая просто случайные значения, которые не зависят от известных тебе параметров? Почему тогда известная тебе зависимость от 100 параметров тебе мешает?

From:

Ну я подозреваю, что если ты захочешь измерить среднюю температуру по Хайфе за год, ты можешь произвести 100 измерений в случайных местах в случайное время и получишь хорошее среднее и хорошую дисперсию. А если ты захочешь измерить среднюю температуру по миру за год, 100 измерений ничего тебе не дадут. Все из-за того, что в Хайфе температура слабо зависит от координаты, а зависит почти только от времени (можно и время представить как 2 координаты: время года и время суток), а в мире - еще и здорово зависит от координаты.

From:

Мне кажется, что в этом случае проблема будет скорее в том, что в мире дисперсия темпрературы больше, чем в Хайфе. Если бы в Хайфе было в один день -50, а в другой +50 - то 100 точек были бы ничем не лучше: скорость сходимости зависит от дисперсии.

Предположим, что тебе дали 100 измерений температуры, и сказали, что это температура с вышки метеоцентра города Анкх-Морпорка на неизвестной планете в случайное время. Ты посчитал среднее и дисперсию, и сказал, что в этом среднем и этой дисперсии достаточно уверен (скажем, дисперсия мала по отношению к среднему). Теперь тебе говорят: "мы тебя обманули, на самом деле это температура, взятая из случайных точек планеты Кин-Дза-Дза в случайное время". Ты скажешь - теперь это среднее неправильно?

From:

Вот ещё такое рассуждение, если ты всё еще думаешь про размерность: температура в Хайфе, как ты сказал, зависит от времени года и времени суток. Но она так же зависит (статистически) от процента облачности, направления ветра, скорости ветра, и влажности. То есть мы можем рассматривать наши 100 измерений как точки 6-мерного пространства вместо двухмерного, причём все переменные играют роль (как ты знаешь, температура при восточном ветре и низкой влажности отличается от температуры с северным ветром и осадками). Но арифметическое среднее (причем уже посчитанное) никак не может начать считаться хуже.

Мне кажется, что ты думаешь - совершенно правильно - что по этим 100 точкам нельзя построить хорошую модель температуры как функции от этих 6 переменных. Для интерполяции в таком пространстве у тебя слишком мало точек; в лучшем случае, получится зависимость от пары переменных и шум. Но для среднего, тебе это не нужно.

From:

mar-shim.livejournal.com

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

From:

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

From:

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

А вообще это сейчас очень модно -- исследовать функции от огромного числа переменных, при этом не очень заботясь об обоснованности производимых манипуляций. Требуется только, чтобы к ответу они приводили быстро, по возможности к правильному. Кое-какие эффекты при этом всё же приходится учитывать, например, что градиент функции -- понятие фиктивное.

From:

Вот выше все говорят, что это не связано с размерностью куба. И вроде логично.

From:

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

From:

Функция совершенно не должна быть непрерывной: скажем, если она равна 0 на одной половине куба, и 1 на другой - сходимость среднего к 0.5 будет хорошей. Откуда вообще может следовать непрерывность фунции, если мы считаем только значения на относительно небольшом количество точек из многомерного пространства? А рассуждение про размерность как раз чепухой не является.

From:

ошибки в их рассуждениях не вижу. А они на мои ошибки указывают довольно ясно. Когда считаешь численно интеграл (скажем, через интерполяцию), конечно в חסם ошибки влезает интеграл черт-знает-какой производной (в многомерном случае совсем даже не черт знает какой) умноженной на произведение расстояний от имеющихся точек до точки куба (интеграл по кубу). Когда размерность большая, это произведение будет совершенно огромным, оттуда и ощущение, что производная (какая-то или почти любая) должна быть почти нулевой. Поэтому мне и казалось, что ничего разумного с тысячей точек на 100 измерениях получить невозможно, кроме как если есть сильные ограничения на функцию. Но здесь подход совсем другой: вместо того, чтоб делать интерполяцию каким-то полиномом, делаем что-то, что в маломерном случае гораздо хуже, а здесь, видимо, гораздо лучше - усредняем.

From:

Да, я понимаю теперь, откуда ты начал: в низком измерении (1-2), если тебе известно, что функция полином (или близка к полиному), то тебе проще всего найти коэффициенты этого полинома, и оттуда посчитать интеграл и всё, что угодно. Но в высоком измерении, даже функция полином и даже если я тебе совершенно бесплатно дам все коэффициенты и степени членов полинома (несколько тысяч штук), ты не сможещь посчитать интеграл: интеграл полинома на единичном кубе, как это ни смешно, polynomial time inapproximable, т.е. нет алгоритма, считающего его с точностью до заданного фактора за время, полиномиальное в длине нашего полинома, если P != NP. Для полиномов с какими-то ограничениями (распадающихся на сумму коротких полиномов), можно посчитать быстрее, но в общем случае, и даже в реальных и резонных случаях, это всё безнадёжно intractable. Придётся считать по методу Монте-Карло, что и делают твои знакомые - здесь, конечно, сходимость не гарантирована, но на практике он будет сходиться достаточно хорошо.

Для более общих функций, неприменимость интерполяции не требует высокого измерения: возьмём двухмерную картинку, каждый пиксель который получен случайно. Представить эту картинку через небольшое количество переменных невозможно ((c) 1948 Claude Shannon), а посчитать интеграл/среднее через выборку - не проблема.

From:

О типе функции что-то должно быть известно. Непрерывная или кусочно-непрерывная -- значения не имеет. Более того, Монте-Карло будет отлично работать для функции вычисляемой случайно и независимо в разных точках -- если только распределение значений всюду одинаковое. А если нет? Трудно придумать функцию, интеграл которой так не посчитаешь? Да вот, отличный пример. Другое дело, что в реальных приложениях, как правило, всё работает. Но о том ведь и был вопрос, как описать требования к функции? Как выделить класс интегрируемых таким образом функций, достаточно широкий, чтобы реально встречающиеся функции ему принадлежали? Инжежнеров эти вопросы совершенно не интересуют, но автор журнала владеет научным мышлением.

From:

Ну вот Шень объясняет, что достаточно чтоб максимум не сильно отличался от минимума. С непрерывностью - по-моему ерунда. Если она всюду разрывна, но при этом равна 1 на (всюду плотном) множестве меры 1/2 и 0 на множестве (всюду плотном) меры 1/2 - все то же самое, что в примере volensnolens. (такие множества - это тема отдельной очень красивой задачки, но не о них речь)

From:

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

From:

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

From:

> Монте-Карло будет отлично работать для функции вычисляемой
> случайно и независимо в разных точках --
> если только распределение значений всюду одинаковое. А если нет?

Это не важно. Даже если значения самой функции вычисляются из разных распределений, случайно выбранные значения функции будут иметь одинаковые и независимые распределения. Скажем, если в половине точек нашей картинки значение взято из распределения Бернулли B, а во второй половины - из распределения Гаусса G, то распределение значения случайно выбранной точки будет 1/2*B+1/2*G. Выбирая точки случайно одну за другой, мы получим последовательность значений i.i.d. переменных f_i, среднее которой (последовательности) будет сходиться к среднему функции f, т.е. интегралу. Это central limit theorem, самый простой её случай. Так что класс функций, для которых это работает - все функции (ну, measurable).

Если имеется в виду скорость сходимости - она зависит от дисперсии значений функции. Для фунции ile-eli, которая берёт значения от 0 до 2^100, дисперсия очень большая, и понадобится нереальное количество точек, чтобы прийти к среднему значению. В данном случае, конечно, есть простое аналитическое решение, но оно не обобщается: для интеграла функции (даже гладкой, с гладкими производными и т.д.) в многомерном пространстве нет эффективного алгоритма - требуется экспоненциальное количество вычислений функции и т.п. То есть глаза иметь надо, и иногда можно подметить простую структуру функции и интегрировать её легко, но вообще в пространствах с размерностью 100 используются методы Монте-Карло почти без исключений.

From:

Ну конечно, скорость сходимости, о ней только и речь. То, что среднее в конце концов сойдётся -- это не Центральная Предельная и даже вообще не теорема, а более или менее тавтология.

Вопрос, как определить скорость сходимости, почему-то никем даже не обсуждался, а между тем, я вдруг осознал, что разумно определить его не так-то просто. Асимптотически среднее по n точкам стремится к пределу как O(1/√n) (это уже утвердение, но проще, чем ЦПТ). А дисперсия среднего по 1000 точек зависит только от дисперсии исходной функции. Ничего интересного.

Интуитивно, хотелось бы спросить, с какой вероятностью средние по n точкам будут более-менее монотонно приближаться друг к другу до n=1000, при этом оставаясь далёкими от предела. Во всяком случае, именно такой эксперимент стал источником дискуссии. Но как это сформулировать, чтобы можно было посчитать, я не придумал.

From:

zlyuk.livejournal.com

например, возьмём распределение состоящее из суммы К гауссиан, каждая со средним в точке 10^k, k=1,...,K, с дисперсией 1. при этом, сумма с весами убывающими от к, но не слишком быстро. для К=10^6, первые тысяча точек могут вполне сходиться к среднему (примерно равному максимуму выборки / 1000). а потом вдруг начать расти. для такого идеальног случая можно точно посчитать распределение среднего выборки n точек. будет какое-то типа F-распределения наверное.

From:

Что значит с какой вероятностью? Придумать функцию, для которой с любой вероятностью так произойдет очень просто. Всюду кроме маленького кусочка 0, на кусочке объема 1/(Nk) она равна Nk. Берем N точек. С вероятностью примерно e^-(1/k) все будут 0 (и все будут уверены, что она вообще всюду 0), а среднее, ясно, 1. Можно еще несколько таких ступенек сделать.

From: