# A.I. & Optimization

## KPI Statistics: Online Computation

In this post we explain the importance of using online algorithms for computing KPI's statistics efficiently when dealing with collecting a stream of data observations in real-time.

### KPI Computation

There are different scenarios where a company is collecting a large amount of data from its products (e.g. users interaction with a game) such as the time each user spends in the game or amount of money each user spends to purchase in-app items. Most of the times companies need to compute some baisc KPIs (key performance indicators) and display them on a Dashboard so that Execs/Dev/Sale/Marketing teams can get first-hand insights on how the product is performing over time and focus their energy/time on effective strategies to improve the main KPI's (e.g. users average LTV).

Thus, computing basic/advanced stats around selected metrics such as means and standard deviations in real time becomes a basic need. One way to compute the statistics on important KPIs is to strore all data and then run the required computation on it once a while in order to update stats over time. This naive computation takes at least n steps when the size of data is n.

### KPI Statistics: Online Computation

However, there are more efficient techniques to update the stats of a stream of observations which saves us time/memory complexities. We can employ a recursive inceremental way to compute metrics where we use every new observed sample to update the current state of the KPI's stat. For instance for computing mean of a sequence using an Online approach one should implement the following formula:


$\bar{x}_{n}=\dfrac{x_{n}+(n-1)&space;\times&space;\bar{x}_{n-1}}{n}=\bar{x}_{n-1}+\dfrac{x_{n}-\bar{x}_{n-1}}{n}$


Using above recurrence equation, one can update the expectation for the given KPI as new observation arrives in constant time. This helps minimize space and time complexities and consequently save money on servers. One can also use online algorithms to compute the standard deviation of a random variable by computing $M_{2,n}$:


$M_{2,n}=M_{2,n-1}+(x_{n}-\bar{x}_{n-1})(x_{n}-\bar{x}_{n})$


Having $M_{2,n}$, we compute the sample variance (i.e. $s_{n}^{2}$) and the population variance (i.e. $\sigma_{n}^{2}$) as follows (this algorithm is due to Knuth) [1]:


$\sigma_{n}^{2}=\dfrac{M_{2,n}}{n}$
$s_{n}^{2}=\dfrac{M_{2,n}}{n-1}$


### Sample Code

See online algorithm for a simple python script demonstrating how one can use online algorithms to compute mean/std for a sequence of data. We also discussed Multi-Armed Bandit Algorithms as another example of online techniques for the purpose of optimization.