Знак в процедуре стохастической аппроксимации

[_hum_]

Почему-то нигде толком не акцентируется внимание, как выбирать знак в процедуре наподобие Робинсона-Монро. Кое-где только мельком замечают, что мол, предположим, что функция монотонно неубывающая. Но, позвольте, откуда же человек, не имеющий этой функции (а иначе смысла в процедуре бы не было) под рукой, будет знать о ее неубывании (монотонность - ладно, но как узнать неубывающая или невозрастающая)?

[dsge]

_hum_ в сообщении #1175774 писал(а):

но как узнать неубывающая или невозрастающая

Подставить 2 значения аргумента в функцию.

_hum_ в сообщении #1175774 писал(а):

откуда же человек, не имеющий этой функции (а иначе смысла в процедуре бы не было) под рукой,

Если под рукой ничего нет, то и искать нечего.

[_hum_]

dsge в сообщении #1175777 писал(а):

_hum_ в сообщении #1175774 писал(а):

но как узнать неубывающая или невозрастающая

Подставить 2 значения аргумента в функцию.

Вы наверное не вникали в суть проблемы. Стохастическая аппроксимация помогает найти корень уравнения $M(\theta)::=\mathbb{E}\big[F(X;\theta)\big] = 0$, не зная саму функцию $M(\theta)$, а только имея под рукой выборку из случайных величин $F(X_i;\theta)$.

[dsge]

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

[_hum_]

dsge в сообщении #1175787 писал(а):

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

Еще раз постановка задачи. Есть набор реализаций $y_i$ случайных величин $F(X_i;\theta)$. Есть два варианта итеративной процедуры поиска корня уравнения $\mathbb{E}\big[F(X;\theta)\big] = 0$:
1) $\theta_{i+1} = \theta_i - \alpha y_i $
2) $\theta_{i+1} = \theta_i + \alpha y_i $
Вопрос, как определить , какой вариант выбирать?

-- Вс дек 11, 2016 00:40:33 --

dsge в сообщении #1175787 писал(а):

В общем случае любая функция в окрестности нуля монотонна.

Кстати это же неверно даже для непрерывной функции. Возьмите какую-нибудь $x\sin(1/x)$

[dsge]

_hum_ в сообщении #1175796 писал(а):

1) $\theta_{i+1} = \theta_i - \alpha y_i $
2) $\theta_{i+1} = \theta_i + \alpha y_i $

${\alpha}_i$??? Если функция возрастающая, то 1), если убывающая, то 2).

_hum_ в сообщении #1175796 писал(а):

Кстати это же неверно даже для непрерывной функции. Возьмите какую-нибудь $x\sin(1/x)$

dsge в сообщении #1175787 писал(а):

В общем случае

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

[_hum_]

dsge в сообщении #1175809 писал(а):

_hum_ в сообщении #1175796 писал(а):

1) $\theta_{i+1} = \theta_i - \alpha y_i $
2) $\theta_{i+1} = \theta_i + \alpha y_i $

${\alpha}_i$???

что непонятного? взял в качестве ${\alpha}_i = \alpha$, где $\alpha \in (0,1)$.

Цитата:

Если функция возрастающая, то 1), если убывающая, то 2).

какая функция?

Цитата:

_hum_ в сообщении #1175796 писал(а):

Кстати это же неверно даже для непрерывной функции. Возьмите какую-нибудь $x\sin(1/x)$

dsge в сообщении #1175787 писал(а):

В общем случае

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

а может все-таки, непрерывную дифференцируемость?

[dsge]

_hum_ в сообщении #1175816 писал(а):

что непонятного? взял в качестве ${\alpha}_i = \alpha$, где $\alpha \in (0,1)$.

Так ничего не сойдется.

_hum_ в сообщении #1175816 писал(а):

какая функция?

Для которой что-то ищется.

[_hum_]

dsge в сообщении #1175822 писал(а):

_hum_ в сообщении #1175816 писал(а):

что непонятного? взял в качестве ${\alpha}_i = \alpha$, где $\alpha \in (0,1)$.

Так ничего не сойдется.

_hum_ в сообщении #1175816 писал(а):

какая функция?

Для которой что-то ищется.

Вы издеваетесь? Ищется для $M(\theta)::=\mathbb{E}\big[F(X;\theta)\big]$. Взять ее неоткуда.

[Pavia]

_hum_
В википедии неписано что это инженерный подход. Так что некоторые неточнгсти и допущения могут быть и могут выбираться по желанию человека.

Всё таже как и в МНК.

Цитата:

Но, позвольте, откуда же человек, не имеющий этой функции (а иначе смысла в процедуре бы не было)

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

[dsge]

_hum_ в сообщении #1175824 писал(а):

Вы издеваетесь?

Нет.

_hum_ в сообщении #1175824 писал(а):

Ищется для $M(\theta)::=\mathbb{E}\big[F(X;\theta)\big]$. Взять ее неоткуда.

Если у вас есть $F(X;\theta)$, то должны быть и идеи относительно свойств $M(\theta)::=\mathbb{E}\big[F(X;\theta)\big]$. Или какие-нибудь априорные знания относительно параметризованного мат.ожидания.
Монотонность существенна в доказательстве сходимости процесса, также как и не очень быстрое стремление к нулю последовательности ${\alpha}_i$.
В книге Вазан (или Невельсон и Хасьминский?) есть пример о влиянии удобрений на урожайность. При данном количестве удобрений урожайность является случайной вкличиной, однако в среднем, чем больше удобрений, тем больше урожайность - откуда и берется монотонность. Задача найти количество удобрений, обеспечивающих заданную урожайность в среднем.

[_hum_]

dsge в сообщении #1176707 писал(а):

Если у вас есть $F(X;\theta)$, то должны быть и идеи относительно свойств $M(\theta)::=\mathbb{E}\big[F(X;\theta)\big]$. Или какие-нибудь априорные знания относительно параметризованного мат.ожидания.
Монотонность существенна в доказательстве сходимости процесса, также как и не очень быстрое стремление к нулю последовательности ${\alpha}_i$.
В книге Вазан (или Невельсон и Хасьминский?) есть пример о влиянии удобрений на урожайность. При данном количестве удобрений урожайность является случайной вкличиной, однако в среднем, чем больше удобрений, тем больше урожайность - откуда и берется монотонность. Задача найти количество удобрений, обеспечивающих заданную урожайность в среднем.

Нет у меня функции $F(X;\theta)$, есть только реализации этой случайной величины.
Вообще, вопрос изначально был вызван желанием понять, как вывести q-learning процедуру из условия поиска нуля среднего методом стохастической аппроксимации. Вроде бы так напрямую и получалось бы, если бы не этот чертов знак. А в q-learning нет никаких предположений относительно поведения случайной величины.

И еще непонятно, почему не придумали процедуру, которая бы сама знак подбирала (типа - если при одном знаке идет увеличение ошибки, то надо выбрать противоположный).
И для многомерного случая непонятно, как там знаки эти выбирать. И вообще, почему так мало литературы по данному вопросу в нете? Эту процедуру что никто сегодня не использует?

[Pavia]

_hum_
Что-то я сразу не обратил внимания метод итерационный. Я слабо их знаю.

_hum_ в сообщении #1176963 писал(а):

И еще непонятно, почему не придумали процедуру, которая бы сама знак подбирала (типа - если при одном знаке идет увеличение ошибки, то надо выбрать противоположный).

Придумали МНК назвали, точнее в МНК такой проблемы нет. А монотонность или знак можно определить через дифференцирование. Так как функция стохастическая, то перед дифференцированием нужно делать усреднение.
В лоб в этом методе не применишь.

_hum_ в сообщении #1176963 писал(а):

Эту процедуру что никто сегодня не использует?

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

_hum_ в сообщении #1176963 писал(а):

И вообще, почему так мало литературы по данному вопросу в нете?

Плохо ищите. Вся статистика укладывается 15-30 страниц. Всё остальное это подстановка формул в другие разделы матанализа.

[_hum_]

Pavia

(Оффтоп)

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