2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Знак в процедуре стохастической аппроксимации
Сообщение10.12.2016, 21:49 


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

 Профиль  
                  
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение10.12.2016, 22:03 
Заслуженный участник


05/08/14
1564
_hum_ в сообщении #1175774 писал(а):
но как узнать неубывающая или невозрастающая

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

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

 Профиль  
                  
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение10.12.2016, 22:25 


23/12/07
1757
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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение10.12.2016, 23:24 


23/12/07
1757
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 
Заслуженный участник


05/08/14
1564
_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 


23/12/07
1757
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 
Заслуженный участник


05/08/14
1564
_hum_ в сообщении #1175816 писал(а):
что непонятного? взял в качестве ${\alpha}_i = \alpha$, где $\alpha \in (0,1)$.

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

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

 Профиль  
                  
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение11.12.2016, 00:52 


23/12/07
1757
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 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Знак в процедуре стохастической аппроксимации
Сообщение13.12.2016, 20:55 
Заслуженный участник


05/08/14
1564
_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 


23/12/07
1757
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 
Аватара пользователя


31/10/08
1244
_hum_
Что-то я сразу не обратил внимания метод итерационный. Я слабо их знаю.
_hum_ в сообщении #1176963 писал(а):
И еще непонятно, почему не придумали процедуру, которая бы сама знак подбирала (типа - если при одном знаке идет увеличение ошибки, то надо выбрать противоположный).

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

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

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

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

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


23/12/07
1757
Pavia

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group