Выборка с отклонением

Выборка с отклонением — метод, используемый для семплирования сложных вероятностных распределений.

Постановка задачи

Для семплирования вероятностного распределения $f(x)$ выборка с отклонением используется тогда, когда форма $f(x)$ делает семплирование напрямую сложным.

Генерация семплов по $f(x)$ происходит с помощью более простого вспомогательного распределения $g(x)$ , которое мы можем просемплировать, и которое удовлетворяет следующему условию:

\forall x\ \ f(x)<cg(x)

, где

c>1

Алгоритм

Взять семпл $x$ по распределению $g(x)$ ;
Выбрать случайное число $u$ равномерно из отрезка $[0,cg(x)]$ ;
Вычислить $f(x)$ $f(x)$ ;
- Если $u\leq f(x)$ , то $x$ добавляется к семплам;
- Если $u>f(x)$ , то $x$ отклоняется (отсюда и название метода).

Алгоритм выбирает точки $[x,u]$ равномерно из области под графиком $f(x)$ , а это и означает что получаются семплы $f(x)$ .

Примеры

Приведем простой геометрический пример. Предположим, мы хотим выбрать случайную точку внутри окружности единичного радиуса.

Сгенерируем точку $(x,y)$ выбрав $x$ и $y$ как независимые произвольные числа из отрезка $[-1,1]$ . Если получится так, что $x^{2}+y^{2}\leq 1$ , то это означает что точка лежит внутри круга, и должна быть принята. В противном случае точка отклоняется, и генерируется следующая.

В качестве еще одного примера можно рассмотреть алгоритм Зиккурат, в основе которого лежит выборка с отклонением. Этот алгоритм используется для генерирования неравномерно распределенных случайных чисел.

Проблемы

Проблемы, как правило, возникают при решении задач большой размерности.

При этом $c$ будет очень большим (экспоненциальным от размерности), и почти все семплы будут отвергаться.

Ссылки

Николенко С. Курс «Вероятностное обучение».

Read other articles:

SMA Negeri 1 Bandung

Artikel ini terlalu bergantung pada referensi dari sumber primer. Mohon perbaiki artikel ini dengan menambahkan sumber sekunder atau tersier. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) SMA Negeri 1 BandungInformasiDidirikan1950JenisNegeriAkreditasiANomor Statistik Sekolah301026006037Nomor Pokok Sekolah Nasional20219271Kepala SekolahDrs. Agung Indaryatno, M.M.Pd)Ketua KomiteDrs. Aqil Faruq, S.H.Jumlah kelas11 kelas setiap tingkatJurusan atau peminatanMIP...

Fakultas Sains dan Teknologi Universitas Airlangga

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Januari 2023. Artikel ini membutuhkan penyuntingan lebih lanjut mengenai tata bahasa, gaya penulisan, hubungan antarparagraf, nada penulisan, atau ejaan. Anda dapat membantu untuk menyuntingnya. Artikel ini terlalu bergantung pada referensi dari sumber primer. Mohon...

Marines

Military organization specialized in amphibious warfare United States Marines aboard USS Wasp engage Royal Marines on HMS Reindeer in 1814 Marines, or naval infantry, are soldiers who specialise at operating in littoral zones, both on land and at sea. Historically, the main tasks undertaken by marines have included raiding ashore in support of naval objectives, and the boarding of vessels during combat or capture of prize ships. Marines also help maintain discipline and order aboard...

The Gadfly (play)

The GadflyWritten byGeorge Bernard ShawDate premieredunproducedOriginal languageEnglishSubjectA devout Catholic becomes a devout revolutionary.Genrenovel adaptationSettingvarious The Gadfly or The Son of the Cardinal (1897-8) is a dramatic adaptation by George Bernard Shaw of Anglo-Irish writer Ethel Lilian Voynich (née Boole)'s novel The Gadfly. It was written as a favour to the author, who was a friend of Shaw's. Creation The Gadfly, a novel about a young man's embrace of revolutionary po...

Antwerpen (arondisemen)

Arrondissement of Antwerp Arrondissement AntwerpenArrondissement of BelgiumLocation of the arrondissement in AntwerpNegara BelgiumRegion FlandersProvince AntwerpMunicipalities30Luas • Total1.000,31 km2 (38,622 sq mi)Populasi (1 January 2015) • Total1.027.342 • Kepadatan00/km2 (0/sq mi)Zona waktuUTC+1 (CET) • Musim panas (DST)UTC+2 (CEST) Antwerpen (Belanda: Arrondissement Antwerpencode: nl is deprecated ; ...

Jepang selama Perang Dunia I

Pasukan Jepang mendarat di dekat Tsingtao. Bagian dari seri artikel mengenaiSejarah Jepang PeriodePaleolitiksebelum 14.000 SMJōmon14.000–300 SMYayoi300 SM – 250 MKofun250–538Asuka538–710Nara710–794Heian794–1185Kamakura1185–1333Restorasi Kemmu1333–1336Muromachi (Ashikaga) Nanboku-chōSengoku 1336–1573Azuchi–Momoyama Perdagangan dengan Nanban 1568–1603Edo (Tokugawa) SakokuPersetujuan KanagawaBakumatsu 1603–1868Meiji Perang BoshinRestorasiPerang Sino-Jepang PertamaPember...

جامع قمرية

جامع قمرية مئذنة جامع قَمَرية، أبريل 2021 معلومات عامة القرية أو المدينة بغداد/ الكرخ الدولة العراق تاريخ بدء البناء 626 هـ/1228م المواصفات المساحة 2000م2 عدد المصلين 400 عدد المآذن 1 عدد القباب 6 التفاصيل التقنية المواد المستخدمة الطابوق التصميم والإنشاء النمط المعماري إسلامية ال...

Чайки

У этого термина существуют и другие значения, см. Чайки (значения). Чайки Доминиканская чайкаЗападная чайкаКалифорнийская чайкаМорская чайка Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:Вторич...

Россотрудничество

Федеральное агентство по делам Содружества Независимых Государств, соотечественников, проживающих за рубежом, и по международному гуманитарному сотрудничествусокращённо: Россотрудничество Общая информация Страна Россия Юрисдикция Россия Дата создания 6 сентября...

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

Washburn Ichabods men's basketball

College basketball team Washburn Ichabods men's basketballUniversityWashburn UniversityFirst season1905–06All-time record1,622–1,097–2 (.596)Head coachBrett Ballard (5th season)ConferenceThe MIAALocationTopeka, KansasArenaLee Arena (Capacity: 4,150)NicknameIchabodsColorsYale blue and white[1] Uniforms Home Away NCAA tournament championsNational Association of Intercollegiate Athletics1987NCAA tournament Final FourNational Association of Intercollegiate...

1942 Japanese general election

1942 Japanese general election ← 1937 30 April 1942 1946 → All 466 seats in the House of Representatives234 seats needed for a majority First party Leader Hideki Tojo Party Taisei Yokusankai Last election 421 Seats won 381 Prime Minister before election Hideki Tojo Taisei Yokusankai Prime Minister after election Hideki Tojo Taisei Yokusankai This article is part of a series onPolitics of Japan Constitution and Laws Constitution of Japan (1947–p...

Crocus City Hall attack

2024 mass shooting and explosion in Krasnogorsk, Russia Crocus City Hall attackPart of Islamic State insurgency in the North Caucasus, terrorism in Russia and Islamic terrorism in EuropeThe Crocus City Hall auditorium after the terrorist attack (25 March)LocationCrocus City Hall, Krasnogorsk, Moscow Oblast, RussiaCoordinates55°49′33″N 37°23′25″E / 55.82583°N 37.39028°E / 55.82583; 37.39028Date22 March 2024; 2 months ago (2024-03-22) 19:58�...

Carate Brianza

Carate Brianzacomune Carate Brianza – VedutaLa prepositurale dei Santi Ambrogio e Simpliciano LocalizzazioneStato Italia Regione Lombardia Provincia Monza e Brianza AmministrazioneSindacoLuca Veggian (FI) dal 25-6-2018 (2º mandato dal 15-5-2023) TerritorioCoordinate45°41′N 9°14′E45°41′N, 9°14′E (Carate Brianza) Altitudine250 m s.l.m. Superficie9,92 km² Abitanti17 883[1] (31-10-2023) Densità1 802,72 ab./km² F...

Disastro di Seveso

Disastro di Sevesodisastro ambientaleIntervento di emergenza dopo il rilascio della nube tossica TipoIncidente industriale Datasabato 10 luglio 197612:28 – 12:37 LuogoSeveso, Meda, Cesano Maderno, Desio, Barlassina, Bovisio Masciago, Nova Milanese e in porzioni minori anche Seregno, Varedo e Lentate sul Seveso Stato Italia Coordinate45°39′14.59″N 9°08′53.77″E45°39′14.59″N, 9°08′53.77″E ConseguenzeMorti0 esseri umani; 3 300 animali (altri 76 000 abbattu...

Grinding (dance)

Suggestive club dancing Freak Dance redirects here. For the 2011 film, see Freak Dance (film). A man and woman grinding. Grinding, also known as juking, freak dancing or freaking (in the Caribbean, wining[1]) is an intimate and romantic close partner dance where two or more dancers rub or bump their bodies against each other, usually with a female dancer rubbing or bumping her buttocks against a male dancer's genital area. The male dancer will typically place his hands on the female d...

小田原之戰

小田原之戰日本戰國時代的一部分小田原城復元天守日期1590年2月-7月（舊曆：天正十八年二月-七月）地点神奈川縣小田原市、關東一帶结果豐臣政權統一日本参战方豐臣軍北條軍指挥官与领导者豐臣秀吉北條氏政兵力總石高超過1500萬石本隊 161,135人船手眾（水軍）20,630人穴太眾3~4萬人北國眾 35,000人（有各種說法）總石高不超過250萬石總兵力不超過62,500人一般號稱有56,0...

2012–13 PFC CSKA Sofia season

CSKA Sofia 2012–13 football seasonCSKA Sofia2012–13 seasonChairman Dimitar BorisovManager Stoycho Mladenov(until 4 January) Miodrag Ješić (until 11 March) Milen Radukanov(from 11 March)A Group Third placeBulgarian CupQuarterfinalUEFA Europa League2nd qualifying round Home colours Away colours ← 2011–122013–14 → The 2012–13 season was PFC CSKA Sofia's 65th consecutive season in A Group. This article shows player statistics and all matches (official and friendl...

Agriculture in the State of Palestine

Palestinian farmers harvesting olives using traditional methods Agriculture in the State of Palestine is a mainstay in the economy of the State of Palestine. The production of agricultural goods supports the population's sustenance needs and fuels Palestine's export economy.[1] According to the Council for European Palestinian Relations, the agricultural sector formally employs 13.4% of the population and informally employs 90% of the population.[1] In the late 2000s unemploy...

Sazeret

Cet article est une ébauche concernant une commune de l’Allier. Vous pouvez partager vos connaissances en l’améliorant (comment ?). Le bandeau {{ébauche}} peut être enlevé et l’article évalué comme étant au stade « Bon début » quand il comporte assez de renseignements encyclopédiques concernant la commune. Si vous avez un doute, l’atelier de lecture du projet Communes de France est à votre disposition pour vous aider. Consultez également la page d’aide ...

PROFILPELAJAR.COM