Разлика между версии на „Стохастична апроксимация“

Версия от 16:14, 3 април 2014

Стохастичната апроксимация (СА) (на английски: Stochastic approximation) е част от алгоритмите на Стохастичната оптимизация, опитваща се да намери центъра или края на функции, които не могат да се изчислят директно, а може само чрез наблюдение да се предположи възможното изчисление. Първите подобни алгоритми от този вид са тези на Робинс-Монро и Кийфър-Уоилфовитц. Тези алгоритми са все още в експериментална фаза.

Същност

Стохастичните оптимизационни методи са оптимизационни алгоритми, които включват вероятностни елементи или в проблемната информация, или в самите алгоритми, или и в двете неща. Тяхната концепция контрастира с детерминистичните оптимизационни методи, където стойностите на функциите се предполага, че са точни числа и изчисленията са напълно определени от възможните стойности.

Алгоритъм на Кийфър-Уоловиц

Алгоритъма на Кийфър-Уоловиц е представен година след този на Робинсън –Монро. Той се опитва да намери максимума, х0, от неизвестните M(x) и да построи последователност х1, х2 изпълняващи формулата

Според този алгоритъм α1, α 2,…. са последователни положителни числа, като в алгоритъма на Робинсън-Монро, и c1,c2,.. са последователност от положителни числа, използвани да се изчисли , чрез метода на крайните числа, производната на M. Кийфър-Уоловиц доказват, че ако an и cn задоволяват различшни граници и M(x) и N(x) задоволяват няколко технически изисквания последователноста от xn се доближава до x0

Последвало развитие

Обширна теоретична литература е нараснал около тези алгоритми, относно условията за конвергенция, степента на конвергенция, многовариантността, избор на размерът на стъпката, възможни модели за шум и много други. Тези методи се прилагат и в теория на управлението, когато искаме да оптимизираме нашите функции. В този случай размерът на стъпката не трябва да клони към нула, а трябва да се подбира така, че да задоволява нашите нужди.

Йохан Мазрелиз и Дъглас Мартин са първите използвали стохастична апроксимация през 1975, когато са се занимавали с линейна оценка.

Вижте още

Източници

Робинсън и Монро, „Летописи на математическата статистика” 1951г.
Мазрелиз и Мартин, „Линейна оценка чрез стохастична апроксимация” 1975г.
Надежда Николаевна Бек, Дмитрий И. Голенко, Статистические методы оптимизации в экономических исследованиях
Мишев, Георги. Цветков, Стоян. Статистика за икономисти. София, Денеб-Консулт, 1995г.

Външни препратки

@@ Ред 3: / Ред 3: @@
 ==Същност==
 Стохастичните оптимизационни методи са оптимизационни алгоритми, които включват вероятностни елементи или в проблемната информация, или в самите алгоритми, или и в двете неща. Тяхната концепция контрастира с [[детерминистичните оптимизационни методи]], където стойностите на [[функциите]] се предполага, че са точни числа и изчисленията са напълно  определени от възможните стойности.
-==Алгоритъм на Робинс-Монро==
-В алгоритъма на Робинс-Монро, представен през 1951 г., има функция ''M''(''x'') , която позволява да се намери стойноста на ''x'',&nbsp;''x''0 задоволяваща уравнението ''M''(''x''0) = α . Най-важното, което се наблюдава не е ''M''(''x'') , а произволна променлива ''N''(''x'') , като ''E''(''N''(''x'') |&nbsp;''x'') =&nbsp;''M''(''x'') . Основната задача на алгоритъма е да построи последователноста х1.х2,... задоволяваща:
-[[image: newp.jpg|alt=]]
-Според този алгоритъм α1, α 2,…. са последователни положителни числа. Робинс и Монро доказват, че ако ''N''(''x'') е еднакво ограничено, ''M''(''x'') не намалява, ''M'''(''x''0) съществува и е положително и, че ако ''an  ''задоволява редица изисквания, тогава ''xn'' клони към ''L''2 в ''x''0.  В общият случай ''an '' трябва да се изравни с 1 /&nbsp;''n.'' Въпреки това, зада се осигури сближаване те трябва да клонят към нула и да се сближават много бавно.
 ==Алгоритъм на Кийфър-Уоловиц==