2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение10.12.2016, 22:03 
_hum_ в сообщении #1175774 писал(а):
но как узнать неубывающая или невозрастающая

Подставить 2 значения аргумента в функцию.
_hum_ в сообщении #1175774 писал(а):
откуда же человек, не имеющий этой функции (а иначе смысла в процедуре бы не было) под рукой,

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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение10.12.2016, 22:25 
dsge в сообщении #1175777 писал(а):
_hum_ в сообщении #1175774 писал(а):
но как узнать неубывающая или невозрастающая

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

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

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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение10.12.2016, 23:24 
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)$

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение10.12.2016, 23:57 
_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 писал(а):
В общем случае

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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение11.12.2016, 00:18 
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 писал(а):
В общем случае

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

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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение11.12.2016, 00:30 
_hum_ в сообщении #1175816 писал(а):
что непонятного? взял в качестве ${\alpha}_i = \alpha$, где $\alpha \in (0,1)$.

Так ничего не сойдется.
_hum_ в сообщении #1175816 писал(а):
какая функция?

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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение11.12.2016, 00:52 
dsge в сообщении #1175822 писал(а):
_hum_ в сообщении #1175816 писал(а):
что непонятного? взял в качестве ${\alpha}_i = \alpha$, где $\alpha \in (0,1)$.

Так ничего не сойдется.
_hum_ в сообщении #1175816 писал(а):
какая функция?

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


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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение12.12.2016, 07:08 
Аватара пользователя
_hum_
В википедии неписано что это инженерный подход. Так что некоторые неточнгсти и допущения могут быть и могут выбираться по желанию человека.

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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение13.12.2016, 20:55 
_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$.
В книге Вазан (или Невельсон и Хасьминский?) есть пример о влиянии удобрений на урожайность. При данном количестве удобрений урожайность является случайной вкличиной, однако в среднем, чем больше удобрений, тем больше урожайность - откуда и берется монотонность. Задача найти количество удобрений, обеспечивающих заданную урожайность в среднем.

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

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

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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение15.12.2016, 09:22 
Аватара пользователя
_hum_
Что-то я сразу не обратил внимания метод итерационный. Я слабо их знаю.
_hum_ в сообщении #1176963 писал(а):
И еще непонятно, почему не придумали процедуру, которая бы сама знак подбирала (типа - если при одном знаке идет увеличение ошибки, то надо выбрать противоположный).

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

_hum_ в сообщении #1176963 писал(а):
Эту процедуру что никто сегодня не использует?

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

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

 
 
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение15.12.2016, 10:09 
Pavia

(Оффтоп)

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

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group