ตัวกรองอนุภาคหรือที่รู้จักกันในชื่อ วิธีการ มอนเตคาร์โลแบบลำดับคือชุดของ อัลกอริธึ มมอนเตคาร์โลที่ใช้ในการค้นหาคำตอบโดยประมาณสำหรับปัญหาการกรองสำหรับระบบปริภูมิสถานะที่ไม่เป็นเชิงเส้น เช่นการประมวลผลสัญญาณและ การอนุมานทางสถิติแบบเบ ย์เซียน^{[ 1 ]}ปัญหาการกรองประกอบด้วยการประมาณสถานะภายในในระบบไดนามิกเมื่อมีการสังเกตบางส่วนและมีการรบกวนแบบสุ่มในเซ็นเซอร์และในระบบไดนามิก วัตถุประสงค์คือการคำนวณการแจกแจงความน่าจะเป็นภายหลังของสถานะของกระบวนการมาร์คอฟโดยพิจารณาจากการสังเกตที่มีเสียงรบกวนและบางส่วน คำว่า "ตัวกรองอนุภาค" ถูกบัญญัติขึ้นครั้งแรกในปี 1996 โดย Pierre Del Moral เกี่ยวกับวิธีการอนุภาคที่มีปฏิสัมพันธ์แบบสนามเฉลี่ยที่ใช้ในกลศาสตร์ของไหลตั้งแต่ต้นทศวรรษ 1960 ^{[ 2 ]}คำว่า "มอนเตคาร์โลแบบลำดับ" ถูกบัญญัติขึ้นโดยJun S. Liuและ Rong Chen ในปี 1998 ^{[ 3 ]}

การกรองอนุภาคใช้ชุดอนุภาค (เรียกอีกอย่างว่าตัวอย่าง) เพื่อแสดงการแจกแจงความน่าจะเป็นภายหลังของกระบวนการสุ่มโดยพิจารณาจากการสังเกตที่มีเสียงรบกวนและ/หรือบางส่วน แบบจำลองปริภูมิสถานะสามารถเป็นแบบไม่เชิงเส้นได้ และการแจกแจงสถานะเริ่มต้นและเสียงรบกวนสามารถมีรูปแบบใดก็ได้ตามต้องการ เทคนิคการกรองอนุภาคเป็นวิธีการที่ได้รับการยอมรับอย่างดี^{[ 2 ] [ 4 ] [ 5 ]}สำหรับการสร้างตัวอย่างจากการแจกแจงที่ต้องการโดยไม่ต้องมีข้อสมมติเกี่ยวกับแบบจำลองปริภูมิสถานะหรือการแจกแจงสถานะ อย่างไรก็ตาม วิธีการเหล่านี้ทำงานได้ไม่ดีเมื่อนำไปใช้กับระบบที่มีมิติสูงมาก

ตัวกรองอนุภาคจะอัปเดตการทำนายในลักษณะโดยประมาณ (ทางสถิติ) ตัวอย่างจากการกระจายจะถูกแทนด้วยชุดของอนุภาค แต่ละอนุภาคจะมีน้ำหนักความน่าจะเป็นที่กำหนดให้กับมัน ซึ่งแสดงถึงความน่าจะเป็นที่อนุภาคนั้นจะถูกสุ่มจากฟังก์ชันความหนาแน่นของความน่าจะเป็น ความไม่สมดุลของน้ำหนักที่นำไปสู่การยุบตัวของน้ำหนักเป็นปัญหาทั่วไปที่พบในอัลกอริธึมการกรองเหล่านี้ อย่างไรก็ตาม สามารถลดปัญหานี้ได้โดยการเพิ่มขั้นตอนการสุ่มตัวอย่างใหม่ก่อนที่น้ำหนักจะไม่เท่ากัน สามารถใช้เกณฑ์การสุ่มตัวอย่างใหม่แบบปรับได้หลายอย่าง รวมถึงความแปรปรวนของน้ำหนักและเอนโทรปี สัมพัทธ์ ที่เกี่ยวข้องกับการกระจายแบบสม่ำเสมอ^{[ 6 ]}ในขั้นตอนการสุ่มตัวอย่างใหม่ อนุภาคที่มีน้ำหนักน้อยมากจะถูกแทนที่ด้วยอนุภาคใหม่ที่อยู่ใกล้กับอนุภาคที่มีน้ำหนักมากกว่า

จากมุมมองทางสถิติและความน่าจะเป็น ตัวกรองอนุภาคอาจถูกตีความว่าเป็นการตีความอนุภาคสนามเฉลี่ย ของ การวัดความน่าจะเป็น ของ Feynman-Kac ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]}เทคนิคการบูรณาการอนุภาคเหล่านี้ได้รับการพัฒนาในเคมีโมเลกุลและฟิสิกส์เชิงคำนวณโดยTheodore E. HarrisและHerman Kahnในปี 1951, Marshall N. RosenbluthและArianna W. Rosenbluthในปี 1955 ^{[ 12 ]}และล่าสุดโดย Jack H. Hetherington ในปี 1984 ^{[ 13 ]}ในฟิสิกส์เชิงคำนวณ วิธีการบูรณาการอนุภาคเส้นทางประเภท Feynman-Kac เหล่านี้ยังใช้ในQuantum Monte Carloและโดยเฉพาะอย่างยิ่งวิธีการ Diffusion Monte Carlo ^{[ 14 ] [ 15 ] [ 16 ]}วิธีการอนุภาคปฏิสัมพันธ์ของ Feynman-Kac ยังมีความเกี่ยวข้องอย่างมากกับอัลกอริธึมทางพันธุกรรมแบบการกลายพันธุ์และการคัดเลือกที่ใช้ในปัจจุบันในการคำนวณเชิงวิวัฒนาการเพื่อแก้ปัญหาการเพิ่มประสิทธิภาพที่ซับซ้อน

ระเบียบวิธีตัวกรองอนุภาคใช้ในการแก้ ปัญหา แบบจำลองมาร์คอฟที่ซ่อนอยู่ (HMM) และ ปัญหา การกรองแบบไม่เชิงเส้นยกเว้นแบบจำลองสัญญาณ-การสังเกตเชิงเส้น-เกาส์เซียน ( ตัวกรอง Kalman ) หรือแบบจำลองประเภทที่กว้างกว่า (ตัวกรอง Benes ^{[ 17 ]} ) Mireille Chaleyat-Maurel และ Dominique Michel ได้พิสูจน์ในปี 1984 ว่าลำดับของการแจกแจงแบบโพสทีเรียร์ของสถานะสุ่มของสัญญาณ เมื่อพิจารณาจากการสังเกต (หรือที่เรียกว่าตัวกรองที่เหมาะสมที่สุด) ไม่มีการเวียนเกิดแบบจำกัด^{[ 18 ]}วิธีการเชิงตัวเลขอื่นๆ ที่ใช้การประมาณค่ากริดคงที่เทคนิคMarkov Chain Monte Carlo การทำให้เป็นเชิงเส้นแบบดั้งเดิม ตัวกรอง Kalman แบบขยายหรือการกำหนดระบบเชิงเส้นที่ดีที่สุด (ในแง่ของต้นทุน-ข้อผิดพลาดที่คาดหวัง) ไม่สามารถรับมือกับระบบขนาดใหญ่ กระบวนการที่ไม่เสถียร หรือความไม่เชิงเส้นที่ไม่เรียบเพียงพอได้

ตัวกรองอนุภาคและระเบียบวิธีอนุภาค Feynman-Kac พบการประยุกต์ใช้ใน การ ประมวลผลสัญญาณและภาพ การอนุมานแบบเบย์เซียนการ เรียนรู้ ของเครื่องการวิเคราะห์ความเสี่ยงและการสุ่มตัวอย่างเหตุการณ์หายากวิศวกรรมและหุ่นยนต์ปัญญาประดิษฐ์ชีวสารสนเทศ [ ^{19 ]}พันธุศาสตร์เชิงวิวัฒนาการวิทยาศาสตร์การคำนวณเศรษฐศาสตร์^และการเงินเชิงคณิตศาสตร์เคมีโมเลกุล ฟิสิกส์เชิงคำนวณเภสัชจลนศาสตร์ความเสี่ยงเชิงปริมาณและการประกันภัย^{[ 20 ] [ 21 ]}และสาขาอื่นๆ

จากมุมมองทางสถิติและความน่าจะเป็น ตัวกรองอนุภาคจัดอยู่ในกลุ่มของอัลกอริทึมแบบแตกแขนง / แบบพันธุกรรม และระเบียบวิธีอนุภาคแบบมีปฏิสัมพันธ์ประเภทสนามเฉลี่ยการตีความวิธีการอนุภาคเหล่านี้ขึ้นอยู่กับสาขาวิทยาศาสตร์ ในการคำนวณเชิงวิวัฒนาการระเบียบ วิธี อนุภาคแบบพันธุกรรมประเภทสนามเฉลี่ยมักถูกใช้เป็นอัลกอริทึมการค้นหาแบบฮิวริสติกและแบบธรรมชาติ (หรือที่เรียกว่า เมตาฮิวริสติก ) ในฟิสิกส์เชิงคำนวณและเคมีโมเลกุลพวกมันถูกใช้เพื่อแก้ ปัญหา การอินทิเกรตเส้นทาง ของ Feynman-Kac หรือเพื่อคำนวณค่า Boltzmann-Gibbs ค่าลักษณะเฉพาะสูงสุด และสถานะพื้นฐานของ ตัวดำเนินการ Schrödingerในชีววิทยาและพันธุศาสตร์พวกมันแสดงถึงวิวัฒนาการของประชากรของแต่ละบุคคลหรือยีนในสภาพแวดล้อมบางอย่าง

ที่มาของ เทคนิคการคำนวณเชิงวิวัฒนาการแบบสนามเฉลี่ยสามารถสืบย้อนไปได้ถึงปี 1950 และ 1954 ด้วยงานของ Alan Turing เกี่ยวกับเครื่องจักรการเรียนรู้แบบการกลายพันธุ์และการคัดเลือกทางพันธุกรรม ^{[ 22 ]}และบทความของNils Aall Barricelliที่Institute for Advanced StudyในPrinceton รัฐนิวเจอร์ซีย์^{[ 23 ] [ 24 ]}ร่องรอยแรกของตัวกรองอนุภาคในวิธีการทางสถิติย้อนกลับไปในช่วงกลางทศวรรษ 1950; 'Poor Man's Monte Carlo' ^{[ 25 ]}ที่เสนอโดยJohn Hammersleyและคณะในปี 1954 มีคำแนะนำเกี่ยวกับวิธีการกรองอนุภาคแบบพันธุกรรมที่ใช้ในปัจจุบัน ในปี 1963 Nils Aall Barricelliได้จำลองอัลกอริทึมแบบพันธุกรรมเพื่อเลียนแบบความสามารถของแต่ละบุคคลในการเล่นเกมง่ายๆ^{[ 26 ]}ใน วรรณกรรม การคำนวณเชิงวิวัฒนาการอัลกอริทึมการคัดเลือกการกลายพันธุ์แบบพันธุกรรมได้รับความนิยมจากผลงานสำคัญของJohn Hollandในช่วงต้นทศวรรษ 1970 โดยเฉพาะหนังสือของเขา^{[ 27 ]}ที่ตีพิมพ์ในปี 1975

ในชีววิทยาและพันธุศาสตร์นักพันธุศาสตร์ชาวออสเตรเลียAlex Fraserยังได้ตีพิมพ์บทความชุดหนึ่งเกี่ยวกับการจำลองทางพันธุกรรมของการคัดเลือกเทียมของสิ่งมีชีวิต ในปี พ.ศ. 2490 ^{[ 28 ]}การจำลองวิวัฒนาการด้วยคอมพิวเตอร์โดยนักชีววิทยาเริ่มแพร่หลายมากขึ้นในช่วงต้นทศวรรษ พ.ศ. 2503 และวิธีการต่างๆ ได้รับการอธิบายไว้ในหนังสือของ Fraser และ Burnell (1970) ^{[ 29 ]}และ Crosby (1973) ^{[ 30 ]}การจำลองของ Fraser ประกอบด้วยองค์ประกอบสำคัญทั้งหมดของอัลกอริทึมอนุภาคทางพันธุกรรมการกลายพันธุ์และการคัดเลือกสมัยใหม่

จากมุมมองทางคณิตศาสตร์การกระจายแบบมีเงื่อนไขของสถานะสุ่มของสัญญาณที่กำหนดโดยการสังเกตบางส่วนและมีสัญญาณรบกวนจะถูกอธิบายโดยความน่าจะเป็นของ Feynman-Kac บนวิถีสุ่มของสัญญาณที่ถ่วงน้ำหนักด้วยลำดับของฟังก์ชันศักยภาพความน่าจะเป็น^{[ 7 ] [ 8 ]} วิธี Quantum Monte Carloและโดยเฉพาะอย่างยิ่งวิธี Diffusion Monte Carloสามารถตีความได้ว่าเป็นค่าประมาณอนุภาคประเภทพันธุกรรมสนามเฉลี่ยของปริพันธ์เส้นทาง Feynman-Kac ^{[ 7 ] [ 8 ] [ 9 ] [ 13 ] [ 14 ] [ 31 ] [ 32 ]}ต้นกำเนิดของ วิธีการ Quantum Monte Carloมักถูกยกให้เป็นผลงานของEnrico FermiและRobert Richtmyerซึ่งพัฒนาการตีความอนุภาคแบบ mean-field ของปฏิกิริยาลูกโซ่นิวตรอน ในปี 1948 [ ^{33 ] แต่ขั้นตอนวิธี อนุภาค}แบบฮิวริสติกและแบบพันธุกรรม (หรือที่เรียกว่าวิธีการ Resampled หรือ Reconfiguration Monte Carlo) สำหรับการประมาณพลังงานสถานะพื้นฐานของระบบควอนตัม (ในแบบจำลองเมทริกซ์ลดรูป) นั้นเป็นผลงานของ Jack H. Hetherington ในปี 1984 ^{[ 13 ]}นอกจากนี้ยังสามารถอ้างถึงผลงานสำคัญก่อนหน้านี้ของTheodore E. HarrisและHerman Kahnในฟิสิกส์อนุภาคที่ตีพิมพ์ในปี 1951 ซึ่งใช้วิธีการแบบ mean-field แต่เป็นแบบฮิวริสติกและแบบพันธุกรรมสำหรับการประมาณพลังงานการส่งผ่านอนุภาค^{[ 34 ]}ในเคมีโมเลกุล การใช้วิธีการอนุภาคแบบฮิวริสติกทางพันธุกรรม (หรือที่เรียกว่ากลยุทธ์การตัดแต่งและการเสริมคุณค่า) สามารถสืบย้อนไปได้ถึงปี 1955 ด้วยผลงานสำคัญของMarshall N. RosenbluthและArianna W. Rosenbluth ^{[ 12 ]}

การใช้อัลกอริทึมอนุภาคทางพันธุกรรมในการประมวลผลสัญญาณ ขั้นสูง และการอนุมานแบบเบย์เซียนนั้นค่อนข้างใหม่ ในเดือนมกราคม พ.ศ. 2536 Genshiro Kitagawa ได้พัฒนา "ตัวกรองมอนเตคาร์โล" ^{[ 35 ]}เวอร์ชันที่แก้ไขเล็กน้อยของบทความนี้ปรากฏใน พ.ศ. 2539 ^{[ 36 ]}ในเดือนเมษายน พ.ศ. 2536 Neil J. Gordon และคณะ ได้ตีพิมพ์งานสำคัญของพวกเขา^{[ 37 ]}เกี่ยวกับการประยุกต์ใช้อัลกอริทึมประเภทพันธุกรรมในการอนุมานทางสถิติแบบเบย์เซียน ผู้เขียนตั้งชื่ออัลกอริทึมของพวกเขาว่า 'ตัวกรองบูตสแตรป' และแสดงให้เห็นว่าเมื่อเปรียบเทียบกับวิธีการกรองอื่นๆ อัลกอริทึมบูตสแตรปของพวกเขาไม่จำเป็นต้องมีข้อสมมติใดๆ เกี่ยวกับพื้นที่สถานะหรือสัญญาณรบกวนของระบบ ในขณะเดียวกัน งานวิจัยของ Pierre Del Moral ^{[ 2 ]}และ Himilcon Carvalho, Pierre Del Moral, André Moninและ Gérard Salut ^{[ 38 ]}เกี่ยวกับตัวกรองอนุภาคที่ตีพิมพ์ในช่วงกลางทศวรรษ พ.ศ. 2533 ก็ได้รับการตีพิมพ์ โดยอิสระเช่นกัน ตัวกรองอนุภาคยังได้รับการพัฒนาในการประมวลผลสัญญาณในช่วงต้นปี 1989–1992 โดย P. Del Moral, JC Noyer, G. Rigal และ G. Salut ในLAAS-CNRSในชุดรายงานการวิจัยที่จำกัดและเป็นความลับร่วมกับ STCAN (Service Technique des Constructions et Armes Navales), บริษัทไอที DIGILOG และLAAS-CNRS (ห้องปฏิบัติการวิเคราะห์และสถาปัตยกรรมของระบบ) เกี่ยวกับปัญหาการประมวลผลสัญญาณ RADAR/SONAR และ GPS ^{[ 39 ] [ 40 ] [ 41 ] [ 42 ] [ 43 ] [ 44 ]}

ตั้งแต่ปี 1950 ถึงปี 1996 สิ่งพิมพ์ทั้งหมดเกี่ยวกับตัวกรองอนุภาคและอัลกอริทึมทางพันธุกรรม รวมถึงวิธีการตัดแต่งและการสุ่มตัวอย่างแบบมอนเตคาร์โลที่นำเสนอในฟิสิกส์เชิงคำนวณและเคมีโมเลกุล ล้วนนำเสนออัลกอริทึมที่เป็นธรรมชาติและคล้ายฮิวริสติกที่นำไปใช้กับสถานการณ์ต่างๆ โดยปราศจากการพิสูจน์ความสอดคล้องหรือการอภิปรายเกี่ยวกับอคติของการประมาณค่าและอัลกอริทึมที่อิงตามลำดับวงศ์ตระกูลและต้นไม้บรรพบุรุษแม้แต่น้อย

พื้นฐานทางคณิตศาสตร์และการวิเคราะห์อย่างเข้มงวดครั้งแรกของอัลกอริธึมอนุภาคเหล่านี้มาจาก Pierre Del Moral ^{[ 2 ] [ 4 ]}ในปี 1996 บทความ^{[ 2 ]}ยังมีการพิสูจน์คุณสมบัติที่ไม่เอนเอียงของการประมาณอนุภาคของฟังก์ชันความน่าจะเป็นและ การวัด ความน่าจะเป็นแบบมีเงื่อนไข ที่ไม่เป็นมาตรฐาน ตัวประมาณอนุภาคที่ไม่เอนเอียงของฟังก์ชันความน่าจะเป็นที่นำเสนอในบทความนี้ถูกนำมาใช้ในปัจจุบันในการอนุมานทางสถิติแบบเบย์เซียน

Dan Crisan, Jessica Gaines และTerry Lyons [ ^{45 ] [ 46 ] [ 47 ] รวม}ถึง Pierre Del Moral และ Terry Lyons ^{[ 48 ]}ได้สร้างเทคนิคอนุภาคแบบแตกแขนงที่มีขนาดประชากรต่างๆ กันในช่วงปลายทศวรรษ 1990 P. Del Moral, A. Guionnet และ L. Miclo ^{[ 8 ] [ 49 ] [ 50 ]} ได้พัฒนาเพิ่มเติมในเรื่องนี้ในปี 2000 Pierre Del Moral และ Alice Guionnet ^{[ 51 ]}ได้พิสูจน์ทฤษฎีบทขีดจำกัดกลางครั้งแรกในปี 1999 และ Pierre Del Moral และ Laurent Miclo ^{[ 8 ]}ได้พิสูจน์ทฤษฎีบทเหล่านั้นในปี 2000 ผลลัพธ์การบรรจบกันแบบสม่ำเสมอครั้งแรกเกี่ยวกับพารามิเตอร์เวลาสำหรับตัวกรองอนุภาคได้รับการพัฒนาในช่วงปลายทศวรรษ 1990 โดย Pierre Del Moral และAlice Guionnet ^{[ 49 ] [ 50 ]}การวิเคราะห์อย่างเข้มงวดครั้งแรกของตัวกรองอนุภาคแบบต้นไม้ตามลำดับวงศ์ตระกูลเป็นผลงานของ P. Del Moral และ L. Miclo ในปี 2544 ^{[ 52 ]}

ทฤษฎีเกี่ยวกับระเบียบวิธีอนุภาค Feynman-Kac และอัลกอริธึมตัวกรองอนุภาคที่เกี่ยวข้องได้รับการพัฒนาในปี 2000 และ 2004 ในหนังสือ^{[ 8 ] [ 5 ]}แบบจำลองความน่าจะเป็นเชิงนามธรรมเหล่านี้ครอบคลุมอัลกอริธึมประเภทพันธุกรรม อนุภาค และตัวกรองบูตสแตรป ตัวกรอง Kalman แบบโต้ตอบ (หรือที่เรียกว่าตัวกรองอนุภาค Rao–Blackwellized ^{[ 53 ]} ) เทคนิค การสุ่มตัวอย่างความสำคัญและเทคนิคการสุ่มตัวอย่างซ้ำแบบอนุภาค รวมถึงระเบียบวิธีแบบต้นไม้ทางสายเลือดและแบบย้อนกลับของอนุภาคสำหรับการแก้ปัญหาการกรองและการปรับให้เรียบ วิธีการกรองอนุภาคประเภทอื่นๆ ได้แก่ โมเดลแบบต้นไม้ตามลำดับวงศ์ตระกูล^{[ 10 ] [ 5 ] [ 54 ]}โมเดลอนุภาค Markov ย้อนกลับ^{[ 10 ] [ 55 ]}โมเดลอนุภาคสนามเฉลี่ยแบบปรับตัว^{[ 6 ]}โมเดลอนุภาคแบบเกาะ^{[ 56 ] [ 57 ]}วิธีการ Monte Carlo แบบลูกโซ่ Markov อนุภาค^{[ 58 ] [ 59 ]}ตัวสุ่ม Monte Carlo แบบลำดับ^{[ 60 ] [ 61 ] [ 62 ]}และวิธีการคำนวณ Bayesian โดยประมาณแบบลำดับ Monte Carlo ^{[ 63 ]}และ Bayesian Bootstrap แบบลำดับ Monte Carlo ABC ^{[ 64 ]}

เป้าหมายของตัวกรองอนุภาคคือการประมาณความหนาแน่นของความน่าจะเป็นภายหลังของตัวแปรสถานะ โดยพิจารณาจากตัวแปรสังเกต ตัวกรองอนุภาคมีจุดประสงค์เพื่อใช้กับแบบจำลองมาร์คอฟแบบซ่อนเร้นซึ่งระบบประกอบด้วยทั้งตัวแปรซ่อนเร้นและตัวแปรสังเกตได้ ตัวแปรสังเกตได้ (กระบวนการสังเกต) เชื่อมโยงกับตัวแปรซ่อนเร้น (กระบวนการสถานะ) ผ่านรูปแบบฟังก์ชันที่ทราบ ในทำนองเดียวกัน คำอธิบายเชิงความน่าจะเป็นของระบบพลวัตที่กำหนดวิวัฒนาการของตัวแปรสถานะก็เป็นที่รู้จักเช่นกัน

ตัวกรองอนุภาคทั่วไปจะประมาณการการแจกแจงความน่าจะเป็นภายหลังของสถานะที่ซ่อนอยู่โดยใช้กระบวนการวัดการสังเกต โดยพิจารณาจากปริภูมิสถานะดังที่แสดงด้านล่าง:

${\displaystyle {\begin{array}{cccccccccc}X_{0}&\to &X_{1}&\to &X_{2}&\to &X_{3}&\to &\cdots &{\text{signal}}\\\downarrow &&\downarrow &&\downarrow &&\downarrow &&\cdots &\\Y_{0}&&Y_{1}&&Y_{2}&&Y_{3}&&\cdots &{\text{observation}}\end{array}}}$

ปัญหาการกรองคือการประมาณค่าของสถานะที่ซ่อนอยู่ตามลำดับ โดยพิจารณาจาก ค่าของกระบวนการสังเกตณ ช่วงเวลาใดๆk${\displaystyle X_{k}}$${\displaystyle Y_{0},\cdots ,Y_{k},}$

การประมาณค่าแบบเบย์ทั้งหมดได้มาจากความหนาแน่นของความน่าจะเป็นภายหลังระเบียบวิธีตัวกรองอนุภาคให้ค่าประมาณของความน่าจะเป็นแบบมีเงื่อนไขเหล่านี้โดยใช้การวัดเชิงประจักษ์ที่เกี่ยวข้องกับอัลกอริทึมอนุภาคแบบพันธุกรรม ในทางตรงกันข้าม วิธีการมาร์คอฟเชน มอนเตคาร์โล หรือการสุ่มตัวอย่างแบบสำคัญจะจำลองความน่าจะเป็นภายหลังแบบเต็มรูปแบบ ${\displaystyle X_{k}}$${\displaystyle p(x_{k}|y_{0},y_{1},...,y_{k})}$${\displaystyle p(x_{0},x_{1},...,x_{k}|y_{0},y_{1},...,y_{k})}$

วิธีการทางอนุภาคมักจะตั้งสมมติฐาน และ สามารถจำลอง การสังเกตการณ์ ได้ในรูปแบบนี้:${\displaystyle X_{k}}$${\displaystyle Y_{k}}$

• ${\displaystyle X_{0},X_{1},\cdots }$เป็นกระบวนการมาร์คอฟบน(สำหรับบางค่า) ที่วิวัฒนาการไปตามความหนาแน่นของความน่าจะเป็นของการเปลี่ยนสถานะแบบจำลองนี้มักเขียนในรูปแบบสังเคราะห์ว่า ${\displaystyle \mathbb {R} ^{d_{x}}}$${\displaystyle d_{x}\geqslant 1}$${\displaystyle p(x_{k}|x_{k-1})}$

  ${\displaystyle X_{k}|X_{k-1}=x_{k}\sim p(x_{k}|x_{k-1})}$

โดยมีความหนาแน่นของความน่าจะเป็นเริ่มต้น${\displaystyle p(x_{0})}$

• ค่า ที่สังเกตได้ จะอยู่ในปริภูมิสถานะบางอย่างบน(สำหรับบางค่า) และเป็นอิสระต่อกันแบบมีเงื่อนไขก็ต่อเมื่อทราบค่า กล่าวอีกนัยหนึ่งคือ แต่ละค่าขึ้นอยู่กับ เท่านั้นนอกจากนี้ เรายังสมมติว่าการแจกแจงแบบมีเงื่อนไขสำหรับเมื่อกำหนดให้เป็นแบบต่อเนื่องสัมบูรณ์ และในทางสังเคราะห์เรามี ${\displaystyle Y_{0},Y_{1},\cdots }$${\displaystyle \mathbb {R} ^{d_{y}}}$${\displaystyle d_{y}\geqslant 1}$${\displaystyle X_{0},X_{1},\cdots }$${\displaystyle Y_{k}}$${\displaystyle X_{k}}$${\displaystyle Y_{k}}$${\displaystyle X_{k}=x_{k}}$

  ${\displaystyle Y_{k}|X_{k}=y_{k}\sim p(y_{k}|x_{k})}$

ตัวอย่างของระบบที่มีคุณสมบัติเหล่านี้คือ:

${\displaystyle X_{k}=g(X_{k-1})+W_{k-1}}$

${\displaystyle Y_{k}=h(X_{k})+V_{k}}$

โดยที่ทั้งและเป็นลำดับอิสระต่อกันที่มีฟังก์ชันความหนาแน่นความน่าจะ เป็นที่ทราบ และgและhเป็นฟังก์ชันที่ทราบ สมการทั้งสองนี้สามารถมองได้ว่าเป็น สมการ ปริภูมิสถานะและมีลักษณะคล้ายกับสมการปริภูมิสถานะสำหรับตัวกรอง Kalman หากฟังก์ชันgและhในตัวอย่างข้างต้นเป็นเชิงเส้น และหากทั้งและเป็นแบบ Gaussianตัวกรอง Kalman จะพบการกระจายการกรองแบบ Bayesian ที่แม่นยำ หากไม่เป็นเช่นนั้น วิธีการที่ใช้ตัวกรอง Kalman จะเป็นการประมาณอันดับแรก ( EKF ) หรือการประมาณอันดับสอง ( UKFโดยทั่วไป แต่ถ้าการกระจายความน่าจะเป็นเป็นแบบ Gaussian การประมาณอันดับสามก็เป็นไปได้) ${\displaystyle W_{k}}$${\displaystyle V_{k}}$${\displaystyle W_{k}}$${\displaystyle V_{k}}$

ข้อสมมติที่ว่าการกระจายเริ่มต้นและการเปลี่ยนสถานะของห่วงโซ่มาร์คอฟมีความต่อเนื่องสำหรับการวัดแบบเลเบสสามารถผ่อนคลายได้ ในการออกแบบตัวกรองอนุภาค เราเพียงแค่ต้องสมมติว่าเราสามารถสุ่มตัวอย่างการเปลี่ยนสถานะของห่วงโซ่มาร์คอฟและคำนวณฟังก์ชันความน่าจะเป็นได้(ดูตัวอย่างเช่น คำอธิบายการกลายพันธุ์จากการคัดเลือกทางพันธุกรรมของตัวกรองอนุภาคที่กล่าวถึงด้านล่าง) ข้อสมมติเรื่องความต่อเนื่องของการเปลี่ยนสถานะของมาร์คอฟนั้นใช้เพื่ออนุมานสูตรที่แตกต่างกันระหว่างการกระจายความน่าจะเป็นภายหลังโดยใช้กฎของเบย์สสำหรับความหนาแน่นแบบมีเงื่อนไขในลักษณะที่ไม่เป็นทางการ (และค่อนข้างไม่ถูกต้อง) เท่านั้น ${\displaystyle X_{k-1}\to X_{k}}$${\displaystyle X_{k},}$${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$${\displaystyle X_{k}}$

ในปัญหาบางประการ การกระจายแบบมีเงื่อนไขของการสังเกต โดยพิจารณาจากสถานะสุ่มของสัญญาณ อาจไม่มีความหนาแน่น ซึ่งอาจเป็นไปไม่ได้หรือซับซ้อนเกินไปที่จะคำนวณ^{[ 19 ]}ในสถานการณ์นี้ จำเป็นต้องมีการประมาณค่าเพิ่มเติมอีกระดับหนึ่ง กลยุทธ์หนึ่งคือการแทนที่สัญญาณด้วยห่วงโซ่มาร์คอฟและแนะนำการสังเกตเสมือนในรูปแบบ ${\displaystyle X_{k}}$${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$

${\displaystyle {\mathcal {Y}}_{k}=Y_{k}+\epsilon {\mathcal {V}}_{k}\quad {\mbox{for some parameter}}\quad \epsilon \in [0,1]}$

สำหรับลำดับของตัวแปรสุ่มอิสระที่มีฟังก์ชันความหนาแน่นความน่าจะ เป็นที่ทราบแล้ว แนวคิดหลักคือการสังเกตว่า ${\displaystyle {\mathcal {V}}_{k}}$

${\displaystyle {\text{Law}}\left(X_{k}|{\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k}\right)\approx _{\epsilon \downarrow 0}{\text{Law}}\left(X_{k}|Y_{0}=y_{0},\cdots ,Y_{k}=y_{k}\right)}$

ตัวกรองอนุภาคที่เกี่ยวข้องกับกระบวนการ Markov ที่กำหนดโดยการสังเกตบางส่วนนั้นถูกกำหนดในแง่ของอนุภาคที่วิวัฒนาการด้วยฟังก์ชันความน่าจะเป็นที่กำหนดด้วยสัญกรณ์ที่ไม่เหมาะสมอย่างเห็นได้ชัดโดยเทคนิคความน่าจะเป็นเหล่านี้มีความเกี่ยวข้องอย่างใกล้ชิดกับการคำนวณแบบเบย์เซียนโดยประมาณ (ABC) ในบริบทของตัวกรองอนุภาค เทคนิคการกรองอนุภาค ABC เหล่านี้ได้รับการแนะนำในปี 1998 โดย P. Del Moral, J. Jacod และ P. Protter ^{[ 65 ]}และได้รับการพัฒนาเพิ่มเติมโดย P. Del Moral, A. Doucet และ A. Jasra ^{[ 66 ] [ 67 ]}${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$${\displaystyle {\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k},}$${\displaystyle \mathbb {R} ^{d_{x}+d_{y}}}$${\displaystyle p({\mathcal {Y}}_{k}|{\mathcal {X}}_{k})}$

กฎของเบย์สสำหรับความน่าจะเป็นแบบมีเงื่อนไขมีดังนี้:

${\displaystyle p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})={\frac {p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})}{p(y_{0},\cdots ,y_{k})}}}$

ที่ไหน

${\displaystyle {\begin{aligned}p(y_{0},\cdots ,y_{k})&=\int p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})dx_{0}\cdots dx_{k}\\p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})&=\prod _{l=0}^{k}p(y_{l}|x_{l})\\p(x_{0},\cdots ,x_{k})&=p_{0}(x_{0})\prod _{l=1}^{k}p(x_{l}|x_{l-1})\end{aligned}}}$

ตัวกรองอนุภาคก็เป็นการประมาณเช่นกัน แต่หากมีอนุภาคมากพอ ก็สามารถมีความแม่นยำมากขึ้นได้^{[ 2 ] [ 4 ] [ 5 ] [ 49 ] [ 50 ]}สมการการกรองแบบไม่เชิงเส้นกำหนดโดยการเรียกซ้ำ

โดยใช้ข้อตกลงสำหรับk = 0 ปัญหาการกรองแบบไม่เชิงเส้นประกอบด้วยการคำนวณการแจกแจงแบบมีเงื่อนไขเหล่านี้ตามลำดับ ${\displaystyle p(x_{0}|y_{0},\cdots ,y_{k-1})=p(x_{0})}$

เรากำหนดช่วงเวลา n และลำดับการสังเกตการณ์และสำหรับแต่ละk = 0, ..., nเราตั้งค่าดังนี้: ${\displaystyle Y_{0}=y_{0},\cdots ,Y_{n}=y_{n}}$

${\displaystyle G_{k}(x_{k})=p(y_{k}|x_{k}).}$

ในสัญลักษณ์นี้ สำหรับฟังก์ชันขอบเขตใดๆFบนเซตของวิถีโคจรจากจุดกำเนิดk = 0 จนถึงเวลาk = nเราจะได้สูตรของ Feynman-Kac ${\displaystyle X_{k}}$

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{n})p(x_{0},\cdots ,x_{n}|y_{0},\cdots ,y_{n})dx_{0}\cdots dx_{n}&={\frac {\int F(x_{0},\cdots ,x_{n})\left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}{\int \left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}}\\&={\frac {E\left(F(X_{0},\cdots ,X_{n})\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}}\end{aligned}}}$

แบบจำลองการบูรณาการเส้นทาง Feynman-Kac เกิดขึ้นในสาขาวิทยาศาสตร์หลายแขนง รวมถึงฟิสิกส์เชิงคำนวณ ชีววิทยา ทฤษฎีสารสนเทศ และวิทยาศาสตร์คอมพิวเตอร์^{[ 8 ] [ 10 ] [ 5 ]}การตีความขึ้นอยู่กับโดเมนการใช้งาน ตัวอย่างเช่น หากเราเลือกฟังก์ชันตัวบ่งชี้ของเซตย่อยบางส่วนของปริภูมิสถานะ ฟังก์ชันเหล่านี้จะแสดงถึงการกระจายแบบมีเงื่อนไขของห่วงโซ่ Markov โดยที่ห่วงโซ่นั้นยังคงอยู่ในท่อที่กำหนด นั่นคือ เรามี: ${\displaystyle G_{n}(x_{n})=1_{A}(x_{n})}$

${\displaystyle E\left(F(X_{0},\cdots ,X_{n})|X_{0}\in A,\cdots ,X_{n}\in A\right)={\frac {E\left(F(X_{0},\cdots ,X_{n})\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}}}$

และ

${\displaystyle P\left(X_{0}\in A,\cdots ,X_{n}\in A\right)=E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}$

ทันทีที่ค่าคงที่การทำให้เป็นมาตรฐานเป็นค่าบวกอย่างเคร่งครัด

ในขั้นต้น อัลกอริทึมดังกล่าวเริ่มต้นด้วยตัวแปรสุ่มอิสระN ตัว ที่มีความหนาแน่นความน่าจะเป็นร่วมกันการเปลี่ยนผ่านการคัดเลือก-การกลายพันธุ์ของอัลกอริทึมทางพันธุกรรม^{[ 2 ] [ 4 ]}${\displaystyle \left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}}$${\displaystyle p(x_{0})}$

${\displaystyle \xi _{k}:=\left(\xi _{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{selection}}{\longrightarrow }}{\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{mutation}}{\longrightarrow }}\xi _{k+1}:=\left(\xi _{k+1}^{i}\right)_{1\leqslant i\leqslant N}}$

เลียนแบบ/ประมาณการเปลี่ยนผ่านการอัปเดต-การทำนายของการวิวัฒนาการตัวกรองที่เหมาะสมที่สุด ( สมการที่ 1 ):

• ในระหว่างช่วงการเปลี่ยนผ่านของการเลือกและการปรับปรุงเราจะสุ่มตัวแปรสุ่มอิสระ (แบบมีเงื่อนไข) จำนวน N ตัว ซึ่งมีการแจกแจงร่วมกัน (แบบมีเงื่อนไข)${\displaystyle {\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle \sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})}$

โดยที่หมายถึงมาตรวัด Diracณ สถานะ a ที่กำหนด ${\displaystyle \delta _{a}}$

• ในระหว่างการเปลี่ยนผ่านจากการทำนายการกลายพันธุ์เราจะสุ่มตัวอย่างการเปลี่ยนผ่านจากอนุภาคที่เลือกแต่ละตัวอย่าง อิสระ${\displaystyle {\widehat {\xi }}_{k}^{i}}$

${\displaystyle {\widehat {\xi }}_{k}^{i}\longrightarrow \xi _{k+1}^{i}\sim p(x_{k+1}|{\widehat {\xi }}_{k}^{i}),\qquad i=1,\cdots ,N.}$

ในสูตรที่แสดงด้านบน หมายถึงฟังก์ชันความน่าจะเป็นที่ประเมินค่า ณ จุดและหมายถึงความหนาแน่นแบบมีเงื่อนไขที่ประเมินค่า ณ จุด. ${\displaystyle p(y_{k}|\xi _{k}^{i})}$${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$${\displaystyle x_{k}=\xi _{k}^{i}}$${\displaystyle p(x_{k+1}|{\widehat {\xi }}_{k}^{i})}$${\displaystyle p(x_{k+1}|x_{k})}$${\displaystyle x_{k}={\widehat {\xi }}_{k}^{i}}$

ในแต่ละช่วงเวลาkเราจะได้ค่าประมาณของอนุภาค

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})}$

และ

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1})}$

ในชุมชนอัลกอริทึมทางพันธุกรรมและการคำนวณเชิงวิวัฒนาการโซ่ Markov การกลายพันธุ์-การคัดเลือกที่อธิบายไว้ข้างต้นมักเรียกว่าอัลกอริทึมทางพันธุกรรมที่มีการคัดเลือกตามสัดส่วน มีการเสนอตัวแปรการแตกแขนงหลายแบบ รวมถึงขนาดประชากรแบบสุ่มในบทความต่างๆ^{[ 5 ] [ 45 ] [ 48 ]}

วิธีการแบบอนุภาค เช่นเดียวกับวิธีการสุ่มตัวอย่างอื่นๆ (เช่นMarkov Chain Monte Carlo ) จะสร้างชุดตัวอย่างที่ประมาณความหนาแน่นของการกรอง

${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k}).}$

ตัวอย่างเช่น เราอาจมี ตัวอย่าง Nตัวอย่างจากความน่าจะเป็นภายหลังโดยประมาณของโดยที่ตัวอย่างเหล่านั้นมีป้ายกำกับด้วยตัวยกดังนี้: ${\displaystyle X_{k}}$

${\displaystyle {\widehat {\xi }}_{k}^{1},\cdots ,{\widehat {\xi }}_{k}^{N}.}$

จากนั้น ค่าคาดหวังเกี่ยวกับการกระจายการกรองจะถูกประมาณโดย

${\displaystyle \int f(x_{k})p(x_{k}|y_{0},\cdots ,y_{k})\,dx_{k}\approx _{N\uparrow \infty }{\frac {1}{N}}\sum _{i=1}^{N}f\left({\widehat {\xi }}_{k}^{i}\right)=\int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})}$

สมการที่ 2

กับ

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})}$

โดยที่หมายถึงการวัดแบบ Diracณ สถานะ a ที่กำหนด ฟังก์ชันfในแบบปกติของ Monte Carlo สามารถให้ค่าโมเมนต์ฯลฯ ทั้งหมดของการกระจายได้จนถึงข้อผิดพลาดในการประมาณค่าบางอย่าง เมื่อสมการการประมาณค่า ( สมการที่ 2 ) เป็นจริงสำหรับฟังก์ชันf ที่มีขอบเขตใดๆ เราจะเขียนได้ว่า ${\displaystyle \delta _{a}}$

${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k}):=p(x_{k}|y_{0},\cdots ,y_{k})dx_{k}\approx _{N\uparrow \infty }{\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})}$

ตัวกรองอนุภาคสามารถตีความได้ว่าเป็นอัลกอริทึมอนุภาคประเภทพันธุกรรมที่วิวัฒนาการไปพร้อมกับการกลายพันธุ์และการคัดเลือก เราสามารถติดตามสายบรรพบุรุษได้

${\displaystyle \left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k-1,k}^{i},{\widehat {\xi }}_{k,k}^{i}\right)}$

ของอนุภาคสถานะสุ่มที่มีดัชนีล่าง l=0,...,k หมายถึงบรรพบุรุษของแต่ละบุคคลที่ระดับ l=0,...,k ในสถานการณ์นี้ เรามีสูตรการประมาณค่า ${\displaystyle i=1,\cdots ,N}$${\displaystyle {\widehat {\xi }}_{l,k}^{i}}$${\displaystyle {\widehat {\xi }}_{k,k}^{i}={\widehat {\xi }}_{k}^{i}}$

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})\,dx_{0}\cdots dx_{k}&\approx _{N\uparrow \infty }{\frac {1}{N}}\sum _{i=1}^{N}F\left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)\\&=\int F(x_{0},\cdots ,x_{k}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\end{aligned}}}$

สมการที่ 3

ด้วยการวัดเชิงประจักษ์

${\displaystyle {\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))}$

ในที่นี้Fหมายถึงฟังก์ชันที่ก่อตั้งขึ้นบนปริภูมิเส้นทางของสัญญาณ ในรูปแบบที่สังเคราะห์มากขึ้น ( สมการที่ 3 ) จะเทียบเท่ากับ

${\displaystyle {\begin{aligned}p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})\,dx_{0}\cdots dx_{k}\\&\approx _{N\uparrow \infty }{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\end{aligned}}}$

ตัวกรองอนุภาคสามารถตีความได้หลายวิธี จากมุมมองเชิงความน่าจะเป็น ตัวกรองอนุภาคจะสอดคล้องกับ การตีความ อนุภาคสนามเฉลี่ยของสมการการกรองแบบไม่เชิงเส้น การเปลี่ยนผ่านการอัปเดต-การทำนายของการวิวัฒนาการตัวกรองที่เหมาะสมที่สุดยังสามารถตีความได้ว่าเป็นการเปลี่ยนผ่านการคัดเลือก-การกลายพันธุ์แบบคลาสสิกทางพันธุกรรมของแต่ละบุคคล เทคนิคการสุ่มตัวอย่างความสำคัญตามลำดับให้การตีความอีกแบบหนึ่งของการเปลี่ยนผ่านของการกรองโดยเชื่อมโยงการสุ่มตัวอย่างความสำคัญกับขั้นตอนการสุ่มตัวอย่างบูตสแตรป สุดท้ายแต่ไม่ท้ายสุด ตัวกรองอนุภาคสามารถมองได้ว่าเป็นวิธีการยอมรับ-ปฏิเสธที่มาพร้อมกับกลไกการรีไซเคิล^{[ 10 ] [ 5 ]}

วิวัฒนาการของการกรองแบบไม่เชิงเส้นสามารถตีความได้ว่าเป็นระบบพลวัตในชุดของการวัดความน่าจะเป็นในรูปแบบที่หมายถึงการแมปบางอย่างจากชุดของการกระจายความน่าจะเป็นไปยังตัวมันเอง ตัวอย่างเช่น วิวัฒนาการของตัวทำนายที่เหมาะสมที่สุดแบบขั้นตอนเดียว${\displaystyle \eta _{n+1}=\Phi _{n+1}\left(\eta _{n}\right)}$${\displaystyle \Phi _{n+1}}$${\displaystyle \eta _{n}(dx_{n})=p(x_{n}|y_{0},\cdots ,y_{n-1})dx_{n}}$

สอดคล้องกับการวิวัฒนาการแบบไม่เชิงเส้น โดยเริ่มต้นจากการกระจายความน่าจะเป็น หนึ่งในวิธีที่ง่ายที่สุดในการประมาณค่ามาตรวัดความน่าจะเป็นเหล่านี้ คือการเริ่มต้นด้วยตัวแปรสุ่มอิสระN ตัว ที่มีการกระจายความน่าจะเป็นร่วมกัน สมมติว่าเราได้กำหนดลำดับของตัวแปรสุ่มN ตัว ไว้ดังนี้ ${\displaystyle \eta _{0}(dx_{0})=p(x_{0})dx_{0}}$${\displaystyle \left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}}$${\displaystyle \eta _{0}(dx_{0})=p(x_{0})dx_{0}}$${\displaystyle \left(\xi _{n}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{n}^{i}}(dx_{n})\approx _{N\uparrow \infty }\eta _{n}(dx_{n})}$

ขั้นตอนต่อไป เราจะสุ่มตัวแปรสุ่มอิสระ (แบบมีเงื่อนไข) จำนวนN ตัว โดยใช้กฎทั่วไป ${\displaystyle \xi _{n+1}:=\left(\xi _{n+1}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle \Phi _{n+1}\left({\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{n}^{i}}\right)\approx _{N\uparrow \infty }\Phi _{n+1}\left(\eta _{n}\right)=\eta _{n+1}}$

เราจะอธิบายหลักการของอนุภาคสนามเฉลี่ยนี้ในบริบทของการวิวัฒนาการของตัวทำนายที่ดีที่สุดแบบขั้นตอนเดียว

สำหรับk = 0 เราใช้ข้อตกลงนี้ ${\displaystyle p(x_{0}|y_{0},\cdots ,y_{-1}):=p(x_{0})}$

ตามกฎของจำนวนมาก เราจะได้ว่า

${\displaystyle {\widehat {p}}(dx_{0})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{0}^{i}}(dx_{0})\approx _{N\uparrow \infty }p(x_{0})dx_{0}}$

ในแง่ที่ว่า

${\displaystyle \int f(x_{0}){\widehat {p}}(dx_{0})={\frac {1}{N}}\sum _{i=1}^{N}f(\xi _{0}^{i})\approx _{N\uparrow \infty }\int f(x_{0})p(dx_{0})dx_{0}}$

สำหรับฟังก์ชันที่มีขอบเขตใดๆเรายังสมมติเพิ่มเติมว่าเราได้สร้างลำดับของอนุภาคที่อันดับk บางอันดับ แล้ว โดยที่ ${\displaystyle f}$${\displaystyle \left(\xi _{k}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }~p(x_{k}~|~y_{0},\cdots ,y_{k-1})dx_{k}}$

ในแง่ที่ว่าสำหรับฟังก์ชันที่มีขอบเขตใดๆเราจะมี ${\displaystyle f}$

${\displaystyle \int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})={\frac {1}{N}}\sum _{i=1}^{N}f(\xi _{k}^{i})\approx _{N\uparrow \infty }\int f(x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$

ในสถานการณ์นี้ เมื่อแทนที่ด้วยการวัดเชิงประจักษ์ในสมการวิวัฒนาการของตัวกรองที่เหมาะสมที่สุดแบบขั้นตอนเดียวที่ระบุไว้ใน ( สมการ 4 ) เราพบว่า ${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

${\displaystyle p(x_{k+1}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }\int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}'){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x''_{k}){\widehat {p}}(dx''_{k}|y_{0},\cdots ,y_{k-1})}}}$

โปรดสังเกตว่าด้านขวามือในสูตรข้างต้นคือส่วนผสมความน่าจะเป็นแบบถ่วงน้ำหนัก

${\displaystyle \int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}'){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x''_{k}){\widehat {p}}(dx''_{k}|y_{0},\cdots ,y_{k-1})}}=\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{j})}}p(x_{k+1}|\xi _{k}^{i})=:{\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})}$

โดยที่ แทนความหนาแน่นที่ประเมิน ณและแทนความหนาแน่นที่ประเมิน ณสำหรับ${\displaystyle p(y_{k}|\xi _{k}^{i})}$${\displaystyle p(y_{k}|x_{k})}$${\displaystyle x_{k}=\xi _{k}^{i}}$${\displaystyle p(x_{k+1}|\xi _{k}^{i})}$${\displaystyle p(x_{k+1}|x_{k})}$${\displaystyle x_{k}=\xi _{k}^{i}}$${\displaystyle i=1,\cdots ,N.}$

จากนั้น เราสุ่มตัวแปรสุ่มอิสระN ตัว ที่มีความหนาแน่นความน่าจะเป็นร่วมกัน เพื่อให้ ${\displaystyle \left(\xi _{k+1}^{i}\right)_{1\leqslant i\leqslant N}}$${\displaystyle {\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})}$

${\displaystyle {\widehat {p}}(dx_{k+1}|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k+1}^{i}}(dx_{k+1})\approx _{N\uparrow \infty }{\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})dx_{k+1}\approx _{N\uparrow \infty }p(x_{k+1}|y_{0},\cdots ,y_{k})dx_{k+1}}$

ด้วยการทำซ้ำขั้นตอนดังกล่าว เราจึงออกแบบห่วงโซ่มาร์คอฟได้ดังนี้

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1}):=p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$

โปรดสังเกตว่าตัวกรองที่เหมาะสมที่สุดจะถูกประมาณค่าในแต่ละช่วงเวลา k โดยใช้สูตรของเบย์ส

${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }{\frac {p(y_{k}|x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x'_{k}){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}}=\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k}^{j})}}~\delta _{\xi _{k}^{i}}(dx_{k})}$

คำศัพท์ "การประมาณค่าเฉลี่ยสนาม" มาจากข้อเท็จจริงที่ว่าเราแทนที่การวัดความน่าจะเป็นด้วยการประมาณเชิงประจักษ์ ในแต่ละขั้นตอนเวลา การประมาณอนุภาคค่าเฉลี่ยสนามของปัญหาการกรองนั้นห่างไกลจากความเป็นเอกลักษณ์ มีกลยุทธ์หลายอย่างที่พัฒนาขึ้นในหนังสือ^{[ 10 ] [ 5 ]}${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k-1})}$${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

การวิเคราะห์การบรรจบกันของตัวกรองอนุภาคเริ่มต้นในปี 1996 ^{[ 2 ] [ 4 ]}และในปี 2000 ในหนังสือ^{[ 8 ]}และชุดบทความ^{[ 48 ] [ 49 ] [ 50 ] [ 51 ] [ 52 ] [ 68 ] [ 69 ]}การพัฒนาล่าสุดสามารถพบได้ในหนังสือ^{[ 10 ] [ 5 ]}เมื่อสมการการกรองมีเสถียรภาพ (ในแง่ที่ว่ามันแก้ไขเงื่อนไขเริ่มต้นที่ผิดพลาดใดๆ) อคติและความแปรปรวนของการประมาณค่าอนุภาค

${\displaystyle I_{k}(f):=\int f(x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})\approx _{N\uparrow \infty }{\widehat {I}}_{k}(f):=\int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

ถูกควบคุมโดยการประมาณค่าสม่ำเสมอที่ไม่ใช่เชิงอะซิมโทติก

${\displaystyle \sup _{k\geqslant 0}\left\vert E\left({\widehat {I}}_{k}(f)\right)-I_{k}(f)\right\vert \leqslant {\frac {c_{1}}{N}}}$

${\displaystyle \sup _{k\geqslant 0}E\left(\left[{\widehat {I}}_{k}(f)-I_{k}(f)\right]^{2}\right)\leqslant {\frac {c_{2}}{N}}}$

สำหรับฟังก์ชันf ใดๆ ที่มีขอบเขตไม่เกิน 1 และสำหรับค่าคงที่จำกัดบางค่า นอกจากนี้ สำหรับ: ${\displaystyle c_{1},c_{2}.}$${\displaystyle x\geqslant 0}$

${\displaystyle \mathbf {P} \left(\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c_{1}{\frac {x}{N}}+c_{2}{\sqrt {\frac {x}{N}}}\land \sup _{0\leqslant k\leqslant n}\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c{\sqrt {\frac {x\log(n)}{N}}}\right)>1-e^{-x}}$

สำหรับค่าคงที่จำกัดบางค่าที่เกี่ยวข้องกับอคติเชิงอะซิมโทติกและความแปรปรวนของการประมาณค่าอนุภาค และค่าคงที่จำกัดc บาง ค่า ผลลัพธ์เดียวกันนี้ยังคงเป็นไปได้หากเราแทนที่ตัวทำนายที่เหมาะสมที่สุดแบบขั้นตอนเดียวด้วยการประมาณค่าตัวกรองที่เหมาะสมที่สุด ${\displaystyle c_{1},c_{2}}$

สืบย้อนรอยสายตระกูลไปในอดีต

${\displaystyle \left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k-1,k}^{i},{\widehat {\xi }}_{k,k}^{i}\right),\quad \left(\xi _{0,k}^{i},\xi _{1,k}^{i},\cdots ,\xi _{k-1,k}^{i},\xi _{k,k}^{i}\right)}$

ของแต่ละบุคคลและในแต่ละช่วงเวลาkเรายังมีการประมาณค่าอนุภาคด้วย ${\displaystyle {\widehat {\xi }}_{k}^{i}\left(={\widehat {\xi }}_{k,k}^{i}\right)}$${\displaystyle \xi _{k}^{i}\left(={\xi }_{k,k}^{i}\right)}$

${\displaystyle {\begin{aligned}{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\ \\{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\\&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k-1})dx_{0},\cdots ,dx_{k}\end{aligned}}}$

การประมาณเชิงประจักษ์เหล่านี้เทียบเท่ากับการประมาณเชิงปริพันธ์ของอนุภาค

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\ \\\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\end{aligned}}}$