weightedchoice_importance_sampling.md

(WIP) Weighted random choice and importance sampling

• Some Keywords: Fitness proportionate selection, roulette wheel selection

Weighted Random Choice

Implemented in C++

• https://en.cppreference.com/w/cpp/numeric/random/discrete_distribution

Implemented in Python

numpy.random.choice

• https://docs.scipy.org/doc/numpy-1.14.0/reference/generated/numpy.random.choice.html
• IMPORTANT: You have to convert weight to probability first IE: (weight divide by total sum of all weights)

Importance Sampling

• Must Read: (start only with the resampling section of the notebook)
  • https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python/blob/master/12-Particle-Filters.ipynb
• Some sampling algorithms:
  • Multinomial Resampling (binary search O(n log (n))
  • Residual Resampling
  • Stratified Resampling
  • Systematic Resampling

Applications where I personally used this:

• Particle Filters (includes localization of robots) - Implemented
• Genetic algorithms - Implemented
• Reinforcement Learning: DQN with Priority Experience Replay - Currently Implementing

Priority Experience Replay Links - sumtree is used

• Read section Efficient Implementation only
  • https://jaromiru.com/2016/11/07/lets-make-a-dqn-double-learning-and-prioritized-experience-replay/

Related Short Videos

• 2:59 https://www.youtube.com/watch?v=DhxRxG5bSrg
• 3:12 https://www.youtube.com/watch?v=wNQVo6uOgYA
• 3:22 https://www.youtube.com/watch?v=aHLslaWO-AQ