From a84de59e6b43eab11692bf815ac1443e024e7c1a Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andr=C3=A9=20Nusser?= <andre.nusser@googlemail.com>
Date: Thu, 23 Aug 2018 13:27:21 +0200
Subject: Continued. Suggestion of algorithm.

---
 sampling_alg.tex | 31 +++++++++++++++++++------------
 1 file changed, 19 insertions(+), 12 deletions(-)

(limited to 'sampling_alg.tex')

diff --git a/sampling_alg.tex b/sampling_alg.tex
index 0fe08df..682f4b5 100644
--- a/sampling_alg.tex
+++ b/sampling_alg.tex
@@ -100,27 +100,34 @@ I will list a number of drawbacks of this algorithm in the following. These will
 \paragraph{History of Size One.} Currently, we only remember the last sample that was played. This seriously limits us to select samples well. Imagine that there are several samples of similar power. We currently rely on the normal distribution solving this, even though using round robin like sampling would result in more diverse samples being chosen while not deviating significantly more from $l$.
 
 \subsection{Related Work}
-Velocity Layers. Round Robin and Random Selection.\todo{Is there actually any academic related work? What is actually the mathematical problem that we are trying to solve?}
+Velocity Layers. Round Robin and Random Selection.Is there actually any academic related work? What is actually the mathematical problem that we are trying to solve?
 
 \section{Requirements}
-\subsection{Pseudo Normal Distribution}
-\subsection{Round Robin for Specific Cases}
-\subsection{Modification to Round Robin}
-If all powers are the same we probably still want some randomness to avoid getting patterns of the length of the round robin cycle.
-\subsection{No Staircase Effect}
-\subsection{Equal Probability}
-This means that all samples have almost equal probability of being played as their neighboring samples.
-% \section{Problematic Special Cases}
-% \subsection{Same Power Values}
-% \subsection{Middle Samples}
-% \subsection{I'm sure there are more\dots}
+\paragraph{Normal Distribution.} The samples should roughly be drawn from a normal distribution.
+\paragraph{Avoid Same Samples.} When we have multiple samples to choose from we should always take one which was last played far enough in the past.
+\paragraph{Randomization.} To avoid patterns (like e.g. in round robin), we want some form of randomization.
+\paragraph{Equal Probability.} Locally, samples should have almost the same probability of being chosen.
 
 \section{Suggested Algorithms}
 \subsection{Resampling}
+Resample from normal distribution until we find a fitting sample. This seems rather wasteful.
+
 \subsection{Objective Function}
+Define an objective function which depends on the history of samples and the current power requested -- or better, a power which comes from the normal distribution of the power requested. The sample that we choose is then the one which minimizes this objective function. This is a nice way to balance the two contradictory requirements of sampling by normal distribution and avoiding samples that were just played.
+
+The rough algorithm should go as follows. A sample with power $l$ is requested. We draw one sample from the normal distribution around $l$ and call it $p$. Let $t_q$ be the time at which $q$ was played last (the unit does not matter as it is parametrized by $\beta$ anyway), and let $r(q,t)$ be a random number generator uniformly producing numbers in the range $[0,1]$. At the current time $t$, we now want to find the sample $q$ minimizing the objective function
+\[
+	f(q, t) \coloneqq \alpha \cdot (p-q)^2 + \beta \cdot (t_q - t)^{-2} + \gamma \cdot r(q,t).
+\]
 
 \section{Experiments}
 \subsection{Methods of Evaluation}
+\begin{itemize}
+\item mean squared error to straight line from min power to max power
+\item histogram of distance to closest next same sample (to check that diverse samples are selected; picture!). Or maybe some other measurement, not sure.
+\item Histogram of how often samples were played. This should be a uniforum distribution (at least locally). Globally it might diverge from that as the sampling is worse for some powers.
+\item mean square error to gaussian curve (to check that we still use something similar to a normal distribution; picture!)
+\end{itemize}
 \subsection{Experimental Evaluation}
 
 \section{Conclusion}
-- 
cgit v1.2.3

