tag:blogger.com,1999:blog-79940872320400332672024-03-14T00:10:18.448-07:00Pragmatic Programming TechniquesRicky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.comBlogger132125tag:blogger.com,1999:blog-7994087232040033267.post-90813582400903435452018-09-02T10:09:00.000-07:002018-09-02T10:09:02.809-07:00Structure Learning and Imitation LearningIn classical prediction use case, the predicted output is either a number (for regression) or category (for classification). A set of training data (x, y) where x is the input and y is the labeled output is provided to train a parameterized predictive model.<br />
<br />
<ul>
<li>The model is characterized by a set of parameters w</li>
<li>Given an input x, for the model predicts y_hat = f(x; w) for regression, or the model predicts the probability of each possible class for classification</li>
<li>Define a Lost function L(y, y_hat) for regression, or L(y, P(y=a | x), P(y=b | x) ...), find the parameters w to minimize L</li>
</ul>
<div>
This problem is typically view as an optimization problem, and use gradient descent approach to solve it.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhvxuWTtWqyaKF4ngBBaddnaT09UwLBc1H-nUolgTu0aSCulbjnVrsW0FifxgP-hspnBmspgLlb7GOxhw0DPAfLeAf3ChJrjQUIayWPNdKABAMDOPCrD7xePHGNeOezLBi1b_HN2JognLUY/s1600/Screen+Shot+2018-09-01+at+10.57.52+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="691" data-original-width="1600" height="170" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhvxuWTtWqyaKF4ngBBaddnaT09UwLBc1H-nUolgTu0aSCulbjnVrsW0FifxgP-hspnBmspgLlb7GOxhw0DPAfLeAf3ChJrjQUIayWPNdKABAMDOPCrD7xePHGNeOezLBi1b_HN2JognLUY/s400/Screen+Shot+2018-09-01+at+10.57.52+AM.png" width="400" /></a></div>
<div>
<br /></div>
<div>
<br /></div>
<h3>
Need for Structure Learning</h3>
<div>
However, in some cases, y is not as simple as a number or a class. For example</div>
<div>
<ul>
<li>For machine translation, x is a sentence in English, and y is a translated sentence in French</li>
<li>For self-driving-vehicle, x is a camera image, and y is the control action on steering wheel, brake, gas pedal</li>
</ul>
<div>
In these cases, the output y can be viewed as an object. But wait, can we break down the object as multiple numbers / categories and use the classical regression / classification approach to solve it ? Not quite, because the lost function cannot be just formulated as the summation of loss of individual components. For example, two French sentences using different words may still be a very good translation of the same English sentence. So we need to generalize a bit more and introduce the concept of an object and compatibility here.</div>
<div>
<br /></div>
<div>
The prediction problem can be generalized as: Given input x, finding an object y such that y is the "most compatible" with x. The compatibility is a parameterized function that we are going to learn from the training data.</div>
</div>
<div>
<ul>
<li>The compatibility function is defined as F(x, y; w)</li>
<li>During training phase, we tune parameter w such that for every sample in training data, F(x, y; w) is the maximum. In other words, F(x, Y=y; w) > F(x, Y=other_val; w)</li>
</ul>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhvvV3bmhDTaBOt4pb81o2ZpRwKIhPr_bVKPGtJiBa4_7aI1HrZ_M8K6Qt1s194NQHi1grx4Jj9z6FhsBTL4NgUQCTUFj47OksEkjQFJHgRPFc7EbCXOJ3JSGKzACVbgvi_fROKewvNfM8g/s1600/Screen+Shot+2018-09-01+at+5.02.25+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="656" data-original-width="1600" height="163" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhvvV3bmhDTaBOt4pb81o2ZpRwKIhPr_bVKPGtJiBa4_7aI1HrZ_M8K6Qt1s194NQHi1grx4Jj9z6FhsBTL4NgUQCTUFj47OksEkjQFJHgRPFc7EbCXOJ3JSGKzACVbgvi_fROKewvNfM8g/s400/Screen+Shot+2018-09-01+at+5.02.25+PM.png" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
</div>
<br />
Notice that the training process is different from classical ML in the following way.<div>
<ul>
<li>There are two optimization loop here. a) Given parameter w, find y_opt that maximize F(x,y,w). b) Given Lost = gap between F(x,y,w) and F(x,y_opt,w), find w that minimize the gap.</li>
<li>It turns out the first optimization is solved in a problem specific way while the second optimization can be solved by classical gradient descent approach.</li>
</ul>
After we learn the compatibility function parameters, at inference phase, we will apply the first optimization to the given input x to find the most compatible y_opt such that F(x, y_opt; w) is the maximum.</div>
<div>
<br /></div>
<div>
Rather than trying to exactly match y_hat to y in the training data, structure learning enable us to learn a more abstract relationship (ie: compatibility) between x and y so that we can output other equally-good y even it is not the same as the y in the training data. This more-generalized form is very powerful when we don't have a lot of training data. The downside of structure learning is it is compute intensive, because at inference phase it needs to solve an optimization problem which is typically expensive.</div>
<div>
<br /></div>
<h3>
Imitation Learning</h3>
<div>
In a typical setting of Reinforcement Learning, an digital agent observe the state from the environment, formulate its policy to determine an action that it believes will maximize its accumulative future reward, take the action, get the reward from the environment and transition to the next state. Reinforcement learning is about how the agent optimize its policy along its experience when interacting with the environment.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWOjhSAZ-jQ1ACa_KwDmp7GNIZcmoMP7XHAV1RZIxI2x52IZ_sCm02iy7rAZwoWRcNWYKKT_WXCNAPGb_kcXUeMoUOCiZdqpmExiYLH-041wCPdVMGlKEi7LffanhR_vDUu_4bdpFp931H/s1600/Screen+Shot+2018-09-02+at+9.33.25+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="540" data-original-width="842" height="205" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWOjhSAZ-jQ1ACa_KwDmp7GNIZcmoMP7XHAV1RZIxI2x52IZ_sCm02iy7rAZwoWRcNWYKKT_WXCNAPGb_kcXUeMoUOCiZdqpmExiYLH-041wCPdVMGlKEi7LffanhR_vDUu_4bdpFp931H/s320/Screen+Shot+2018-09-02+at+9.33.25+AM.png" width="320" /></a></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
For an <a href="http://horicky.blogspot.com/2017/08/reinforcement-learning-overview.html" target="_blank">overview of Reinforcement Learning</a> and basic algorithm, you can visit my previous blog <a href="http://horicky.blogspot.com/2017/08/reinforcement-learning-overview.html" target="_blank">here</a>.</div>
<div>
<br /></div>
<div>
Basically, reinforcement learning is based on a trial-and-error approach to learn the lesson. This approach can be very costly because during the trial process, serious mistake can be made (imagine if we use reinforcement learning to learn self-driving car, we may crash many cars before we learn something meaningful). In practice, people rely on simulator to mimic the environment. However, coming up good simulator is not easy because it requires a very deep understanding of how the actual environment behaves, this is one of the limitation that restrict reinforcement learning to be broadly applied.</div>
<div>
<br /></div>
<div>
Another important design consideration is how the reward is assigned. Of course, we can use the actual reward from the environment to train the policy, but this is usually very inefficient. Imagine when playing the chess game, we only get the reward at the end when we win/lose the game. Propagating this reward all the way to each move will be very inefficient. To make the learning faster, we usually use a technique called "reward shaping", basically to assign some artificial reward along the trajectory to bias the agent towards certain desirable actions (based on domain knowledge).</div>
<div>
<br /></div>
<div>
One special form of reward shaping is "imitation learning" where we assign intermediate reward based on how the action "similar" to when an expert does in real-life circumstances. Lets say we collect a set of observations that the expert is taking action y in state x, and try to learn a model that the agent will bias to take action y when seeing state x. But wait, does it sound like a supervised learning problem ? Can we just train a prediction model from x to y and we are done ?</div>
<div>
<br /></div>
<div>
Unfortunately, it is not as simple. Expert data is typically very sparse and expensive to get, meaning we usually don't have too many data from the expert. Imagine in a self-driving program, if we want to learn how to react when the car is almost crash, we may not find any situation in the expert's observation because the expert may not run into such dangerous situation at all. On the other hand, we don't need to copy exactly when the expert did in every situation, we just need to copy those that is relevant to the situation.</div>
<div>
<br /></div>
<div>
"Inverse Reinforcement Learning" comes into rescue. Basically, it cuts off the reward from the environment and replace it with a "reward estimator function", which is trained from a set of expert behavior, assuming that expert behavior will achieve highest reward.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj6NOh4qXHkFaL0TTFIpG-NiL_YWjVHszjPrJhu2Is3A9aizhEzDkAgxUgkXgoQoVuQsbX9Td3Kqk7UW-CW05FmCfSYX29e79_xG6-PnYdR4xrY8pAmj3c0aDDjAKlO2cLdqg96le3er_4v/s1600/Screen+Shot+2018-09-02+at+9.52.51+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="536" data-original-width="1028" height="166" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj6NOh4qXHkFaL0TTFIpG-NiL_YWjVHszjPrJhu2Is3A9aizhEzDkAgxUgkXgoQoVuQsbX9Td3Kqk7UW-CW05FmCfSYX29e79_xG6-PnYdR4xrY8pAmj3c0aDDjAKlO2cLdqg96le3er_4v/s320/Screen+Shot+2018-09-02+at+9.52.51+AM.png" width="320" /></a></div>
<div>
<br /></div>
<div>
Underlying algorithm of inverse reinforcement learning is based on the "structure learning" algorithm. In this case, the x is the start state, y is the output of the trajectory of the expert which is basically the training data. And y_opt is the output of the trajectory based on the agent policy, which is learned from the reward function using Reinforcement Learning algorithm. The compatibility function is basically our reward function because we assume expert behavior achieve highest reward.</div>
<div>
<br /></div>
<div>
Then we bring it the structure learning algorithm below ...</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjCOd_iS2YzJM8bL70pIHlA9Vz_WSOu0LW_T3K_Pm24tUFE4AKKYeL2bknXeQy_GT9QU4_XcmO4Og6G3MCyRsTX8pZ6rJL6N6wlHSFw051ZuAW312kS2twIv7YCDSNwWeU5bTaxCkY7RZPa/s1600/Screen+Shot+2018-09-02+at+10.00.34+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="842" data-original-width="1592" height="211" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjCOd_iS2YzJM8bL70pIHlA9Vz_WSOu0LW_T3K_Pm24tUFE4AKKYeL2bknXeQy_GT9QU4_XcmO4Og6G3MCyRsTX8pZ6rJL6N6wlHSFw051ZuAW312kS2twIv7YCDSNwWeU5bTaxCkY7RZPa/s400/Screen+Shot+2018-09-02+at+10.00.34+AM.png" width="400" /></a></div>
<div>
<br /></div>
<div>
The agent still need to interact with the environment (or simulator) to get its trajectory, but the environment only need to determine the next state, but not the reward. Again, there are two nested optimization loop in the algorithm</div>
<div>
<ul>
<li>Given a reward function (characterized by w), use classical RL to learn the optimal policy</li>
<li>Use the optimal policy to interact with the environment to collect the total reward of each episode, then adjust the reward function parameter w such that the expert behavior always get the highest total reward.</li>
</ul>
<div>
<br /></div>
</div>
<div>
<br /></div>
Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-61574079964992977832017-08-25T22:51:00.002-07:002017-08-25T22:57:59.637-07:00Reinforcement Learning Overview<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
There are basically 3 different types of Machine Learning<br />
<ul>
<li><b>Supervised Learning</b>: The major use case is Prediction. We provide a set of training data including the input and output, then train a model that can predict output from an unseen input.</li>
<li><b>Unsupervised Learning</b>: The major use case is Pattern extraction. We provide a set of data that has no output, the algorithm will try to extract the underlying non-trivial structure within the data.</li>
<li><b>Reinforcement Learning</b>: The major use case is Optimization. Mimicking how human learn from childhood, we use a trial and error approach to find out what actions will produce good outcome, and bias our preference towards those good actions.</li>
</ul>
</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
In this post, I will provide an overview of the settings of Reinforcement Learning as well as some of its key algorithms.</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<br /></div>
<h2 style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: large;">Agent / Environment Interaction</span></h2>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
Reinforcement Learning is all about how we can make good decision through trial and error. It is the interaction between the "agent" and the "environment". </div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<br /></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
Repeat the following steps until reaching a termination condition</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<ol>
<li>The agent observe the environment having state s</li>
<li>Out of all possible actions, the agent need to decide which action to take. (this is called "policy", which is a function that output an action given the current state)</li>
<li>Agent take the action, and the environment receive that action</li>
<li>Through a transition matrix model, environment determine what is the next state and proceed to that state</li>
<li>Through a reward distribution model, the environment determines the reward to the agent given he take action a at state s</li>
</ol>
</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<br /></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLNTO95YjdrPJdbF7h8EMhP2K3YMdNUvctP61R7eBxO0WQHXOkR0wDDuYKjRbJkpQR1Ixdo3MIVCGzp3h7hF7gQQu75t8NNxNNxo5ZHn8ogJmfTOmZHznHJybgy88-CP-Y1IQX-NmiEOiy/s1600/Picture1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1052" data-original-width="1525" height="275" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLNTO95YjdrPJdbF7h8EMhP2K3YMdNUvctP61R7eBxO0WQHXOkR0wDDuYKjRbJkpQR1Ixdo3MIVCGzp3h7hF7gQQu75t8NNxNNxo5ZHn8ogJmfTOmZHznHJybgy88-CP-Y1IQX-NmiEOiy/s400/Picture1.png" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<br /></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
The goal for the agent is to determine an optimal policy such that the "value" of the start state is maximized.</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<br /></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
Some terminology</div>
<div style="background-color: white; margin-bottom: 0px; margin-top: 0px;">
<ul>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">Episode: a sequence of (s1, a1, r1, s2, a2, r2, s3, a3, r3 .... st, at, rt ... sT, aT, rT)</span></li>
<li>Reward rt: Money the agent receive after taking action at a state at time t</li>
<li>Return: Cumulative reward since the action is taken (sum of rt, r[t+1], ... rT)</li>
<li>Value: Expected return at a particular state, called "state value" V(s), or expected return when taking action a at state s, called "Q Value" Q(s,a)</li>
</ul>
</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
The optimal policy can be formulated as choosing action a* amount all choices of a at state s such that Q(s, a*) is maximum.</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<br /></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
To deal with never ended interaction, we put a discount factor "gamma" on future reward. This discount factor will turn the sum of an infinite series into a finite number.</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<h3 style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: large;">Optimal Policy when model is known</span></h3>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;">If we know the "model", then figuring out the policy is easy. We just need to use dynamic programming technique to compute the optimal policy offline and there is no need for learning. </span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;">Two algorithms can be used: </span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;">"Value iteration" starts with a random value and iteratively update the value based on the Bellman's equation, and finally compute the "value" of each state or state/action pair (also call Q state). The optimal policy for a given state s is to choose the action a* that maximize the Q value, Q(s, a). </span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiulZbyzl8Gk1X8venK7IkVq3klq8LN3qKeUXx1zHE7aFcwKAxo_a7PiMS9ExW64Ygym0t9J7axDewaHLCt9Qa9S2XWXlwJq1kjybNYiAi3Lh_NRLYEWVj3kMJxgU6kiMBwQmyeCgp0m8sC/s1600/Picture1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1030" data-original-width="1600" height="255" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiulZbyzl8Gk1X8venK7IkVq3klq8LN3qKeUXx1zHE7aFcwKAxo_a7PiMS9ExW64Ygym0t9J7axDewaHLCt9Qa9S2XWXlwJq1kjybNYiAi3Lh_NRLYEWVj3kMJxgU6kiMBwQmyeCgp0m8sC/s400/Picture1.png" width="400" /></a></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;">Another algorithm "Policy iteration" starts with a random policy, and iteratively modifies the policy to make it better, until the </span><span style="font-size: 12pt;">policy at next iteration doesn't change any more.</span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhPM05tqnebAX7fJJUX1TnQvf_m2sKPOm51zyVn1oatrThX3kXsFVh8Md4jGkmKnS1iPp0_YCti3QMs9JJqHu3AYjsQawDSq0BFwCVuMli-WoeoSwLOC4EyqW0k-eaIVfOJlYL6YzXJKYA/s1600/Picture2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="605" data-original-width="1600" height="150" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhPM05tqnebAX7fJJUX1TnQvf_m2sKPOm51zyVn1oatrThX3kXsFVh8Md4jGkmKnS1iPp0_YCti3QMs9JJqHu3AYjsQawDSq0BFwCVuMli-WoeoSwLOC4EyqW0k-eaIVfOJlYL6YzXJKYA/s400/Picture2.png" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;">However, in practice, we usually don't know the model, so we cannot compute the optimal policy as described above.</span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<h3 style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: large;">Optimal Policy when model is unknown</span></h3>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;">One solution is the "model based" learning, we spare some time to find out the transition probability model as well as the reward distribution model. To make sure we experience all possible combinations of different state/action pairs, we will take random action in order to learn the model.</span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;">Once we learn the model, we can go back to use the value iteration or policy iteration to determine the optimal policy.</span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;">Learning has a cost though. Rather than taking the best action, we will take random action in order to explore new actions that we haven't tried before and it is very likely that the associated reward is not maximum. However we accumulate our knowledge about how the environment reacts under a wider range of scenarios and hopefully this will help us to get a better action in future. In other words, we sacrifice or trade off our short term gain for a long term gain. </span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;">Making the right balance is important. A common approach is to use the epsilon greedy algorithm. For each decision step, we allocate a small probability e where we take random action and probability (1-e) where we take the best known action we have explored before.</span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: 12pt;"><br /></span></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnUOt2q7r5-1NB8j87c0uy2totDBHrpk350zBHBrpQivnB5k6V2GvdWI1Qd3Nc61Bpw41roBi_vNGh2RpiOzQ4u7APCOkc_veYpPDJ8Hmk5hKejlClwM_44EAsXmzb_XBYYTYtPDmPuZzg/s1600/Picture4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="851" data-original-width="913" height="298" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnUOt2q7r5-1NB8j87c0uy2totDBHrpk350zBHBrpQivnB5k6V2GvdWI1Qd3Nc61Bpw41roBi_vNGh2RpiOzQ4u7APCOkc_veYpPDJ8Hmk5hKejlClwM_44EAsXmzb_XBYYTYtPDmPuZzg/s320/Picture4.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: small;"><span style="font-size: 12pt;">Another solution approach is the "model free" learning. Lets go back to look at the detail formula under Value iteration and Policy iteration, the reason of knowing the model is to calculate the expected value of state value and Q value. Can we directly figure out the expected state and Q value through trial and error ?</span></span></div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: small;"><span style="font-size: 12pt;"><br /></span></span></div>
<h3 style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: large;">Value based model free learning</span></h3>
<div style="background-color: white; margin-bottom: 0px; margin-top: 0px;">
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: small;"><span style="font-size: 12pt;">If we modify the Q value iteration algorithm to replace the expected reward/nextstate with the actual reward/nextstate, we arrive at the SARSA algorithm below.</span></span></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: small;"><span style="font-size: 12pt;"><br /></span></span></div>
<div class="separator" style="clear: both; font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjJxq5k2CAYYtKW1yaKsQRoNeMEnrxYruSg03HLjAn33-0N0_Q024-hWZfNKf7gaWOXr_IIAXDroSdoFzSueudR38FtTqOpC2mz1TVHei0KQSAo0dtG4OU_jttqXXvG6OH6V2lbkrpwIkmH/s1600/Picture1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="472" data-original-width="973" height="193" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjJxq5k2CAYYtKW1yaKsQRoNeMEnrxYruSg03HLjAn33-0N0_Q024-hWZfNKf7gaWOXr_IIAXDroSdoFzSueudR38FtTqOpC2mz1TVHei0KQSAo0dtG4OU_jttqXXvG6OH6V2lbkrpwIkmH/s400/Picture1.png" width="400" /></a></div>
<div class="separator" style="clear: both; font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px; text-align: center;">
<br /></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: small;"><span style="font-size: 12pt;"><br /></span></span></div>
<h2 style="font-family: calibri, helvetica, sans-serif, serif, emojifont; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: large;">Deep Q Learning </span></h2>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;">The algorithm above requires us to keep a table to remember all Q(s,a) values which can be huge, and also becomes infinite if any of the state or action is continuous. To deal with this, we will introduce the idea of value function. The state and action will become the input parameters of this function, which will create "input features" and then feed into a linear model and finally output the Q value.</span></span></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;"><br /></span></span></div>
<div class="separator" style="clear: both; font-family: calibri, helvetica, sans-serif, serif, emojifont; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZXs-K_S9cr8kcEBEp1iiqAScg6xDR7o96Whpa_j12DiDRHTGgjVFx5DDwmpb-DLb9zGqOZEBpH5XF7Bb4kBfVx4jksQ2J76Zc9yuNk37nfvBeLJHPiAtOCEuW3jmENJLzRrXofG1yq8I5/s1600/Picture1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="531" data-original-width="1600" height="131" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZXs-K_S9cr8kcEBEp1iiqAScg6xDR7o96Whpa_j12DiDRHTGgjVFx5DDwmpb-DLb9zGqOZEBpH5XF7Bb4kBfVx4jksQ2J76Zc9yuNk37nfvBeLJHPiAtOCEuW3jmENJLzRrXofG1yq8I5/s400/Picture1.png" width="400" /></a></div>
<div class="separator" style="clear: both; font-family: calibri, helvetica, sans-serif, serif, emojifont; text-align: center;">
<br /></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<br /></div>
<div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
Now we modify the previous SARSA algorithm to the following ...</div>
<br />
<ul>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">Instead of lookup the Q(s,a) value, we call the function (can be a DNN) to pass in the f(s, a) feature, and get its output</span></li>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">We randomly initialize the parameter of the function (can be weights if the function is a DNN)</span></li>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">We update the parameters using gradient descent on the lost which can be the difference between the estimated value and the target value (can be a one step look ahead estimation: r + gamma*max_a'[Q(s',a)] )</span></li>
</ul>
</div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<br /></div>
<div class="separator" style="clear: both; font-family: calibri, helvetica, sans-serif, serif, emojifont; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUbkWl-OtME2x-mUlM2UlV584Ms0UM8B6Nw5tuEiPD8sLVqjzckSO0UvkQOx9S2AKEXjX_M-ypNhE9INGpAJW5usumn87FPyl_f59CJD82ElXozmrgVbNnx8OIpKZYDSnOqrkA04JFCGvI/s1600/Picture1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="591" data-original-width="1548" height="243" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUbkWl-OtME2x-mUlM2UlV584Ms0UM8B6Nw5tuEiPD8sLVqjzckSO0UvkQOx9S2AKEXjX_M-ypNhE9INGpAJW5usumn87FPyl_f59CJD82ElXozmrgVbNnx8OIpKZYDSnOqrkA04JFCGvI/s640/Picture1.png" width="640" /></a></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;"><br /></span></span></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;">If we further generalize the Q value function using a deep neural network, and update the parameter using back propagation, then we reach a simple version of Deep Q Learning.</span></span></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;"><br /></span></span></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont;">
<div style="font-size: 16px;">
While this algorithm allow us to learn the Q value function which can represents a continuous state, we still need to evaluate every action and pick the one with the maximum Q value. In other words, the action space can only be discrete and finite.</div>
<div style="font-size: 16px;">
<br /></div>
<h3>
<span style="font-size: large;">Policy gradient</span></h3>
</div>
<div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;">Since the end goal is to pick the right action, and finding out the Q value is just the means (so we can pick the action of maximum Q), why don't we learn a function that takes a state and directly output an action. Using this policy function approach, we can handle both continuous or discrete action space as well.</span></span></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;"><br /></span></span></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;">The key idea is to learn a function (given a state, output an action)</span></span></div>
<br />
<ul>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">If the action is discrete, it outputs a probability distribution of each action</span></li>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">It the action is continuous, it output the mean and variance of the action, assume normal distribution</span></li>
</ul>
The agent will sample from the output distribution to determine the action, so its chosen action is stochastic (nondeterministic). Then the environment will determine the reward and next state. Cycle repeats ...<br />
<br />
The goal is to find the best policy function where the expected value of Q(s, a) is maximize. Notice that s and a are random variable parameterized by <span style="font-family: "cambria math";">θ.</span><br />
<span style="font-family: "cambria math";"><br /></span>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgfEGvNtQ4upKfnlM8bs1GKxSM6k5Brq2KMqGNU4LkveoDTFjzY8Nqjemlv4dxnS2Ul8dJVoek5mpxy5gQ86vKWn9dykxcbnkDb0xdwQnF5Swr5CPx0LSEQRo1WA2kMVLgDASWYrwPDKunO/s1600/Picture1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="734" data-original-width="1564" height="187" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgfEGvNtQ4upKfnlM8bs1GKxSM6k5Brq2KMqGNU4LkveoDTFjzY8Nqjemlv4dxnS2Ul8dJVoek5mpxy5gQ86vKWn9dykxcbnkDb0xdwQnF5Swr5CPx0LSEQRo1WA2kMVLgDASWYrwPDKunO/s400/Picture1.png" width="400" /></a></div>
<span style="font-family: "cambria math";"><br /></span></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;"><br /></span></span></div>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
To maximize an "expected value" of a function with parameters <span style="font-family: "cambria math"; font-size: small;">θ</span>, we need to calculate the gradient of that function.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhG8MaDiDTifZRC9X41Kf162ICgB1ejGdxx1pI-NFpQsg15ryIM5iWWJG74LB263hlNIxp9PSJGGRQuBfmmmOVY9KlqxAl77jalEPkw_YkSbkIpqILOomGA5NuhKDCuW96NV2YRlLFlYyGy/s1600/Picture1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="802" data-original-width="1600" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhG8MaDiDTifZRC9X41Kf162ICgB1ejGdxx1pI-NFpQsg15ryIM5iWWJG74LB263hlNIxp9PSJGGRQuBfmmmOVY9KlqxAl77jalEPkw_YkSbkIpqILOomGA5NuhKDCuW96NV2YRlLFlYyGy/s400/Picture1.png" width="400" /></a></div>
<br /></div>
</div>
<div style="background-color: white; margin-bottom: 0px; margin-top: 0px;">
<h3 style="font-family: calibri, helvetica, sans-serif, serif, emojifont;">
<span style="font-size: large;">Actor Critic Algorithm</span></h3>
<div style="font-family: calibri, helvetica, sans-serif, serif, emojifont; font-size: 16px;">
<span style="font-size: small;"><span style="font-size: 12pt;">There are 2 moving targets in this equation:</span></span></div>
<br />
<ul>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">To improve the policy function, we need an accurate estimation of Q value and also need to know the gradient of log(s, a)</span></li>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">To make the Q value estimation more accurate, we need a stable policy function</span></li>
</ul>
<div>
<span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">We can break down these into two different roles</span></div>
<div>
<ul>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">An actor, whose job is to improve the policy function by tuning the policy function parameters</span></li>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">A critic, whose job is to fine tune the estimation of Q value based on current (incrementally improving) policy</span></li>
</ul>
<div>
<span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">The "actor critic" algorithm is shown below.</span></div>
</div>
<div>
<span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";"><br /></span></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhpXwHB2DgSvKx__hISXPp9suChzRvnNujneiNV7Lmu263ml5GXkJMM8vsFmGlWYkdPwXOBDKyrM-ZwapDBBdtsuikMg7sPX93jU2e9aCLki4EanZQ-huGAMAUwyHPZi1BsM3sWJnAsQiHr/s1600/Screen+Shot+2017-08-25+at+10.15.22+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="465" data-original-width="626" height="296" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhpXwHB2DgSvKx__hISXPp9suChzRvnNujneiNV7Lmu263ml5GXkJMM8vsFmGlWYkdPwXOBDKyrM-ZwapDBBdtsuikMg7sPX93jU2e9aCLki4EanZQ-huGAMAUwyHPZi1BsM3sWJnAsQiHr/s400/Screen+Shot+2017-08-25+at+10.15.22+PM.png" width="400" /></a></div>
<div>
<span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";"><br /></span></div>
<div>
<span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">Then we enhance this algorithm by adding the following steps</span></div>
<div>
<ul>
<li><span style="font-family: "calibri" , "helvetica" , sans-serif , serif , "emojifont";">Replace the Q value function with an <b>Advantage</b> function, </span>where A(s, a) = Q(s, a) - Expected Q(s, *). ie: A(s, a) = Q(s, a) - V(s)</li>
<li>Run multiple thread Asynchronously</li>
</ul>
</div>
</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
This is the state of the art A3C algorithm.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhWUiP6C-vVGt4W-1TKMxC2YwMk29mRgQoExNlb-XHojkJamSg14DtbdtmHxA5FabBHFZ0FqS8e1GPQm1LM9mFIwKnry7q7Z7Mxdr5bq16li6ohvUedbIO0Q4-oGP6bVt_8B0DkC0igcGNa/s1600/Screen+Shot+2017-08-25+at+10.56.36+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="552" data-original-width="812" height="270" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhWUiP6C-vVGt4W-1TKMxC2YwMk29mRgQoExNlb-XHojkJamSg14DtbdtmHxA5FabBHFZ0FqS8e1GPQm1LM9mFIwKnry7q7Z7Mxdr5bq16li6ohvUedbIO0Q4-oGP6bVt_8B0DkC0igcGNa/s400/Screen+Shot+2017-08-25+at+10.56.36+PM.png" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br /></div>
<h3 style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; margin-bottom: 0px; margin-top: 0px;">
<span style="font-size: large;">Learning resources and credits</span></h3>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<br />
Some of the algorithms I discussed above is extracted from the following sources</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<ul>
<li><a href="http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html" target="_blank">David Silver's excellent RL lecture</a></li>
<li><a href="https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=5&cad=rja&uact=8&ved=0ahUKEwjtvbfJl_TVAhUM1GMKHX8nDNcQtwIIPzAE&url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DaUrX-rP_ss4&usg=AFQjCNGU0p3ypyw08blK6cUmAE5xRk60pQ" target="_blank">John Schulman's RL tutorial</a></li>
<li><a href="https://arxiv.org/pdf/1602.01783.pdf" target="_blank">A3C algorithm paper</a></li>
</ul>
</div>
<div style="background-color: white; font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px; margin-bottom: 0px; margin-top: 0px;">
<br /></div>
<div>
<span style="font-size: small;"><span style="font-size: 12pt;"><br /></span></span></div>
Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-13627940037468637842017-07-15T11:45:00.000-07:002017-07-15T11:48:22.141-07:00Regression model outputting probability density distribution<span style="font-family: "times" , "times new roman" , serif;">For a classification problem (let say output is one of the labels R, G, B), how do we predict ?</span><br />
<span style="font-family: "times" , "times new roman" , serif;"><br /></span>
<span style="font-family: "times" , "times new roman" , serif;">There are two formats that we can report our prediction</span><br />
<ol>
<li><span style="font-family: "times" , "times new roman" , serif;">Output a single value which is most probable outcome. e.g. output </span>"B" if P(B) > P(R) and P(B) > P(G)</li>
<li><span style="font-family: "times" , "times new roman" , serif;">Output the probability estimation of each label. (e.g. R=0.2, G=0.3, B=0.4)</span></li>
</ol>
<div>
<span style="font-family: "times" , "times new roman" , serif;">But if we look at regression problem (lets say we output a numeric value v), most regression model only output a single value (that minimize the RMSE). In this article, we will look at some use cases where outputting a probability density function is much preferred.</span></div>
<div>
<br /></div>
<h3>
Predict the event occurrence time</h3>
As an illustrative example, we want to predict when would a student finish her work given she has already spent some time s. In other words, we want to estimate E[t | t > s] where t is a random variable representing the total duration and s is the elapse time so far.<br />
<br />
Estimating time t is generally hard if the model only output an expectation. Notice that the model has the same set of features, expect that the elapse time has changed in a continuous manner as time passes.<br />
<br />
<span style="font-family: "times" , "times new roman" , serif;">Lets look at how we can train a prediction model that can output a density distribution.</span><br />
<br />
<span style="font-family: "times" , "times new roman" , serif;">Lets say our raw data schema: </span><span style="font-family: "times" , "times new roman" , serif; font-size: 16px;">[feature, duration]</span><br />
<div style="font-size: 16px;">
</div>
<ul>
<li><span style="font-family: "times" , "times new roman" , serif;">f1, 13.30</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f2, 14.15</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f3, 15.35</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f4, 15.42</span></li>
</ul>
<div style="font-size: 16px;">
<span style="font-family: "times" , "times new roman" , serif;">Take a look at the range (ie. min and max) of the output value. We transform into the training data of the following schema:</span></div>
<div style="font-size: 16px;">
<span style="font-family: "times" , "times new roman" , serif;">[feature, dur<13, dur<14, dur<15, dur<16]</span></div>
<div style="font-size: 16px;">
</div>
<div style="font-size: 16px;">
</div>
<ul>
<li><span style="font-family: "times" , "times new roman" , serif;">f1, 0, 1, 1, 1</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f2, 0, 0, 1, 1</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f3, 0, 0, 0, 1</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f4, 0, 0, 0, 1</span></li>
</ul>
After that, we train 4 classification model.<br />
<div style="font-size: 16px;">
</div>
<ul>
<li><span style="font-family: "times" , "times new roman" , serif;">feature, dur<13</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">feature, dur<14</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">feature, dur<15</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">feature, dur<16</span></li>
</ul>
<br />
<span style="font-family: "times" , "times new roman" , serif;"></span><br />
<div style="-webkit-text-stroke-width: 0px; color: black; font-family: Times; font-size: medium; font-style: normal; font-variant-caps: normal; font-variant-ligatures: normal; font-weight: normal; letter-spacing: normal; margin: 0px; orphans: 2; text-align: start; text-decoration-color: initial; text-decoration-style: initial; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">
<span style="background-color: white; font-size: 16px;"><span style="font-family: "times" , "times new roman" , serif;">Now, given a new observation with corresponding feature, we can invoke these 4 model to output the probability of binary classification (cumulative probability). If we want the probability density, simply take the difference (ie: differentiation of cumulative probability).</span></span></div>
<div style="-webkit-text-stroke-width: 0px; color: black; font-family: Times; font-size: medium; font-style: normal; font-variant-caps: normal; font-variant-ligatures: normal; font-weight: normal; letter-spacing: normal; margin: 0px; orphans: 2; text-align: start; text-decoration-color: initial; text-decoration-style: initial; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">
<span style="background-color: white; font-size: 16px;"><span style="font-family: "times" , "times new roman" , serif;"><br /></span></span></div>
<div style="-webkit-text-stroke-width: 0px; color: black; font-style: normal; font-variant-caps: normal; font-variant-ligatures: normal; font-weight: normal; letter-spacing: normal; margin: 0px; orphans: 2; text-align: start; text-decoration-color: initial; text-decoration-style: initial; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">
<span style="font-family: "times" , "times new roman" , serif;"><span style="background-color: white;">At this moment, we can output a probability distribution given its input feature.</span></span></div>
<div style="-webkit-text-stroke-width: 0px; color: black; font-style: normal; font-variant-caps: normal; font-variant-ligatures: normal; font-weight: normal; letter-spacing: normal; margin: 0px; orphans: 2; text-align: start; text-decoration-color: initial; text-decoration-style: initial; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">
<span style="font-family: "times" , "times new roman" , serif;"><span style="background-color: white;"><br /></span></span></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjz8y4XeaxcaAvpHR1c0P84h7MrZ5IsI_C4flOiq5Q0qh3dZthfm5fPkVvirdUEiZBr-yqsLzyqA45Kq8jHXBcIoB4wNu0N1HmDjokFz4MsazWAMUswWYpZtVQTBot7X7hx2cLVfvvmUYWv/s1600/Picture1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="490" data-original-width="986" height="198" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjz8y4XeaxcaAvpHR1c0P84h7MrZ5IsI_C4flOiq5Q0qh3dZthfm5fPkVvirdUEiZBr-yqsLzyqA45Kq8jHXBcIoB4wNu0N1HmDjokFz4MsazWAMUswWYpZtVQTBot7X7hx2cLVfvvmUYWv/s400/Picture1.png" width="400" /></a></div>
<br />
Now, we can easily estimate the remaining time from the expected time in the shade region. As time passed, we just need to slide the red line continuously and recalculate the expected time, we don't need to execute the prediction model unless the input features has changed.<br />
<br />
<h3>
<span style="font-family: "times" , "times new roman" , serif;">Predict cancellation before commitment </span><span style="font-family: "times" , "times new roman" , serif;"><br /></span></h3>
<span style="font-family: "times" , "times new roman" , serif;">As an illustrative example, lets say a customer of restaurant has reserved a table at 8:00pm. Time now is 7:55pm and the customer still hasn't arrive, what is the chance of no-show ?</span><br />
<span style="font-family: "times" , "times new roman" , serif;"><br /></span>
<span style="font-family: "times" , "times new roman" , serif;">Now, given a person (with feature x), and current time is S - t (still hasn't bought the ticket yet), predict the probability of this person watching the movie.</span><br />
<span style="font-family: "times" , "times new roman" , serif;"><br /></span>
<span style="font-family: "times" , "times new roman" , serif;">Lets say our raw data schema: </span><span style="font-family: "times" , "times new roman" , serif; font-size: 16px;">[feature, arrival]</span><br />
<div style="font-size: 16px;">
</div>
<ul>
<li><span style="font-family: "times" , "times new roman" , serif;">f1, -15.42</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f2, -15.35</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f3, -14.15</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f4, -13.30</span></li>
<div style="font-size: 16px;">
</div>
<li><span style="color: red;">f5, infinity</span></li>
<li><span style="color: red; font-family: "times" , "times new roman" , serif;">f6, infinity</span></li>
</ul>
<div style="font-size: 16px;">
<span style="font-family: "times" , "times new roman" , serif;">We transform into the training data of the following schema:</span><br />
<div style="font-size: 16px;">
<span style="font-family: "times" , "times new roman" , serif;">[feature, arr<-16, arr<-15, arr<-14, arr<-13]</span></div>
<ul style="-webkit-text-stroke-width: 0px; color: black; font-family: Times; font-size: medium; font-style: normal; font-variant-caps: normal; font-variant-ligatures: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-decoration-color: initial; text-decoration-style: initial; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">
<li><span style="font-family: "times" , "times new roman" , serif;">f1, 0, 1, 1, 1</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f2, 0, 1, 1, 1</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f3, 0, 0, 1, 1</span></li>
<li><span style="font-family: "times" , "times new roman" , serif;">f4, 0, 0, 0, 1</span></li>
<li><span style="color: red;">f5, 0, 0, 0, 0</span></li>
<li><span style="color: red; font-family: "times" , "times new roman" , serif;">f6, 0, 0, 0, 0</span></li>
<div style="font-size: 16px;">
</div>
</ul>
</div>
<div style="font-size: 16px;">
<span style="font-family: "times" , "times new roman" , serif;">After that, we train 4 classification models.</span></div>
<ul style="-webkit-text-stroke-width: 0px; color: black; font-family: Times; font-size: medium; font-style: normal; font-variant-caps: normal; font-variant-ligatures: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-decoration-color: initial; text-decoration-style: initial; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">
<li><span style="font-family: "times" , "times new roman" , serif;">feature, </span>arr<-16</li>
<li><span style="font-family: "times" , "times new roman" , serif;">feature, </span>arr<-15</li>
<li><span style="font-family: "times" , "times new roman" , serif;">feature, </span>arr<-14</li>
<li><span style="font-family: "times" , "times new roman" , serif;">feature, </span>arr<-13</li>
</ul>
<span style="font-family: "times" , "times new roman" , serif;">Notice that P(arr<0) can be smaller than 1 because the customer can be no show.</span><br />
<span style="font-family: "times" , "times new roman" , serif;"><br /></span>
<span style="font-family: "times" , "times new roman" , serif;"><br /></span>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgUwi6OkEogPgEryhl_MVlFdD_Uh78ULP1y5I8o4n1eGe5WbqOP1i3SkxBtNczABeZOkEfeHnFrE1bkhO8ZkCcCnQ6QuCpcolxbBKAl-JZfgooj1y1OuQWHXhHTDNOBxbyAP2xjfklPCuk_/s1600/Picture1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1015" data-original-width="1216" height="332" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgUwi6OkEogPgEryhl_MVlFdD_Uh78ULP1y5I8o4n1eGe5WbqOP1i3SkxBtNczABeZOkEfeHnFrE1bkhO8ZkCcCnQ6QuCpcolxbBKAl-JZfgooj1y1OuQWHXhHTDNOBxbyAP2xjfklPCuk_/s400/Picture1.png" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<span style="font-family: "times" , "times new roman" , serif;"><br /></span>
<span style="font-family: "times" , "times new roman" , serif;">In this post, we discuss some use cases where we need the regression model to output not just its value prediction but also the probability density distribution. And we also illustrate how we can build such prediction model.</span><br />
<h3>
</h3>
Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-3391812564655124022017-07-02T00:43:00.002-07:002017-07-02T00:44:28.448-07:00How AI differs from MLAI is not a new term, it is multiple decades old starting around early 80s when computer scientist design algorithms that can "learn" and "mimic human behavior".<br />
<br />
On the "learning" side, the most significant algorithm is Neural Network, which is not very successful due to overfitting (the model is too powerful but not enough data). Nevertheless, in some more specific tasks, the idea of "using data to fit a function" has gained significant success and this form the foundation of "machine learning" today.<br />
<br />
On the "mimic" side, people have focus in "image recognition", "speech recognition", "natural language processing", experts have been spending tremendous amount of time to create features like "edge detection", "color profile", "N-grams", "Syntax tree" ... etc. Nevertheless, the success is moderate.<br />
<br />
<h3>
Traditional Machine Learning</h3>
Machine Learning (ML) Technique has played a significant role in prediction and ML has undergone multiple generations, with a rick set of model structure, such as<br />
<br />
<ul>
<li>Linear regression</li>
<li>Logistic regression</li>
<li>Decision tree</li>
<li>Support Vector Machine</li>
<li>Bayesian model</li>
<li>Regularization model</li>
<li>Ensemble model</li>
<li>Neural network</li>
</ul>
<br />
Each of these predictive model is based on certain algorithmic structure, with parameters as tunable knobs. Training a predictive model involves the following<br />
<br />
<ol>
<li>Choose a model structure (e.g. Logistic regression, or Random forest, or ...)</li>
<li>Feed the model with training data (with both input and output)</li>
<li>The learning algorithm will output the optimal model (ie: model with specific parameters that minimize the training error)</li>
</ol>
<br />
Each model has its own characteristics and will perform good in some tasks and bad in others. But generally, we can group them into the low-power (simple) model and the high-power (complex) model. Choose between different models is a very tricky question.<br />
<br />
Traditionally, using a low power / simple model is preferred over the use of a high power / complex model for the following reasons<br />
<br />
<ul>
<li>Until we have massive processing power, training the high power model will take too long</li>
<li>Until we have massive amount of data, training the high power model will cause the overfit problem (since the high power model has rich parameters and can fit into a wide range of data shape, we may end up train a model that fits too specific to the current training data and not generalized enough to do good prediction on future data).</li>
</ul>
<br />
However, choosing a low power model suffers from the so called "under-fit" problem where the model structure is too simple and unable to fit the training data in case it is more complex. (Imagine the underlying data has a quadratic relationship: y = 5 * x^2, there is no way you can fit a linear regression: y = a*x + b no matter what a and b we pick).<br />
<br />
To mitigate the "under-fit problem", data scientist will typically apply their "domain knowledge" to come up with "input features", which has a more direct relationship with the output. (e.g. Going back to the quadratic relationship: y = 5 * square(x), if you create a feature z = x^2, then you can fit a linear regression: y = a*z + b, by picking a = 5 and b = 0)<br />
<br />
The major obstacle of "Machine Learning" is this "Feature Engineering" step which requires deep "domain experts" to identify important signals before feeding into training process. The feature engineering step is very manual and demands a lot of scarce domain expertise and therefore become the major bottleneck of most machine learning tasks today.<br />
<br />
In other words, if we don't have enough processing power and enough data, then we have to use the low-power / simpler model, which requires us to spend significant time and effort to create appropriate input features. This is where most data scientists spending their time doing today.<br />
<br />
<h3>
Return of Neural Network</h3>
At early 2000, machine processing power has increased tremendously, with the advancement of cloud computing, massively parallel processing infrastructure, together with big data era where massive amount of fine grain event data being collected. We are no longer restricted to the low-power / simple model. For example, two most popular, mainstream machine learning model today are RandomForest and Gradient Boosting Tree. Nevertheless, although both of them are very powerful and provide non-linear model fitting to the training data, data scientist still need to carefully create features in order to achieve good performance.<br />
<br />
At the same time, computer scientists has revisited the use of many layers Neural Network in doing these human mimic tasks. This give a new birth to DNN (Deep Neural Network) and provide a significant breakthrough in image classification and speech recognition tasks. The major difference of DNN is that you can feed the raw signals (e.g. the RGB pixel value) directly into DNN without creating any domain specific input features. Through many layers of neurons (hence it is called "deep" neural network), DNN can "automatically" generate the appropriate features through each layer and finally provide a very good prediction. This saves significantly the "feature engineering" effort, a major bottleneck done by the data scientists.<br />
<br />
DNN also evolves into many different network topology structure, so we have CNN (Convolutional Neural Network), RNN (Recurrent Neural Network), LSTM (Long Short Term Memory), GAN (Generative Adversarial Network), Transfer Learning, Attention Model ... etc. The whole spectrum is called Deep Learning, which is catching the whole machine learning community’s attention today.<br />
<br />
<h3>
Reinforcement Learning</h3>
Another key component is about how to mimic a person (or animal) learn. Imagine the very natural animal behavior of perceive/act/reward cycle. A person or animal will first understand the environment by sensing what "state" he is in. Based on that, he will pick an "action" which brings him to another "state". Then he will receive a "reward". The cycle repeats until he dies. This way of learning (called "Reinforcement Learning") is quite different from the "curve fitting" approaches of traditional supervised machine learning approach. In particular, learning in RL is very fast because every new feedback (such as perform an action and receive a reward) is sent immediately to influence subsequent decisions. Reinforcement Learning has gain tremendous success in self-driving cars as well as AlphaGO (Chess Playing Robot).<br />
<br />
Reinforcement Learning also provides a smooth integration between "Prediction" and "Optimization" because it maintains a belief of current state and possible transition probabilities when taking different actions, and then make decisions which action can lead to the best outcome.<br />
<br />
<h3>
AI = DL + RL</h3>
<div>
Compare to the classical ML Technique, DL provide a more powerful prediction model that usually produce good prediction accuracy. Compare to the classical Optimization model using LP, RL provide a much faster learning mechanism and also more adaptive to change of the environment.<br />
<br /></div>
Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-73229494558648831442017-04-29T23:58:00.000-07:002017-04-30T00:02:25.446-07:00An output of a truly random process<span style="font-family: Times, Times New Roman, serif;">Recently I have a discussion with my data science team whether we can challenge the observations is following a random process or not. Basically, data science is all about learning hidden pattern that is affecting the observations. If the observation is following a random process, then there is nothing we can learn about. Let me walk through an example to illustrate.</span><br />
<span style="font-family: Times, Times New Roman, serif;"><span style="font-family: "times" , "times new roman" , serif;"><br /></span>
<span style="font-family: "times" , "times new roman" , serif;">Lets say someone is making a claim that he is throwing a fair dice (with number 1 to 6) sequentially.</span></span><br />
<span style="background-color: white; font-size: 16px;"><span style="font-family: Times, Times New Roman, serif;">Lets say I claim the output of my dice throw is uniformly random, ie: with equal chances of getting a number from 1 to 6.</span></span><br />
<div style="background-color: white; font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="background-color: white; font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">And then he throws the dice 12 times, and show you the output sequence. From the output, can you make a judgement whether this is really a sequential flow of a fair dice ? In other words, is the output really follow a random process as expected ?</span></div>
<div style="background-color: white; font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="background-color: white; font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">Lets look at 3 situations</span></div>
<div style="background-color: white;">
<ul style="font-size: 16px;">
<li><span style="font-family: Times, Times New Roman, serif;">Situation 1 output is [4, 1, 3, 1, 2, 6, 3, 5, 5, 1, 2, 4]</span></li>
<li><span style="font-family: Times, Times New Roman, serif;">Situation 2 output is [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]</span></li>
<li><span style="font-family: Times, Times New Roman, serif;">Situation 3 output is [1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6]</span></li>
</ul>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">At first glance, the output of situation 1 looks like resulting from a random process. Situation 2 definitely doesn't look like it. Situation 3 is harder to judge. If you look at the proportion of the output numbers, the frequency of each output number of situation 3 definitely follows a uniform distribution of a fair dice. But if you look at the number ordering, situation 3 follows a well-defined ordering that doesn't seem to be random at all. Therefore, I don't think the output of situation 3 is following a random process.</span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">However, this seems to be a very arbitrary choice. Why would I look at the number ordering at all ? Should I look for more properties ? such as ...</span></div>
<div style="font-size: 16px;">
<ul>
<li><span style="font-family: Times, Times New Roman, serif;">Whether the number of the even position are even</span></li>
<li><span style="font-family: Times, Times New Roman, serif;">Average gap between consecutive throws</span></li>
<li><span style="font-family: Times, Times New Roman, serif;">Whether the number in the 3rd position always smaller than the 10th position</span></li>
<li><span style="font-family: Times, Times New Roman, serif;">...</span></li>
</ul>
<div>
<span style="font-family: Times, Times New Roman, serif;">As you can see, depends on my imagination, the list can go on and on. How can I tell whether situation 3 is following a random process or not ?</span></div>
</div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<h3 style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">
Method 1: Randomization Test</span></h3>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">This is based on the hypothesis testing methodology. We establish null hypothesis H0 that situation 3 follows a random process.</span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">First, I define an arbitrary list of statistics of my choices</span></div>
<div>
<ul>
<li><span style="font-family: Times, Times New Roman, serif;">statisticA = proportion of even numbers in even position</span></li>
<li><span style="font-family: Times, Times New Roman, serif;">statisticB = average gap between consecutive output numbers</span></li>
<li><span style="font-family: Times, Times New Roman, serif;">statisticC = ...</span></li>
</ul>
</div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">Second, I run a simulation to generate 12 numbers based on a random process. Calculate the corresponding statistics defined above.</span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">Third repeat the simulation for N times, output the mean and standard deviation of the statistics.</span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">If the statisticA or B or C of situation 3 are too far away (based on the likelihood pValue) from the mean of statistics A/B/C by the number of standard deviation of statistics A/B/C, then we conclude that situation 3 is not following a random process. Otherwise, we don't have enough evidence to show our null hypothesis is violated and so we accept situation 3 follows the random process.</span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<h3 style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">
Method 2: Predictability Test</span></h3>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">This is based on the theory of predictive analytics.</span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">First, I pick a particular machine learning algorithm, lets say time series forecast using ARIMA.</span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">Notice that I can also choose to use RandomForest and create some arbitrary input features (such as previous output number, maximum number in last 3 numbers ... etc)</span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">Second, I train my selected predictive model based on the output data of situation 3 (in this example, situation 3 has only 12 data point, but imagine we have much more than 12 data point).</span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="font-size: 16px;">
<span style="font-family: Times, Times New Roman, serif;">Third, I evaluate my model in the test set. And see whether the prediction is much better than a random guess. For example I can measure the lift of my model by comparing the RMSE (root mean square error) or my prediction and the standard deviation of the testing data. If the lift is very insignificant, then I conclude that situation 3 results from a random process, because my predictive model doesn't learn any pattern.</span></div>
</div>
<div style="background-color: white; font-size: 16px;">
<div>
<span style="font-family: Times, Times New Roman, serif;"><br /></span></div>
</div>
<span style="font-family: "times" , "times new roman" , serif;"><br /></span>
Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-41851482872369293572015-08-25T23:11:00.002-07:002015-08-25T23:12:02.197-07:00Common techniques in optimizationOptimization is a frequently encountered problem in real life. We need to make a decision to achieve something within a set of constraints, and we need to maximize or minimize our objective based on some measurement. For example, a restaurant may need to decide how many workers (of each position) to hire to serve the customers, with the constraint that workers cannot work overtime, and the objective is to minimize the cost. A car manufacturer may need to decide how many units of each model to be produced, within the constraint of the storage capacity of its warehouse, and maximize the profit of its sales.<br />
<br />
<h3>
Exhaustive Search</h3>
If there isn't a lot of choices, an exhaustive search (e.g. breath-first, depth-first, best-first, A* ... etc.) can be employed to evaluate each option, see if it meets all the constraints (ie: a feasible solution), and then compute its objective value. Then we sort all feasible solutions based on its corresponding objective value and pick the solution that has the max (or min) objective value as our decision. Unfortunately, real world problem usually involve a large number (exponentially large due to combinatorial explosion) of choices, making the exhaustive search in many cases impractical.<br />
<br />
When this happens, two other solution approaches are commonly used.<br />
1) Mathematical Programming<br />
2) Local Greedy Search.<br />
<br />
<h3>
Mathematical Programming </h3>
Mathematical programming is a classical way to solve optimization problem. It is a family of approaches including linear programming, integer programming, quadratic programming and even non-linear programming. The development process usually go through the following steps ...<br />
<br />
From a problem description, the modeler will express the problem into a mathematical structure containing 3 parts.<br />
<ul>
<li><b>Variables</b>: there are two types of variables. <i><b>Data variables</b></i> contains the current value of your business environment (e.g. cost of hiring a waiter, price of a car), and <i><b>Decision variables</b></i> hold the decision you make to optimize your objective (e.g. how many staff to hire, how many cars to make).</li>
<li><b>Constraints</b>: it is a set of rules that you cannot break. Effectively, constraints disallow certain combinations of your decision variables and is mainly used to filter out in-feasible solutions. In a typical settings, constraints are expressed as a system of linear inequality equations where a linear expression of decision variables are specified on the left hand side and a value is specified on the right hand side after an inequality comparison.</li>
<li><b>Objective function</b>: it encapsulates the quantitative measure of how our goal has been achieved. In a typical setting, objective function is expressed as a single linear (or quadratic) combination of decision variables</li>
</ul>
After the mathematical structure is defined, the modeler will submit it to a solver, which will output the best solution. The process can be depicted as follows.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgXie97e812Hnuxo_wiezdLlgzSQNL8z8NtEzfOdP2i1_MMFOhF8dRW2VqitNzKg-biVnd_Xb6n69gExjdotYEt5uJBrykvq4-ROP6GTBHE95NLOZrlp_LjoqkE2iaTplKRhltGG0TJzHS/s1600/P1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="286" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgXie97e812Hnuxo_wiezdLlgzSQNL8z8NtEzfOdP2i1_MMFOhF8dRW2VqitNzKg-biVnd_Xb6n69gExjdotYEt5uJBrykvq4-ROP6GTBHE95NLOZrlp_LjoqkE2iaTplKRhltGG0TJzHS/s400/P1.png" width="400" /></a></div>
<br />
Expressing the problem in the mathematical structure is the key design of the solution. There are many elements to be considered, which we described below.<br />
<br />
The first consideration is how to represent your decision, specially whether the decision is a quantity (real number), a number of units (integer) or a binary decision (integer 0, 1).<br />
<br />
The next step is to represent the constraints in terms of inequality equations of linear combination of decision variables. You need to think whether the constraints is a hard of soft constraints. Hard constraints should be expressed in the constraint part of the problem. Notice the solver will not consider any solution once it violates any constraints. Therefore, if the solver cannot find a feasible solution that fulfill all constraints, it will simply abort. In other words, it won't return you a solution that violates the smallest number of constraints. If you want the solve to tell you that because you have rooms to relax them, you should model these soft constraints in the objective function rather than in the constraint section. Typically, you define an objective function that quantifies the degree of violation. The solver will then give you the optimal solution (violating least number of constraints) rather than just telling you no solution is found.<br />
<br />
Finally you define the objective function. In most real-life problems, you have multiple goals in mind (e.g. you want to minimize your customer's wait time in the queue, but you also want to minimize your cost of hiring staffs). First you express each goal as a linear expression of decision variables and then take the weighted average among different goals (which is also a linear combination of all decision variables) to form the final objective function. How to choose the weights among different goals is a business question, based on how much you are willing to trade off between conflicting goals.<br />
<br />
There are some objectives that cannot be expressed by a linear expression of decision variables. One frequently encountered example is about minimizing the absolute deviation from a target value (ie. no matter the deviation is a positive and negative value). A common way is to minimize the sum of square of the difference. But after we square it, it is no longer a linear expression. To address this requirement, there is a more powerful class of solver call "quadratic programming" which relax the objective function to allow a degree 2 polynomial expression.<br />
<br />
After you expressed the problem in the mathematical structure. You can pass
it to a solver (there are many open source and commercial solver
available) which you can treat it as a magical black box. The solver
will output an optimal solution (with a value assigned to each decision
variable) that fulfill all constraints and maximize (or minimize) the
objective function.<br />
<br />
Once you received the solution from the solver, you need to evaluate how "reliable" is this optimal solution. There may be fluctuations in the data variables due to collection error, or the data may have a volatile value that changes rapidly, or the data is an estimation of another unknown quantity.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsbfawtObejLU5Z0IACY8SbRaHd1NNfLmCs0dfnRUhsWIucCfYp3dQTqgYSBRYeYmMe-xgjq4JRitaQe_Frk2AG52iHqJ06UTN9odweNw_At1MBM367OZ0_j2tFXc8UgDuCBMQsF4LCOzE/s1600/P1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="312" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsbfawtObejLU5Z0IACY8SbRaHd1NNfLmCs0dfnRUhsWIucCfYp3dQTqgYSBRYeYmMe-xgjq4JRitaQe_Frk2AG52iHqJ06UTN9odweNw_At1MBM367OZ0_j2tFXc8UgDuCBMQsF4LCOzE/s400/P1.png" width="400" /></a></div>
<br />
<br />
Ideally, the optimal solution doesn't change much when we fluctuate the data values within its error bound. In this case, our optimal solution is stable against error in our data variables and therefore is a good one. However, if the optimal solution changes drastically when the data variable fluctuates, we say the optimal solution is unreliable and cannot use it. In the case, we usually modify each data variables one at a time to figure out which data variable is causing a big swing of optimal solution and try to reduce our estimation error of that data variable.<br />
<br />
The <i><b>sensitivity analysis</b></i> is an important step to evaluate the stability and hence the quality of our optimal solution. It also provides guidance on which area we need to invest effort to make the estimation more accurate.<br />
<br />
Mathematical Programming allows you to specify your optimization problem in a very declarative manner and also output an optimal solution if it exist. It should be the first-to-go solution. The downside of Mathematical programming is that it requires linear constraints and linear (or quadratic) objectives. And it also has limits in terms of number of decision variables and constraints that it can store (and this limitation varies among different implementations). Although there are non-linear solvers, the number of variables it can take is even smaller.<br />
<br />
Usually the first thing to do is to test out if your problem is small enough to fit in the mathematically programming solver. If not, you may need to use another approach.<br />
<br />
<h3>
Greedy Local Search</h3>
The key words here are "local" and "greedy". Greedy local search starts at a particular selection of decision variables, and then it look around surrounding neighborhood (hence the term "local") and within that find the best solution (hence the term "greedy"). Then it moves the current point to this best neighbor and then the process repeats until the new solution stays at the same place (ie. there is no better neighbor found).<br />
<br />
If the initial point is selected to be a non-feasible solution, the greedy search will first try to find a feasible solution first by looking for neighbors that has less number of constraint violation. After the feasible solution is found, the greedy search will only look for neighbors that fulfill all constraints and within which to find a neighbor with the best objective value. Another good initialization strategy is to choose the initial point to be a feasible (of course not optimal) solution and then start the local search from there.<br />
<br />
Because local search limits its search within a neighborhood, it can control the degree of complexity by simply limits the scope of neighbor. Greedy local search can evaluate a large number of variables by walking across a chain of neighborhoods. However, because local search only navigate towards the best neighbor within a limited scope, it loses the overall picture and rely on the path to be a convex shape. If there are valleys along the path, the local search will stop there and never reach the global optimum. This is called a local optimal trap because the search is trapped within a local maximum and not able to escape. There are <a href="http://horicky.blogspot.com/2013/12/escape-local-optimum-trap.html" target="_blank">some techniques to escape from local optimum</a> that I describe in my <a href="http://horicky.blogspot.com/2013/12/escape-local-optimum-trap.html" target="_blank">previous blog post</a>.<br />
<br />
When performing greedy local search, it is important to pick the right greedy function (also called heuristic function) as well as the right neighborhood. Although it is common to choose the greedy function to be the same objective function itself, they don't have to be the same. In many good practices, the greedy function is chosen to be the one that has high correlation with the objective function, but can be computed much faster. On the other hand, evaluating objective function of every point in the neighborhood can also be a very expensive operation, especially when the data has a high dimension and the number of neighbors can be exponentially large. A good neighbor function can be combined with a good greedy function such that we don't need to evaluate each neighbor to figure out which one has the best objective value.<br />
<br />
<h3>
Combining the two approaches</h3>
In my experience, combining the two approaches can be a very powerful solution itself. At the outer layer, we are using the greedy local search to navigate the direction towards better solution. However, when we search for the best neighbor within the neighborhood, we use the mathematical programming by taking the greedy function as the objective function, and we use the constraints directly. This way, we can use a very effective approach to search for best solution within the neighborhood and can use the flexible neighborhood scoping of local search to control the complexity of the mathematical programming solver.<br />
<br />Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-87876607481970357492015-06-27T09:28:00.002-07:002015-06-27T09:53:43.084-07:00When machine replace human<div id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
<span id="yui_3_16_0_1_1435385723542_38876">Recently, a good friend sent me an article from Harvard Business Review called "Beyond Automation", written by Thomas H. Davenport and Julia Kirby. The article talked about how automation affects our job forces and displacing values from human workers. It proposed 5 strategies in how we can get prepared to retain competitiveness in the automation era. This is a very good article and triggers me a lot of thoughts.</span><br />
<br />
I want to explore a fundamental question: "Can machine replace a human in future ?"</div>
<div id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
<br /></div>
<div id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
Lets start looking at what machines are doing and not doing today. Machines are operating under a human's program, and therefore it can only solve those problems that we, human can express or codified in a structural form. Don't underestimate its power underneath. With good abstract thinking, smartest human in the world has partitioned large number of problems (by its problem nature) into different problem categories. Each category is expressed in form od a "generic problem" and subsequently a "general solution" is developed. Notice that computer scientist has been doing this for many decades, and come up with the powerful algorithm such as "Sorting", "Finding shortest path", "Heuristic search" ... etc.</div>
<div id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
<br /></div>
<div id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
By grouping concrete problems by their nature into a "generic, abstract problem", we can significantly reduce the volume of cases/scenarios while still covers a large area of ground. The "generic solution" we developed can also be specialized for each concrete problem scenario. After that we can develop a software program which can be executed in a large cluster of machines equipped with fast CPU and a lot of memory. Compare this automated solution with what a human can do in a manual fashion. In these areas, once problems are well-defined and solutions are automated by software program, computers with much powerful CPU and memory will always beat human in many many orders of magnitude. There is no question that the human job in these areas will be eliminated.</div>
<div id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
<br /></div>
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
In terms of capturing our experience using a abstract data structure and algorithm, computer scientist are very far from done. There are still a very large body of problems that even the smartest human haven't completely figured out how to put them in a structural form yet. Things that involve "perception", "intuition", "decision making", "estimation", "creativity" are primarily done today by human. I believe these type of jobs will continue to be done by human workers in our next decade. On the other hand, with our latest technology research, we continuously push our boundary of automation into some of these areas. "Face recognition", "Voice recognition" that involves high degree of perception can now be done very accurately by software program. With "machine learning" technology, we can do "prediction" and make judgement in a more objective way than a human. Together with "planning" and "optimization" algorithm, large percentage of decision making can be automated, and the result is usually better because of a less biased and data-driven manner.</div>
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
<br /></div>
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
However, in these forefront areas where latest software technology is unable to automate every steps, the human is need in the path to make a final decision, or interven in those exceptional situation that the software is not programmed to handled. There are jobs that a human and machine can working together to make better outcome. This is what is called "augmentation" in the article. Some job examples are artists are using advanced software to touchup their photos, using computer graphics to create movies, using machine learning to do genome sequence processing, using robots to perform surgery, driver-less vehicles ... etc.</div>
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
<br /></div>
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
Whether computer programming can replace human completely remains to be seen, but I don't think this will happen in the next 2 decades. We humans are unique and good at perceiving things with multiple level of abstractions from different angles. We are good at connecting the dots between unrelated areas. We can invent new things. These are things that machine will be very hard to do, or at least will take a long time if at all possible.</div>
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="-webkit-text-stroke-width: 0px; color: black; font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; margin-bottom: 0.1em; margin-top: 0.1em; orphans: auto; padding: 0px; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px;">
</div>
<br />
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="-webkit-text-stroke-width: 0px; color: black; font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; margin-bottom: 0.1em; margin-top: 0.1em; orphans: auto; padding: 0px; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px;">
<div style="margin: 0px;">
"When can we program a machine that can write program ?"</div>
</div>
<br /></div>
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
The HBR article suggests a person can consider five strategies (step up, step aside, step in, step narrowly and step forward) to retain value in the automation era. I favor the "step forward" strategy because the person is driving the trend rather than passively reacting to the trend. Date back to our history, human's value system has been shifted across industry revolution, internet revolution etc. At the end of the day, it is more-sophisticated human who take away jobs (and value) from other less-sophisticated human. And it is always the people who drives the movement to be the winner of this value shift. It happens in the past and will continue into future.</div>
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
<br /></div>
<div data-setdir="false" dir="ltr" id="yui_3_16_0_1_1435385723542_22548" style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 13px; margin-bottom: 0.1em; margin-top: 0.1em; padding: 0px;">
<br /></div>
Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-47580673662838189782015-02-22T23:42:00.001-08:002015-02-22T23:43:43.437-08:00Big Data Processing in SparkIn the traditional 3-tier architecture, data processing is performed by the application server where the data itself is stored in the database server. Application server and database server are typically two different machine. Therefore, the processing cycle proceeds as follows<br />
<ol>
<li>Application server send a query to the database server to retrieve the necessary data</li>
<li>Application server perform processing on the received data</li>
<li>Application server will save the changed data to the database server</li>
</ol>
In the traditional data processing paradigm, <i><b>we move data to the code</b></i>.<br />
It can be depicted as follows ...<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2ykcNxSifUH7n3Xcvcch499xgDPIkIL_kBlTqcvj-_TPHKDg1cVnD8008SUkRNACYiPL1Lznpx10exlISCpni26mEj4_gz6nWxd_MHFWkgPZOt5tHjiGIeI6ORPXre_fKcgVqxBmAA7Ap/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2ykcNxSifUH7n3Xcvcch499xgDPIkIL_kBlTqcvj-_TPHKDg1cVnD8008SUkRNACYiPL1Lznpx10exlISCpni26mEj4_gz6nWxd_MHFWkgPZOt5tHjiGIeI6ORPXre_fKcgVqxBmAA7Ap/s1600/p1.png" height="165" width="320" /></a></div>
<br />
<br />
Then big data phenomenon arrives. Because the data volume is huge, it cannot be hold by a single database server. Big data is typically partitioned and stored across many physical DB server machines. On the other hand, application servers need to be added to increase the processing power of big data.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKqIjyAmPrBOQmxx0hiV4O6UprzgAg4DDN-pyUPWP9dWUAR6ToeGI9CdSB19EE7ZqDwD5z_81rues1wlM93-ANJkO2BfdfUF_VXGyoP_Iv1Mwmi2HW2KoevaW13bEamGB8QSvYb-V9dHd9/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKqIjyAmPrBOQmxx0hiV4O6UprzgAg4DDN-pyUPWP9dWUAR6ToeGI9CdSB19EE7ZqDwD5z_81rues1wlM93-ANJkO2BfdfUF_VXGyoP_Iv1Mwmi2HW2KoevaW13bEamGB8QSvYb-V9dHd9/s1600/p1.png" height="235" width="400" /></a></div>
<br />
However, as we increase the number of App servers and DB servers for storing and processing the big data, more data need to be transfer back and forth across the network during the processing cycle, up to a point where the network becomes a major bottleneck.<br />
<br />
<h3>
Moving code to data</h3>
To overcome the network bottleneck, we need a new computing paradigm. Instead of moving data to the code, we move the code to the data and perform the processing at where the data is stored.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgKAuQkCO99qDxVchMkTabG72NUQ8XYmdNZkMz_Yj_rLOYLOCNhD4pRjZHTgzAbL5Y9wwKIPEbsEDa0W_SepWF2dNhwfvBSS4FPXt3eCb4B8dzF0V7Do101QHjt4rXjfemeIvbDzIOXegy/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgKAuQkCO99qDxVchMkTabG72NUQ8XYmdNZkMz_Yj_rLOYLOCNhD4pRjZHTgzAbL5Y9wwKIPEbsEDa0W_SepWF2dNhwfvBSS4FPXt3eCb4B8dzF0V7Do101QHjt4rXjfemeIvbDzIOXegy/s1600/p1.png" height="243" width="400" /></a></div>
<br />
<br />
Notice the change of the program structure<br />
<ul>
<li>The program execution starts at a driver, which orchestrate the execution happening remotely across many worker servers within a cluster.</li>
<li>Data is no longer transferred to the driver program, the driver program holds a data reference in its variable rather than the data itself. The data reference is basically an id to locate the corresponding data residing in the database server</li>
<li>Code is shipped from the program to the database server, where the execution is happening, and data is modified at the database server without leaving the server machine.</li>
<li>Finally the program request a save of the modified data. Since the modified data resides in the database server, no data transfer happens over the network.</li>
</ul>
By moving the code to the data, the volume of data transfer over network is significantly reduced. This is an important paradigm shift for big data processing.<br />
<br />
In the following session, I will use Apache Spark to illustrate how this big data processing paradigm is implemented.<br />
<br />
<h3>
RDD</h3>
Resilient Distributed Dataset (RDD) is how Spark implements the data reference concept. RDD is a logical reference of a dataset which is partitioned across many server machines in the cluster.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEigbQVz_uA6lqk56q8Rdgsvms5fMa21iK3Ry5mxATpUpkjjQKo1Djyw98Gh1IGVMTz35rLb9kQbb825OSKd-SGnj8JvfwTGftmm_g3_mwRtgLVuhy2U1w2YTn0TRHWd4c-Eh-IxB51DXoou/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEigbQVz_uA6lqk56q8Rdgsvms5fMa21iK3Ry5mxATpUpkjjQKo1Djyw98Gh1IGVMTz35rLb9kQbb825OSKd-SGnj8JvfwTGftmm_g3_mwRtgLVuhy2U1w2YTn0TRHWd4c-Eh-IxB51DXoou/s1600/p1.png" height="194" width="200" /></a></div>
<br />
To make a clear distinction between data reference and data itself, a Spark program is organized as a sequence of execution steps, which can either be a "transformation" or an "action".<br />
<br />
<h3>
Programming Model </h3>
A typical program is organized as follows<br />
<ol>
<li>From an environment variable "context", create some initial data reference RDD objects</li>
<li>Transform initial RDD objects to create more RDD objects. Transformation is expressed in terms of functional programming where a code block is shipped from the driver program to multiple remote worker server, which hold a partition of the RDD. Variable appears inside the code block can either be an item of the RDD or a local variable inside the driver program which get serialized over to the worker machine. After the code (and the copy of the serialized variables) is received by the remote worker server, it will be executed there by feeding the items of RDD residing in that partition. Notice that the result of a transformation is a brand new RDD (the original RDD is not mutated)</li>
<li>Finally, the RDD object (the data reference) will need to be materialized. This is achieved through an "action", which will dump the RDD into a storage, or return its value data to the driver program.</li>
</ol>
Here is a word count example <br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code># Get initial RDD from the context
file = spark.textFile("hdfs://...")
# Three consecutive transformation of the RDD
counts = file.flatMap(lambda line: line.split(" "))
.map(lambda word: (word, 1))
.reduceByKey(lambda a, b: a + b)
# Materialize the RDD using an action
counts.saveAsTextFile("hdfs://...")
</code></pre>
<br />
When the driver program starts its execution, it builds up a graph where nodes are RDD and edges are transformation steps. However, no execution is happening at the cluster until an action is encountered. At that point, the driver program will ship the execution graph as well as the code block to the cluster, where every worker server will get a copy.<br />
<br />
The execution graph is a DAG.<br />
<ul>
<li>Each DAG is a atomic unit of execution. </li>
<li>Each source node (no incoming edge) is an external data source or driver memory</li>
<li>Each intermediate node is a RDD</li>
<li>Each sink node (no outgoing edge) is an external data source or driver memory</li>
<li>Green edge connecting to RDD represents a transformation. Red edge connecting to a sink node represents an action</li>
</ul>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhzjurS4A9q4CBYDTmFx0BhvVbhgVZI0Qx2xm7NIaYueBtRpZH724r8_zeNo1TuznT1L4-Y7Fnk2-lFOhQk8VUi7LgV8IRxh8o77_2kntbHm69pPI8FSNp59pRrQvgr0ZM39pDYpUd8AdPJ/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhzjurS4A9q4CBYDTmFx0BhvVbhgVZI0Qx2xm7NIaYueBtRpZH724r8_zeNo1TuznT1L4-Y7Fnk2-lFOhQk8VUi7LgV8IRxh8o77_2kntbHm69pPI8FSNp59pRrQvgr0ZM39pDYpUd8AdPJ/s1600/p1.png" height="320" width="227" /></a></div>
<br />
<br />
<h3>
Data Shuffling</h3>
Although we ship the code to worker server where the data processing happens, data movement cannot be completely eliminated. For example, if the processing requires data residing in different partitions to be grouped first, then we need to shuffle data among worker server.<br />
<br />
Spark carefully distinguish "transformation" operation in two types.<br />
<ul>
<li>"Narrow transformation" refers to the processing where the processing logic depends only on data that is already residing in the partition and data shuffling is unnecessary. Examples of narrow transformation includes filter(), sample(), map(), flatMap() .... etc.</li>
<li>"Wide transformation" refers to the processing where the processing logic depends on data residing in multiple partitions and therefore data shuffling is needed to bring them together in one place. Example of wide transformation includes groupByKey(), reduceByKey() ... etc.</li>
</ul>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQAPEo78CFomtw2GGwjS0L8Muaq_5u4AJzKIOj4aUIOJ6WER4UuiP2JmRYWokk6rIhe_icQ0LDKJ7FTwj0azQOt5FVxWg1T6qhpiG0wmB83wuwxPmEtZdSKEU96sMucZbaJsTNKMG6f6NU/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQAPEo78CFomtw2GGwjS0L8Muaq_5u4AJzKIOj4aUIOJ6WER4UuiP2JmRYWokk6rIhe_icQ0LDKJ7FTwj0azQOt5FVxWg1T6qhpiG0wmB83wuwxPmEtZdSKEU96sMucZbaJsTNKMG6f6NU/s1600/p1.png" height="255" width="400" /></a></div>
<br />
<br />
Joining two RDD can also affect the amount of data being shuffled. Spark provides two ways to join data. In a shuffle join implementation, data of two RDD with the same key will be redistributed to the same partition. In other words, each of the items in each RDD will be shuffled across worker servers.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfjn6DPCMxSUVpmc89rkiFQ1l1MROXj14X-2-XUWNJXXuKzgRg8GbZK6xUO7Ll_S-KThg06NS7xuB3Dc0jdvta02DLgu8_SXfgUEA3A5Fqt35VMFUPy9eqHbOHgTUe38DvGvV9lTAcgib2/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfjn6DPCMxSUVpmc89rkiFQ1l1MROXj14X-2-XUWNJXXuKzgRg8GbZK6xUO7Ll_S-KThg06NS7xuB3Dc0jdvta02DLgu8_SXfgUEA3A5Fqt35VMFUPy9eqHbOHgTUe38DvGvV9lTAcgib2/s1600/p1.png" height="242" width="400" /></a></div>
<br />
Beside shuffle join, Spark provides another alternative call broadcast join. In this case, one of the RDD will be broadcasted and copied over to every partition. Imagine the situation when one of the RDD is significantly smaller relative to the other, then broadcast join will reduce the network traffic because only the small RDD need to be copied to all worker servers while the large RDD doesn't need to be shuffled at all.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBzpNpAI3jXhhljUJHRn42ZACuDkm8oOKOPjzBlv5m_HQDC55J5BISPrRKT3WJIhZQF1WhB7VlxIw-ZtzmquSrTnIJIuqLM3nB7qLzaWgNgGJCg47Z8Mz0QFIkkudFm3BBq-GwLh5sTd2m/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBzpNpAI3jXhhljUJHRn42ZACuDkm8oOKOPjzBlv5m_HQDC55J5BISPrRKT3WJIhZQF1WhB7VlxIw-ZtzmquSrTnIJIuqLM3nB7qLzaWgNgGJCg47Z8Mz0QFIkkudFm3BBq-GwLh5sTd2m/s1600/p1.png" height="242" width="400" /></a></div>
<br />
<br />
In some cases, transformation can be re-ordered to reduce the amount of data shuffling. Below is an example of a JOIN between two huge RDDs followed by a filtering.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJ0cGMHrQ1aKkTN_w56RLiNP9viUPY2EU6WA01x_leSPhmetDnTbyNNEyvd0ykGdxwrIgE3eSfUtbOjp4-30Vi4XEkkfgV8S5UnotT4WRHcj8-nDbxGAmY6XzwsDub2DEMogfjzI-MHZOM/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJ0cGMHrQ1aKkTN_w56RLiNP9viUPY2EU6WA01x_leSPhmetDnTbyNNEyvd0ykGdxwrIgE3eSfUtbOjp4-30Vi4XEkkfgV8S5UnotT4WRHcj8-nDbxGAmY6XzwsDub2DEMogfjzI-MHZOM/s1600/p1.png" height="260" width="400" /></a></div>
<br />
<br />
Plan1 is a naive implementation which follows the given order. It first join the two huge RDD and then apply the filter on the join result. This ends up causing a big data shuffling because the two RDD is huge, even though the result after filtering is small.<br />
<br />
Plan2 offers a smarter way by using the "push-down-predicate" technique where we first apply the filtering in both RDDs before joining them. Since the filtering will reduce the number of items of each RDD significantly, the join processing will be much cheaper.<br />
<br />
<h3>
Execution planning </h3>
As explain above, data shuffling incur the most significant cost in the overall data processing flow. Spark provides a mechanism that generate an execute plan from the DAG that minimize the amount of data shuffling.<br />
<ol>
<li>Analyze the DAG to determine the order of transformation. Notice that we starts from the action (terminal node) and trace back to all dependent RDDs.</li>
<li>To minimize data shuffling, we group the narrow transformation together in a "stage" where all transformation tasks can be performed within the partition and no data shuffling is needed. The transformations becomes tasks that are chained together within a stage</li>
<li>Wide transformation sits at the boundary of two stages, which requires data to be shuffled to a different worker server. When a stage finishes its execution, it persist the data into different files (one per partition) of the local disks. Worker nodes of the subsequent stage will come to pickup these files and this is where data shuffling happens </li>
</ol>
Below is an example how the execution planning turns the DAG into an execution plan involving stages and tasks.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIQm-Qffx6ZNmkYF4F-aaRNoHLYxOFkguvCtjg8zTq4Gp0hEV-LogsPXt69zWt3iw24AcBiu35FhfUSvqDj1pztZimzx3PrWWFb65hfv0VTxiWT2rXhL5FL8f57std7xk1DZHe6untxUve/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIQm-Qffx6ZNmkYF4F-aaRNoHLYxOFkguvCtjg8zTq4Gp0hEV-LogsPXt69zWt3iw24AcBiu35FhfUSvqDj1pztZimzx3PrWWFb65hfv0VTxiWT2rXhL5FL8f57std7xk1DZHe6untxUve/s1600/p1.png" height="320" width="274" /></a></div>
<br />
<h3>
Reliability and Fault Resiliency </h3>
Since the DAG defines a deterministic transformation steps between different partitions of data within each RDD RDD, fault recovery is very straightforward. Whenever a worker server crashes during the execution of a stage, another worker server can simply re-execute the stage from the beginning by pulling the input data from its parent stage that has the output data stored in local files. In case the result of the parent stage is not accessible (e.g. the worker server lost the file), the parent stage need to be re-executed as well. Imagine this is a lineage of transformation steps, and any failure of a step will trigger a restart of execution from its last step.<br />
<br />
Since the DAG itself is an atomic unit of execution, all the RDD values will be forgotten after the DAG finishes its execution. Therefore, after the driver program finishes an action (which execute a DAG to its completion), all the RDD value will be forgotten and if the program access the RDD again in subsequent statement, the RDD needs to be recomputed again from its dependents. To reduce this repetitive processing, Spark provide a caching mechanism to remember RDDs in worker server memory (or local disk). Once the execution planner finds the RDD is already cache in memory, it will use the RDD right away without tracing back to its parent RDDs. This way, we prune the DAG once we reach an RDD that is in the cache.<br />
<br />
<br />
Overall speaking, Apache Spark provides a powerful framework for big data processing. By the caching mechanism that holds previous computation result in memory, Spark out-performs Hadoop significantly because it doesn't need to persist all the data into disk for each round of parallel processing. Although it is still very new, I think Spark will take off as the main stream approach to process big data.<br />
<br />Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-892426961423521792014-11-28T22:11:00.000-08:002014-11-28T22:12:07.068-08:00Spark StreamingIn this post, we'll discuss another important topic of big data processing: real-time stream processing area. This is an area where Hadoop falls short because of its high latency, and another open source framework Storm is developed to cover the need in real-time processing. Unfortunately, Hadoop and Storm provides quite different programming model, resulting in high development and maintenance cost.<br />
<br />
Continue from <a href="http://horicky.blogspot.com/2013/12/spark-low-latency-massively-parallel.html" target="_blank">my previous post on Spark</a>, which provides a highly efficient parallel processing framework. Spark streaming is a natural extension of its core programming paradigm to provide large-scale, real-time data processing. The biggest benefits of using Spark Streaming is that it is based on a similar programming paradigm of its core and there is no need to develop and maintain a completely different programming paradigm for batch and realtime processing.<br />
<br />
<br />
<h3>
Spark Core Programming Paradigm Recap</h3>
The core Spark programming paradigm consists of the following steps ...<br />
<ol>
<li>Taking input data from an external data source and create an RDD (a distributed data set across many servers)</li>
<li>Transform the RDD to another RDD (these transformation defines a direct acyclic graph of dependencies between RDD)</li>
<li>Output the final RDD to an external data source</li>
</ol>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVX-orY2Ag8_fRAItH6Pafi-jVob0G0qvGgrKbEbz5pxvSOZgjhvqmmWXlrEhgLEzsUD7Y3FrOxoBAX5jdeeyEyrTN9MmNN6-2SndcRJuP9r3BbbU7UnuQFmFiTB9d2_PVTSvsTOWbTdem/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVX-orY2Ag8_fRAItH6Pafi-jVob0G0qvGgrKbEbz5pxvSOZgjhvqmmWXlrEhgLEzsUD7Y3FrOxoBAX5jdeeyEyrTN9MmNN6-2SndcRJuP9r3BbbU7UnuQFmFiTB9d2_PVTSvsTOWbTdem/s1600/p1.png" height="200" width="133" /></a></div>
<br />
Notice that the RDD is immutable, therefore the sequence of transformations is deterministic and therefore recovery from intermediate processing failure is simply by tracing back to the parent of the failure node (in the DAG) and redo the processing from there.<br />
<br />
<br />
<h3>
Spark Streaming</h3>
Spark Streaming introduce a data structure call DStream which is basically a sequence of RDD where each RDD contains data associated with a time interval. DStream is created with a frequency parameters which defines the frequency RDD creation into the sequence.<br />
<br />
Transformation of a DStream boils down to transformation of each RDD (within the sequence of RDD that the DStream contains). Within the transformation, the RDD inside the DStream can "join" with another RDD (outside the DStream), hence provide a mix processing paradigm between DStream and other RDDs. Also, since each transformation produces an output RDD, the result of transforming a DStream results in another sequence of RDDs that defines an output DStream.<br />
<br />
Here is the basic transformation where each RDD in the output DStream has a one to one correspondence with each RDD in the input DStream. <br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi0EFOJ7MFyHyqbED3jym-fPg7SwppyEKeYNLCCr_JlCcwgHqWxgw6rss_ofENFrHiYIqOrQp_nsgbjOaRCISn8UziIrcRApXFlN8nJi36ol7M-n0MaLWmcfkqIsYOBs7EuUT7TDhX8BjEg/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi0EFOJ7MFyHyqbED3jym-fPg7SwppyEKeYNLCCr_JlCcwgHqWxgw6rss_ofENFrHiYIqOrQp_nsgbjOaRCISn8UziIrcRApXFlN8nJi36ol7M-n0MaLWmcfkqIsYOBs7EuUT7TDhX8BjEg/s1600/p1.png" height="192" width="400" /></a></div>
<br />
Instead of performing a 1 to 1 transformation of each RDD in the DStream. Spark streaming enable a sliding window operation by defining a WINDOW which groups consecutive RDDs along the time dimension. There are 2 parameters that the window is defined ...<br />
<ol>
<li>Window length: defines how many consecutive RDDs will be combined for performing the transformation. </li>
<li>Slide interval: defines how many RDD will be skipped before the next transformation executes.</li>
</ol>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhUXdOIR1raPlrK0u5VcQQadIv8WqCusGuEEf2hknLL_QaX2-btR9qTOIppKdw1zc_y7sEZRDCgHMXLUSIk6okV3z2DxO20mOsBdUPzi56xeLeOgqyDni8i9xJykheRv3zCtxXl4VM0Ecoe/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhUXdOIR1raPlrK0u5VcQQadIv8WqCusGuEEf2hknLL_QaX2-btR9qTOIppKdw1zc_y7sEZRDCgHMXLUSIk6okV3z2DxO20mOsBdUPzi56xeLeOgqyDni8i9xJykheRv3zCtxXl4VM0Ecoe/s1600/p1.png" height="247" width="400" /></a></div>
<br />
<br />
By providing a similar set of transformation operation for both RDD and DStream, Spark enable a unified programming paradigm across both batch and real-time processing, and hence reduce the corresponding development and maintenance cost.Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-41498432746133521252014-11-05T16:01:00.000-08:002014-11-05T16:04:42.159-08:00Common data science project flowAs working across multiple data science projects, I observed a similar pattern across a group of strategic data science projects where a common methodology can be used. In this post, I want to sketch this methodology at a high level.<br />
<br />
First of all, "data science" itself is a very generic term that means different things to different people. For the projects I involved, many of them target to solve a very tactical and specific problem. However, over the last few years more and more enterprises start to realize the strategic value of data. I observed a growing number of strategic data science projects were started from a very broad scope and took a top-down approach to look at the overall business operation. Along the way, the enterprise prioritize the most critical areas within their operation cycle and build sophisticated models to guide and automate the decision process.<br />
<br />
Usually, my engagement started as a data scientist / consultant, with very little (or even no) domain knowledge. Being unfamiliar with the domain is nothing to be proud of and often slow down my initial discussion. Therefore, within a squeezed time period I need to quickly learn enough "basic domain knowledge" to facilitate the discussion smooth. On the other hand, lacking a per-conceived model enables me (or you can say force me) to look from a fresh-eye view, from which I can trim off unnecessary details from the legacies and only focus on those essential elements that contributes to the core part of the data model. It is also fun to go through the concept blending process between a data scientist and a domain expert. I force them to think in my way and they force me to think in their way. This is by far the most effective way for me to learn any new concepts.<br />
<br />
Recently I had a discussion with a company who has a small, but very sophisticated data science team that build pricing model, and demand forecasting for their product line. I am, by no means an expert in their domain. But their problem (how to predict demand, and how to set price) is general enough across many industries. Therefore, I will use this problem as an example to illustration the major steps in the common pattern that I describe above.<br />
<br />
<h3>
Problem Settings</h3>
Lets say a car manufacturer starts its quarterly planning process. Here are some key decisions that need to be made by the management.<br />
<ul>
<li>How many cars the company should produce for next year ?</li>
<li>What should be the renew price of the cars ?</li>
</ul>
First of all, we need to identify the ultimate "goal" of these decisions. Such goal is usually easy to find as it usually in the company's mission statement.<br />
<br />
In this problem, the goal is to ...<br />
<span style="color: red;">maximize: "Profit_2015"</span> <br />
<br />
In general, I find it is a good start to look at the problem from an "optimization" angle, from which we define our goal in terms of an objective function as well as a set of constraints.<br />
<br />
<h3>
Step 1: Identify variables and define its dependency graph</h3>
Build the dependency graph between different variables starting from the Objective function. Separate between the decision variables (where you have control) and environment variable (where you have no control).<br />
<br />
As an illustrative example, we start from our objective function "Profit_2015" and define the dependency relationship below. Decision variable is highlighted in blue.<br />
<br />
<span style="color: red;">Profit_2015 = F(UnitSold_2015, <span style="color: blue;">UnitProduced_2015, Price_2015</span>, Cost_2015)</span><br />
<span style="color: red;">UnitSold_2015 = G(Supply_2015, Demand_2015, <span style="color: blue;">Price_2015</span>, CompetitorPrice_2015)</span><br />
<span style="color: red;">Demand_2015 = H(GDP_2014, PhoneSold_2014)</span><br />
<span style="color: red;">GDP_2015 = T(GDP_2014, GDP_2013, GDP_2012, GDP_2011 ...) </span><br />
<span style="color: red;">...</span><br />
<br />
Identifying these variable and their potential dependencies typically come from a well-studied theory from University, or domain experts in the industry. At this stage, we don't need to know the exact formula of the function F/G/H. We only need to capture the links between the variables. It is also ok to include a link that shouldn't have exist (ie: there is no relationship between the 2 variables in reality). However, it is not good if we miss a link (ie: fail to capture a strong, existing dependency).<br />
<br />
This round usually involves 4 to 5 half day brainstorming sessions with the domain experts, facilitated by the data scientist/consultant who is familiar with the model building process. There may be additional investigation, background studies if the subject matter experts doesn't exist. Starting from scratch, this round can take somewhere between couple weeks to couple months<br />
<br />
<h3>
Step 2: Define the dependency function </h3>
In this round, we want to identify the relationship between variable using formula of F(), G(), H().<br />
<br />
<br />
<u><b>Well-Known Function </b></u><br />
For some relationship that is well-studied, we can use a known mathematical model.<br />
<br />
For example, in the relationship <br />
<span style="color: red;">Profit_2015 = F(UnitSold_2015, <span style="color: blue;">UnitProduced_2015, Price_2015</span>, Cost_2015)</span><br />
<br />
We can use the following Mathematical formula in a very straightforward manner<br />
<span style="color: red;">Profit = (UnitSold * <span style="color: blue;">Price</span>) - (<span style="color: blue;">UnitProduced</span> * Cost)</span><br />
<br />
<br />
<u><b>Semi-Known Function</b></u><br />
However, some of the relationship is not as straightforward as that. For those relationship that we don't exactly know the formula, but can make a reasonable assumption on the shape of the formula, we can assume the relationship follows a family of models (e.g. Linear, Quadratic ... etc.), and then figure out the optimal parameters that best fit the historical data.<br />
<br />
For example, in the relationship<br />
<span style="color: red;">Demand_2015 = H(GDP_2014, PhoneSold_2014)</span><br />
<br />
Lets assume the "demand" is a linear combination of "GDP" and "Phone sold", which seems to be a reasonable assumption.<br />
<br />
For the linear model we assume<br />
<span style="color: red;">Demand = w0 + (w1 * GDP) + (w2 * PhoneSold)</span><br />
<br />
Then we feed the historical training data to a build a linear regression model and figure out what the fittest value of w0, w1, w2 should be.<br />
<br />
<br />
<u><b>Time-Series Function</b></u><br />
In some cases, a variable depends only on its own past value but not other variables, here we can train a Time Series model to predict the variable based on its own past values. Typically, the model is decomposed into 3 components; Noise, Trend and Seasonality. One popular approach is to use <a href="http://en.wikipedia.org/wiki/Exponential_smoothing" target="_blank">exponential smoothing techniques</a> such as Holt/Winters model. Another popular approach is to use <a href="http://en.wikipedia.org/wiki/Autoregressive_integrated_moving_average" target="_blank">the ARIMA model</a> which decomposed the value into "Auto-Regression" and "Moving-Average".<br />
<br />
For example, in the relationship<br />
<span style="color: red;">GDP_2015 = T(GDP_2014, GDP_2013, GDP_2012, GDP_2011 ...) </span><br />
<br />
We can use TimeSeries model to learn the relationship between the historical data to its future value. <br />
<br />
<br />
<u><b>Completely Unknown Function</b></u><br />
But if we cannot even assume the model family, we can consider using "k nearest neighbor" approach to interpolate the output from its input. We need to define the "distance function" between data points based on domain knowledge and also to figure out what the optimal value of k should be. In many case, using a weighted average of the k-nearest neighbor is a good interpolation.<br />
<br />
For example, in the relationship<br />
<span style="color: red;">UnitSold_2015 = G(Supply_2015, Demand_2015, <span style="color: blue;">Price_2015</span>, CompetitorPrice_2015)</span><br />
It is unclear what model to be used in representing UnitSold as a function of Supply, Demand, Price and CompetitorPrice. So we go with a nearest neighbor approach.<br />
<br />
Based on monthly sales of past 3 years, we can use "Euclidean distance" (we can also consider scaling the data to a comparable range by minus its mean and divide by its standard deviation) to find out the closest 5 neighbors, and then using the weighted average to predict the unit sold.<br />
<br />
<h3>
Step 3: Optimization</h3>
At this point, we have the following defined<br />
<ul>
<li>A goal defined by maximizing (or minimizing) an objective function</li>
<li>A set of variables (including the decision and environment variables)</li>
<li>A set of functions that define how these variables are inter-related to each other. Some of them is defined by a mathematical formula and some of them is defined as a black-box (base on a predictive model)</li>
</ul>
Our goal is to figure out what the decision variables (which we have control) should be set such that the objective function is optimized (maximized or minimized).<br />
<br />
<u><b>Determine the value of environment variables</b></u><br />
For those environment variables that has no dependencies on other variables, we can acquire their value from external data sources. For those environment variables that has dependencies on other environment variables (but not decision variables), we can estimate their value using the corresponding dependency function (of course, we need to estimate all its depending variables first). For those environment variables that has dependencies (direct or indirect) on decision variables, leave it as undefined.<br />
<br />
<u><b>Determine the best value of decision variables</b></u><br />
Once we formulate the dependency function, depends on the format of these function, we can employ different optimization methods. Here is how I choose the appropriate method based on the formulation of dependency functions.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhF-6b74rQFBonEUbUrjgMVZB-vJakSPCOaVuGpFziEKH4rB02P9e-AGkmwyZfY8_wF2eVWBJElxtUUZnbgoj2mDpqe4UEJkNFyuZ1uxc6CT3OGrJtYAOEi_o3KhukF8-82ebtJw0na6S0A/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhF-6b74rQFBonEUbUrjgMVZB-vJakSPCOaVuGpFziEKH4rB02P9e-AGkmwyZfY8_wF2eVWBJElxtUUZnbgoj2mDpqe4UEJkNFyuZ1uxc6CT3OGrJtYAOEi_o3KhukF8-82ebtJw0na6S0A/s1600/p1.png" height="372" width="400" /></a></div>
<br />
<br />
<h3>
Additional Challenges</h3>
To summarize, we have following the process below <br />
<ol>
<li>Define an objective function, constraints, decision variables and environment variables</li>
<li>Identify the relationship between different variables</li>
<li>Collect or predict those environment variables</li>
<li>Optimize those decision variables based on the objective functions</li>
<li>Return the optimal value of decision variables as the answer</li>
</ol>
So far, our dependency graph is acyclic where our decision won't affect the underlying variables. Although this is reasonably true if the enterprise is an insignificant small player in the market, it is no longer true if the enterprise is one of the few major players. For example, their pricing strategy may causes other competitors to change their own pricing strategy as well. And how the competitors would react is less predictable and historical data play a less important role here. At some point, human judgement will get involved to fill the gaps.<br />
<br />
<br />
<br />Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-3241974056233231022014-08-17T22:36:00.000-07:002014-08-17T23:20:43.030-07:00Lambda Architecture Principles"Lambda Architecture" (introduced by Nathan Marz) has gained a lot of traction recently. Fundamentally, it is a set of design patterns of dealing with Batch and Real time data processing workflow that fuel many organization's business operations. Although I don't realize any novice ideas has been introduced, it is the first time these principles are being outlined in such a clear and unambiguous manner.<br />
<br />
In this post, I'd like to summarize the key principles of the Lambda architecture, focus more in the underlying design principles and less in the choice of implementation technologies, which I may have a different favors from Nathan.<br />
<br />
One important distinction of Lambda architecture is that it has a clear separation between the batch processing pipeline (ie: Batch Layer) and the real-time processing pipeline (ie: Real-time Layer). Such separation provides a means to localize and isolate complexity for handling data update. To handle real-time query, Lambda architecture provide a mechanism (ie: Serving Layer) to merge/combine data from the Batch Layer and Real-time Layer and return the latest information to the user.<br />
<br />
<h3>
Data Source Entry</h3>
At the very beginning, data flows in Lambda architecture as follows ...<br />
<ul>
<li>Transaction data starts streaming in from OLTP system during business operations. Transaction data ingestion can be materialized in the form of records in OLTP systems, or text lines in App log files, or incoming API calls, or an event queue (e.g. Kafka)</li>
<li>This transaction data stream is replicated and fed into both the Batch Layer and Realtime Layer</li>
</ul>
Here is an overall architecture diagram for Lambda. <br />
<ul>
</ul>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhG1Iz8jjvzNmHVcO5bcQZAINdLl2XytP0M9JOmjLvtrg2VnjzE_QeEVdWRpAE9URMT1x5HMNQoY0Un24pp3ModJyo8FQM3YnCVFyZH7TnTGVF8hB3Sr_ppC9Oa8A8DG7REI7yPV38Fi5b8/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhG1Iz8jjvzNmHVcO5bcQZAINdLl2XytP0M9JOmjLvtrg2VnjzE_QeEVdWRpAE9URMT1x5HMNQoY0Un24pp3ModJyo8FQM3YnCVFyZH7TnTGVF8hB3Sr_ppC9Oa8A8DG7REI7yPV38Fi5b8/s1600/p1.png" height="291" width="400" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<br />
<h3>
Batch Layer </h3>
For storing the ground truth, "Master dataset" is the most fundamental DB that captures all basic event happens. It stores data in the most "raw" form (and hence the finest granularity) that can be used to compute any perspective at any given point in time. As long as we can maintain the correctness of master dataset, every perspective of data view derived from it will be automatically correct.<br />
<br />
Given maintaining the correctness of master dataset is crucial, to avoid the complexity of maintenance, master dataset is "immutable". Specifically data can only be appended while update and delete are disallowed. By disallowing changes of existing data, it avoids the complexity of handling the conflicting concurrent update completely.<br />
<br />
Here is a conceptual schema of how the master dataset can be structured. The center green table represents the old, traditional-way of storing data in RDBMS. The surrounding blue tables illustrates the schema of how the master dataset can be structured, with some key highlights<br />
<ul>
<li>Data are partitioned by columns and stored in different tables. Columns that are closely related can be stored in the same table</li>
<li>NULL values are not stored</li>
<li>Each data record is associated with a time stamp since then the record is valid</li>
</ul>
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9XWcGrfihqAJPPe1UTa6jeA_-QQAiBJDT44tPl5HBdli0kZazKome8cEk1nETCFgSfHDBGRrIf9kZv2Apjj56YqMqZ0gsY9n7k-0ACXWQ9OnivkIU3as5W0kpH9f-UyhK_tQPzhD7OIM9/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9XWcGrfihqAJPPe1UTa6jeA_-QQAiBJDT44tPl5HBdli0kZazKome8cEk1nETCFgSfHDBGRrIf9kZv2Apjj56YqMqZ0gsY9n7k-0ACXWQ9OnivkIU3as5W0kpH9f-UyhK_tQPzhD7OIM9/s1600/p1.png" height="290" width="400" /></a></div>
<br />
<br />
Notice that every piece of data is tagged with a time stamp at which
the data is changed (or more precisely, a change record that represents
the data modification is created). The latest state of an object can be retrieved by extracting the version of the object with the largest time stamp.<br />
<br />
Although master dataset stores data in the finest granularity and therefore can be used to compute result of any query, it usually take a long time to perform such computation if the processing starts with such raw form. To speed up the query processing, various data at intermediate form (called Batch View) that aligns closer to the query will be generated in a periodic manner. These batch views (instead of the original master dataset) will be used to serve the real-time query processing. <br />
<br />
To generate these batch views, the "Batch Layer" use a massively parallel, brute force approach to process the original master dataset. Notice that since data in master data set is timestamped, the data candidate can be identified simply from those that has the time stamp later than the last round of batch processing. Although less efficient, Lambda architecture advocates that at each round of batch view generation, the previous batch view should just be simply discarded and the new batch view is computed from master dataset. This simple-mind, compute-from-scratch approach has some good properties in stopping error propagation (since error cannot be accumulated), but the processing may not be optimized and may take a longer time to finish. This can increase the "staleness" of the batch view.<br />
<br />
<h3>
Real time Layer</h3>
As discussed above, generating the batch view requires scanning a large volume of master dataset that takes few hours. The batch view will therefore be stale for at least the processing time duration (ie: between the start and end of the Batch processing). But the maximum staleness can be up to the time period between the end of this Batch processing and the end of next Batch processing (ie: the batch cycle). The following diagram illustrate this staleness.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_aUWE7wOtTtCDDcsgj7GVs6ollDf21lpqcGtOjYw-iJ5YNgm8a1n24MwjRvazA4Z4-sZC-URFr-RlHlJ_SUrurQQx2QsyDQ0et_svnEr00G5AIXpPwpTZFr8ablwgR6QvM3WXzXtc3tiq/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_aUWE7wOtTtCDDcsgj7GVs6ollDf21lpqcGtOjYw-iJ5YNgm8a1n24MwjRvazA4Z4-sZC-URFr-RlHlJ_SUrurQQx2QsyDQ0et_svnEr00G5AIXpPwpTZFr8ablwgR6QvM3WXzXtc3tiq/s1600/p1.png" height="185" width="320" /></a></div>
<br />
Even the batch view is stale period, business operates as usual and transaction data will be streamed in continuously. To answer user's query with the latest, up-to-date information. The business transaction records need to be captured and merged into the real-time view. This is the responsibility of the Real-time Layer. To reduce the latency of latest information availability close to zero, the merge mechanism has to be done in an incremental manner such that no batching delaying the processing will be introduced. This requires the real time view update to be very different from the batch view update, which can tolerate a high latency. The end goal is that the latest information that is not captured in the Batch view will be made available in the Realtime view.<br />
<br />
The logic of doing the incremental merge on Realtime view is application specific. As a common use case, lets say we want to compute a set of summary statistics (e.g. mean, count, max, min, sum, standard deviation, percentile) of the transaction data since the last batch view update. To compute the sum, we can simply add the new transaction data to the existing sum and then write the new sum back to the real-time view. To compute the mean, we can multiply the existing count with existing mean, adding the transaction sum and then divide by the existing count plus one. To implement this logic, we need to READ data from the Realtime view, perform the merge and WRITE
the data back to the Realtime view. This requires the Realtime serving
DB (which host the Realtime view) to support both random READ and WRITE.
Fortunately, since the realtime view only need to store the stale data up to
one batch cycle, its scale is limited to some degree.<br />
Once the batch view update is completed, the real-time layer will discard the data from the real time serving DB that has time stamp earlier than the batch processing. This not only limit the data volume of Realtime serving DB, but also allows any data inconsistency (of the realtime view) to be clean up eventually. This drastically reduce the requirement of sophisticated multi-user, large scale DB. Many DB system support multiple user random read/write and can be used for this purpose.<br />
<br />
<h3>
Serving Layer</h3>
The serving layer is responsible to host the batch view (in the batch serving database) as well as hosting the real-time view (in the real-time serving database). Due to very different accessing pattern, the batch serving DB has a quite different characteristic from the real-time serving DB.<br />
<br />
As mentioned in above, while required to support efficient random read at large scale data volume, the batch serving DB doesn't need to support random write because data will only be bulk-loaded into the batch serving DB. On the other hand, the real-time serving DB will be incrementally (and continuously) updated by the real-time layer, and therefore need to support both random read and random write. <br />
<br />
To maintain the batch serving DB updated, the serving layer need to periodically check the batch layer progression to determine whether a later round of batch view generation is finished. If so, bulk load the batch view into the batch serving DB. After completing the bulk load, the batch serving DB has contained the latest version of batch view and some data in the real-time view is expired and therefore can be deleted. The serving layer will orchestrate these processes. This purge action is especially important to keep the size of the real-time serving DB small and hence can limit the complexity for handling real-time, concurrent read/write.<br />
<br />
To process a real-time query, the serving layer disseminates the incoming query into 2 different sub-queries and forward them to both the Batch serving DB and Realtime serving DB, apply application-specific logic to combine/merge their corresponding result and form a single response to the query. Since the data in the real-time view and batch view are different from a timestamp perspective, the combine/merge is typically done by concatenate the results together. In case of any conflict (same time stamp), the one from Batch view will overwrite the one from Realtime view.<br />
<br />
<h3>
Final Thoughts</h3>
By separating different responsibility into different layers, the Lambda architecture can leverage different optimization techniques specifically designed for different constraints. For example, the Batch Layer focuses in large scale data processing using simple, start-from-scratch approach and not worrying about the processing latency. On the other hand, the Real-time Layer covers where the Batch Layer left off and focus in low-latency merging of the latest information and no need to worry about large scale. Finally the Serving Layer is responsible to stitch together the Batch View and Realtime View to provide the final complete picture.<br />
<br />
The clear demarcation of responsibility also enable different technology stacks to be utilized at each layer and hence can tailor more closely to the organization's specific business need. Nevertheless, using a very different mechanism to update the Batch view (ie: start-from-scratch) and Realtime view (ie: incremental merge) requires two different algorithm implementation and code base to handle the same type of data. This can increase the code maintenance effort and can be considered to be the price to pay for bridging the fundamental gap between the "scalability" and "low latency" need.<br />
<br />
Nathan's Lambda architecture also introduce a set of candidate technologies which he has developed and used in his past projects (e.g. Hadoop for storing Master dataset, Hadoop for generating Batch view, ElephantDB for batch serving DB, Cassandra for realtime serving DB, STORM for generating Realtime view). The beauty of Lambda architecture is that the choice of technologies is completely decoupled so I intentionally do not describe any of their details in this post. On the other hand, I have my own favorite which is different and that will be covered in my future posts.Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com3tag:blogger.com,1999:blog-7994087232040033267.post-42141588120277810702014-07-27T15:44:00.001-07:002014-07-27T15:45:05.998-07:00Incorporate domain knowledge into predictive modelAs a data scientist / consultant, in many cases we are being called in to work with domain experts who has in-depth business knowledge of industry settings. The main objective is to help our clients to validate and quantify the intuition of existing domain knowledge based on empirical data, and remove any judgement bias. In many cases, customers will also want to build a predictive model to automate their business decision making process.<br />
<br />
To create a predictive model, <b>feature engineering</b> (defining the set of input) is a key part if not the most important. In this post, I'd like to share my experience in how to come up with the initial set of features and how to evolve it as we learn more.<br />
<br />
Firstly, we need to acknowledge two forces in this setting<br />
<ol>
<li>Domain experts tends to be narrowly focused (and potentially biased) towards their prior experience. Their domain knowledge can usually encoded in terms of <b>"business rules"</b> and tends to be simple and obvious (if it is too complex and hidden, human brain is not good at picking them up).</li>
<li>Data scientist tends to be less biased and good at mining through a large set of signals to determine how relevant they are in an objective and quantitative manner. Unfortunately, raw data rarely gives strong signals. And lacking the domain expertise, data scientist alone will not even be able to come up with a good set of features (usually requires derivation from the combination of raw data). Notice that trying out all combinations are impractical because there are infinite number of ways to combine raw data. Also, when you have too many features in the input, the training data will not be enough and resulting in model with high variance.</li>
</ol>
Maintain a balance between these forces is a critical success factor of many data science project.<br />
<br />
This best project settings (in my opinion) is to let the data scientist to take control in the whole exercise (as less bias has an advantage) while guided by input from domain experts.<br />
<br />
<h3>
Indicator Feature</h3>
This is a binary variable based on a very specific boolean condition (ie: true or false) that the domain expert believe to be highly indicative to the output. For example, for predicting stock, one indicator feature is whether the stock has been drop more than 15 % in a day.<br />
<br />
Notice that indicator features can be added at any time once a new boolean condition is discovered by the domain expert. Indicators features doesn't need to be independent to each other and in fact most of the time they are highly inter-correlated.<br />
<br />
After fitting these indicator features into the predictive model, we can see how many influence each of these features is asserting in the final prediction and hence providing a feedback to the domain experts about the strength of these signals.<br />
<br />
<h3>
Derived Feature</h3>
This is a numeric variable (ie: quantity) that the domain expert believe to be important to predicting the output. The idea is same as indicator feature except it is numeric in nature.<br />
<br />
<h3>
Expert Stacking</h3>
Here we build a predictive model whose input features are taking from each of the expert's prediction output. For example, to predict the stock, our model takes 20 analyst's prediction as its input.<br />
<br />
The strength of this approach is that it can incorporate domain expertise very easily because it treat them as a blackbox (without needing to understand their logic). The model we training will take into account the relative accuracy of each expert's prediction and adjust its weighting accordingly. On the other hand, one weakness is the reliance of domain expertise during the prediction, which may or may not be available in an on-going manner.<br />
<br />Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-28091916856156827722014-06-28T09:02:00.001-07:002014-06-28T09:03:11.828-07:00Interactive Data VisualizationRecently, "interactive report" is becoming a hot topic in data visualization. I believe it is becoming the next generation UI paradigm for KPI reports.<br />
<br />
Interactive report is sitting somewhere in between static report and BI tools …<br />
<br />
<h3>
Executive KPI report today</h3>
<h3>
</h3>
Today most executive reports are "static report" provided by financial experts by pulling data from various ERP system on the regular basis, summarize these raw data in a highly condensed and simplified form, then generate a static report for the execs. When the exec gets the report, it is already in a summarized form that is customized based on his/her prior requirement. There is no way to ask any other question that the report is not already showing. Of course, the exec can ask for a separate report which requires additional development time and effort on his/her staff, but also need to wait for the new report to be developed.<br />
<br />
This is a suboptimal situation. In order to survive or maintain leadership in today's highly competitive business environment, execs not just need a much broader perspective (from wide variety of operation data) to make his/her decision, but also he/she has to make the decision fast. Static report cannot fulfill this need.<br />
<br />
<br />
<br />
<h3>
Business Intelligence Tools </h3>
<br />
On the other hand, BI tools (such as Tableau) or OLAP tools can do very detail analysis in wide range of data sources. However, using these tools to perform more detail analysis (such as slice/dice/rollup/drilldown) typically requires specially trained data analysis skills. In reality, very few execs use these tools directly. What they do is to ask their data analyst to prepare a static report for them using these BI tools. The exec still get a "static report" although it is provided by the BI tools. Whenever they need to ask a different question, they need to go back to the data analyst and ask to prepare a separate report.<br />
<br />
<br />
<br />
There is a gap between the static report and BI tool.<br />
<br />
<h3>
Interactive Report </h3>
"Interactive Report" provides a new paradigm to fill this gap. It has the following characteristics …<br />
<ul>
<li>Like a static report, "Interactive Report" is still based on "static data", which is a fixed set of data generated in a periodic batch fashion.</li>
<li>Unlike static report, this pre-generated "static data" is much larger and wider that covers a broader scope of questions that the execs may ask.</li>
<li>Because the "static data" is large and wide, it is impossible to visualize all aspects in the report. Therefore, only one perspective of the static data (based on the exec's pre-specified requirement) is shown in the report.</li>
<li>However, if the exec wants to ask a different question, he/she can switch to a different perspective of the same "static data".</li>
</ul>
<br />
By providing a much large volume of static data, "interactive report" provides a more dynamic data navigation experience to the execs to find out the answer of their ad/hoc unplanned questions.<br />
<br />
<br />
<br />
There are many open source technologies (such as <a href="http://cran.r-project.org/web/packages/googleVis/vignettes/googleVis_examples.html" target="_blank">Googlevis</a>...) to support interactive data visualization from which the "interactive report" can be built. And many of them provides a programmatic interface with R so now data scientist without much Javascript experience can produce highly interactive web pages.Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-18440916210937282592014-03-12T00:06:00.001-07:002014-03-12T00:06:44.896-07:00Common Text Mining workflowIn this post, I want to summarize a common pattern that I have used in my previous text mining projects.<br />
<br />
Text mining is different in that it uses vocabulary term as a key elements in feature engineering, otherwise it is quite similar to a statistical data mining project. Following are the key steps ...<br />
<ol>
<li>Determine the "object" that we are interested to analyze. In some cases, the text document itself is the object (e.g. an email). In other cases, the text document is providing information about the object (e.g. user comment of a product, tweaks about a company)</li>
<li>Determine the features of the object we are interested, and create the corresponding feature vector of the object.</li>
<li>Feed the data (each object and its corresponding set of features) to standard descriptive analytics and predictive analytics techniques.</li>
</ol>
The overall process of text mining can be described in the following flow ...<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwSeKu07YIC7qaPEt7be585o6A7-oyHwvayhZy850naPlpMqjKYqiXMkge1U-FLcdIV2i_3HFav7eGEIYGmMPfmS2BrR1AfJPG-0jD9xH1umJU22-y5clX6FKhx61yHj77Yf5L-p4wgl0X/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwSeKu07YIC7qaPEt7be585o6A7-oyHwvayhZy850naPlpMqjKYqiXMkge1U-FLcdIV2i_3HFav7eGEIYGmMPfmS2BrR1AfJPG-0jD9xH1umJU22-y5clX6FKhx61yHj77Yf5L-p4wgl0X/s1600/p1.png" height="293" width="400" /></a></div>
<br />
<h3>
Extract docs</h3>
In this phase, we are extracting text document from various types of external sources into a text index (for subsequent search) as well as a text corpus (for text mining).<br />
<br />
Document source can be a public web site, an internal file system, or a SaaS offerings. Extracting documents typically involves one of the following ...<br />
<ul>
<li>Perform a google search or crawl a predefined list of web sites, then download the web page from the list of URL, parse the DOM to extract text data from its sub-elements, and eventually creating one or multiple documents, store them into the text index as well as text Corpus.</li>
<li>Invoke the Twitter API to search for tweets (or monitor a particular topic stream of tweets), store them into the text index and text Corpus.</li>
<li>There is no limit in where to download the text data. In an intranet environment, this can be downloading text document from a share drive. On the other hand, in a compromised computer, user's email or IM can also be download from the virus agent.</li>
<li>If the text is in a different language, we may also invoke some machine translation service (e.g. Google translate) to convert the language to English. </li>
</ul>
Once the document is stored in the text index (e.g. Lucene index), it is available for search. Also, once the document is stored in the text corpus, further text processing will be involved.<br />
<br />
<h3>
Transformation</h3>
After the document is stored in the Corpus, here are some typical transformations ...<br />
<ul>
<li>If we want to extract information about some entities mentioned in the document, we need to conduct sentence segmentation, paragraph segmentation in order to provide some local context from which we can analyze the entity with respect to its relationship with other entities.</li>
<li>Attach Part-Of-Speech tagging, or Entity tagging (person, place, company) to each word.</li>
<li>Apply standard text processing such as lower case, removing punctuation, removing numbers, removing stopword, stemming.</li>
<li>Perform domain specific conversion such as replace dddd-dd-dd with <date>, (ddd)ddd-dddd to <phone>, remove header and footer template text, remove terms according to domain-specific stop-word dictionary.</phone></date></li>
<li>Optionally, normalize the words to its synonyms using Wordnet or domain specific dictionary.</li>
</ul>
<br />
<h3>
Extract Features</h3>
For text mining, the "bag-of-words model" is commonly used as the feature set. In this model, each document is represented as a word vector (a high dimensional vector with magnitude represents the importance of that word in the document). Hence all documents within the corpus is represented as a giant document/term matrix. The "term" can be generalized as uni-gram, bi-gram, tri-gram or n-gram, while the cell value in the matrix represents the frequency of the term appears in the document. We can also use TF/IDF as the cell value to dampen the importance of those terms if it appears in many documents. If we just want to represent whether the term appears in the document, we can binarize the cell value into 0 or 1. <br />
<br />
After this phase, the Corpus will turn into a large and sparse document term matrix.<br />
<br />
<h3>
Reduce Dimensions</h3>
Since each row in the document/term matrix represents each document as a high dimension vector (with each dimension represents the occurrence of each term), there are two reasons we want to reduce its dimension ...<br />
<ol>
<li>For efficiency reason, we want to reduce the memory footprint for storing the corpus</li>
<li>We want to transform the vector from the "term" space to a "topic" space, which allows document of similar topics to situate close by each other even they use different terms. (e.g. document using the word "pet" and "cat" are map to the same topic based on their co-occurrence)</li>
</ol>
SVD (Singular Value Decomposition) is a common matrix factorization technique to convert a "term" vector into a "concept" vector. SVD can be used to factor a large sparse matrix of M by N into the multiplication of three smaller dense matrix M*K, K*K, K*N. Latent Semantic Indexing (LSI) is applying the SVD in the document term matrix.<br />
<br />
Another popular technique call topic modeling, based on LDA (Latent Dirichlet Allocation) is also commonly used to transform the document into a smaller set of topic dimensions.<br />
<br />
<h3>
Apply standard data mining</h3>
At this point, each document is represented as a topic vector. We can also add more domain specific features (such as for spam detection, whether the document contains certain word or character patterns such as '$', '!'). After that we can feed the each vector into the regular machine learning process.<br />
<br />
<h3>
Tools and Library</h3>
I have used Python's NLTK as well as R's TM, topicmodel library for performing the text mining work that I described above. Both of these library provide a good set of features for mining text documents. Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com1tag:blogger.com,1999:blog-7994087232040033267.post-10985909913772792072014-03-03T23:14:00.003-08:002014-03-03T23:21:20.041-08:00Estimating statistics via Bootstrapping and Monte Carlo simulationWe want to estimate some "statistics" (e.g. average income, 95 percentile height, variance of weight ... etc.) from a population.<br />
<br />
It will be too tedious to enumerate all members of the whole population. For efficiency reason, we randomly pick a number samples from the population, compute the statistics of the sample set to estimate the corresponding statistics of the population. We understand the estimation done this way (via random sampling) can deviate from the population. Therefore, in additional to our estimated statistics, we also include a "standard error" (how big our estimation may be deviated from the actual population statistics) or a "confidence interval" (a lower and upper bound of the statistics which we are confident about containing the true statistics).<br />
<br />
The challenge is how do we estimate the "standard error" or the "confidence interval". A straightforward way is to repeat the sampling exercise many times, each time we create a different sample set from which we compute one estimation. Then we look across all estimations from different sample sets to estimate the standard error and confidence interval of the estimation.<br />
<br />
But what if collecting data from a different sample set is expensive, or for any reason the population is no longer assessable after we collected our first sample set. Bootstrapping provides a way to address this ...<br />
<br />
<h3>
Bootstrapping </h3>
Instead of creating additional sample sets from the population, we create additional sample sets by re-sampling data (with replacement) from the original sample set. Each of the created sample set will follow the same data distribution of the original sample set, which in turns, follow the population.<br />
<br />
R provides a nice "bootstrap" library to do this.<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>> library(boot)
> # Generate a population
> population.weight <- rnorm(100000, 160, 60)
> # Lets say we care about the ninety percentile
> quantile(population.weight, 0.9)
90%
236.8105
> # We create our first sample set of 500 samples
> sample_set1 <- sample(population.weight, 500)
> # Here is our sample statistic of ninety percentile
> quantile(sample_set1, 0.9)
90%
232.3641
> # Notice that the sample statistics deviates from the population statistics
> # We want to estimate how big is this deviation by using bootstrapping
> # I need to define my function to compute the statistics
> ninety_percentile <- function(x, idx) {return(quantile(x[idx], 0.9))}
> # Bootstrapping will call this function many times with different idx
> boot_result <- boot(data=sample_set1, statistic=ninety_percentile, R=1000)
> boot_result
ORDINARY NONPARAMETRIC BOOTSTRAP
Call:
boot(data = sample_set1, statistic = ninety_percentile, R = 1000)
Bootstrap Statistics :
original bias std. error
t1* 232.3641 2.379859 5.43342
> plot(boot_result)
> boot.ci(boot_result, type="bca")
BOOTSTRAP CONFIDENCE INTERVAL CALCULATIONS
Based on 1000 bootstrap replicates
CALL :
boot.ci(boot.out = boot_result, type = "bca")
Intervals :
Level BCa
95% (227.2, 248.1 )
Calculations and Intervals on Original Scale
</code></pre>
<br />
Here is the visual output of the bootstrap plot<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhTP0ReoaW8gCM0w8rIcMxEXrZEm6dNBnLqXtwNseia9oGiUHYwi7GBj1Ln4QpjgzIYe91kkImvSEaujBfcNNuNEp7_DDr3zdY82Pg6z7KYpkZGT03O7d1LxHNxy7B-AyxdinntWtbVywkb/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhTP0ReoaW8gCM0w8rIcMxEXrZEm6dNBnLqXtwNseia9oGiUHYwi7GBj1Ln4QpjgzIYe91kkImvSEaujBfcNNuNEp7_DDr3zdY82Pg6z7KYpkZGT03O7d1LxHNxy7B-AyxdinntWtbVywkb/s1600/p1.png" height="225" width="400" /></a></div>
<br />
Bootstrapping is a powerful simulation technique for estimate any statistics in an empirical way. It is also non-parametric because it doesn't assume any model as well as parameters and just use the original sample set to estimate the statistics. <br />
<br />
If we assume certain distribution model want to see the distribution of certain statistics. Monte Carlo simulation provides a powerful way for this.<br />
<br />
<h3>
Monte Carlo Simulation</h3>
The idea is pretty simple, based on a particular distribution function (defined by a specific model parameters), we generate many sets of samples. We compute the statistics of each sample set and see how the statistics distributed across different sample sets.<br />
<br />
For example, given a normal distribution population, what is the probability distribution of the max value of 5 randomly chosen samples.<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>> sample_stats <- rep(0, 1000)
> for (i in 1:1000) {
+ sample_stats[i] <- max(rnorm(5))
+ }
> mean(sample_stats)
[1] 1.153008
> sd(sample_stats)
[1] 0.6584022
> par(mfrow=c(1,2))
> hist(sample_stats, breaks=30)
> qqnorm(sample_stats)
> qqline(sample_stats)
</code></pre>
<br />
Here is the distribution of the "max(5)" statistics, which shows some right skewness<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhF2x7xwwoQXKrjzcVR3K6OnErK8p_p6-Ft9I3jqHM-4dVyqpa3bjzEzixeOnPkQKJeaOgDlR-rpNF_vBvmS-06LvpyQ9eJ8RzxBs5gKms6WGwBlveKWXGbvKpfAf_7N93jTkmHeykoN7w-/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhF2x7xwwoQXKrjzcVR3K6OnErK8p_p6-Ft9I3jqHM-4dVyqpa3bjzEzixeOnPkQKJeaOgDlR-rpNF_vBvmS-06LvpyQ9eJ8RzxBs5gKms6WGwBlveKWXGbvKpfAf_7N93jTkmHeykoN7w-/s1600/p1.png" height="180" width="320" /></a></div>
<br />
Bootstrapping and Monte Carlo simulation is a powerful tool to estimate statistics in an empirical manner, especially when we don't have an analytic form of solution.Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-91774815067716755552013-12-27T14:55:00.000-08:002014-02-02T23:19:13.660-08:00Spark: Low latency, massively parallel processing frameworkWhile Hadoop fits well in most batch processing workload, and is the primary choice of big data processing today, it is not optimized for other types of workload due to its following limitation<br />
<ul>
<li>Lack of iteration support</li>
<li>High latency due to persisting intermediate data onto disk</li>
</ul>
For a more detail elaboration of the <a href="http://horicky.blogspot.com/2009/11/what-hadoop-is-good-at.html" target="_blank">Hadoop limitation</a>, refer to my <a href="http://horicky.blogspot.com/2009/11/what-hadoop-is-good-at.html" target="_blank">previous post</a>.<br />
<br />
Nevertheless, the Map/Reduce processing paradigm is a proven mechanism for dealing with large scale data. On the other hand, many of Hadoop's infrastructure piece such as HDFS, HBase has been mature over time.<br />
<br />
In this blog post, we'll look at a different architecture called Spark, which has taken the strength of Hadoop and make improvement in a number of Hadoop's weakness, and provides a more efficient batch processing framework with a much lower latency (from the benchmark result, Spark (using RAM cache) claims to be 100x faster than Hadoop, and 10x faster than Hadoop when running on disk. Although competing with Hadoop MapRed, Spark integrates well with other parts of Hadoop Ecosystem (such as HDFS, HBase ... etc.). Spark has generated a lot of excitement in the big data community and represents a very promising parallel execution stack for big data analytics. <br />
<br />
<h3>
Berkeley Spark </h3>
Within the Spark cluster, there is a driver program where the application logic execution is started, with multiple workers which processing data in parallel. Although this is not mandated, data is typically collocated with the worker and partitioned across the same set of machines within the cluster. During the execution, the driver program will passed code/closure into the worker machine where processing of corresponding partition of data will be conducted. The data will undergoing different steps of transformation while staying in the same partition as much as possible (to avoid data shuffling across machines). At the end of the execution, actions will be executed at the worker and result will be returned to the driver program.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjx-lrJxNv6NNQmjryFkFhCujYhKBgenuyY-cCfLRKzlluFIPyytw-pimfQ7Sf1Jji86A18HoTB3PKhUM6UocCjaA_nj2P2A_kIk7ALy-oUeGbfU7DHdBGwpIVcN2x-EVENwL6ZGCmj817q/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjx-lrJxNv6NNQmjryFkFhCujYhKBgenuyY-cCfLRKzlluFIPyytw-pimfQ7Sf1Jji86A18HoTB3PKhUM6UocCjaA_nj2P2A_kIk7ALy-oUeGbfU7DHdBGwpIVcN2x-EVENwL6ZGCmj817q/s320/p1.png" height="320" width="304" /></a></div>
<br />
Underlying the cluster, there is an important Distributed Data Structure called RDD (Resilient Distributed Dataset), which is a logically centralized entity but physically partitioned across multiple machines inside a cluster based on some notion of key. Controlling how different RDD are co-partitioned (with the same keys) across machines can reduce inter-machine data shuffling within a cluster. Spark provides a "partition-by" operator which create a new RDD by redistributing the data in the original RDD across machines within the cluster.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjTp3QKXkSACuXf_5cthLE-MCHD91csRCkVJAeVQC2qIj1H9sYWOqhXbrSRyrYDeMB9PUW5AxUfiUtDm0BUH3dUaYswOjY6DzBFRQGIZ_HgoEx3M286LMXIEoPPQZg193CvJqKaP-JZ_LhP/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjTp3QKXkSACuXf_5cthLE-MCHD91csRCkVJAeVQC2qIj1H9sYWOqhXbrSRyrYDeMB9PUW5AxUfiUtDm0BUH3dUaYswOjY6DzBFRQGIZ_HgoEx3M286LMXIEoPPQZg193CvJqKaP-JZ_LhP/s1600/p1.png" height="320" width="301" /></a></div>
<br />
<br />
RDD can optionally be cached in RAM and hence providing fast access. Currently the granularity of caching is done at the RDD level, either the whole or none of the RDD is cached. Cached is a hint but not a guarantee. Spark will try to cache the RDD if sufficient memory is available in the cluster, based on LRU (Least Recent Use) eviction algorithm.<br />
<br />
RDD provides an abstract data structure from which application logic can be expressed as a sequence of transformation processing, without worrying about the underlying distributed nature of the data.<br />
<br />
Typically an application logic are expressed in terms of a sequence of TRANSFORMATION and ACTION. "Transformation" specifies the processing dependency DAG among RDDs and "Action" specifies what the output will be (ie: the sink node of the DAG with no outgoing edge). The scheduler will perform a topology sort to determine the execution sequence of the DAG, tracing all the way back to the source nodes, or node that represents a cached RDD.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiu7c1pyWplZ86oCMe73dNL4EMvRa5MCr6sU0nrwiNL9w2jrzLgaiWyyDnYD4d1Ryx8MpHYe3lh0BOjBZbzqHRQ9kZAUc3W3pUqJPj6_fg6e-xfMPY0_GhjsucOEtuK2SRPCuxTQBngUDT7/s1600/P2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiu7c1pyWplZ86oCMe73dNL4EMvRa5MCr6sU0nrwiNL9w2jrzLgaiWyyDnYD4d1Ryx8MpHYe3lh0BOjBZbzqHRQ9kZAUc3W3pUqJPj6_fg6e-xfMPY0_GhjsucOEtuK2SRPCuxTQBngUDT7/s1600/P2.png" height="320" width="214" /></a></div>
<br />
Notice that dependencies in Spark come in two forms. "Narrow dependency" means the all partitions of an RDD will be consumed by a single child RDD (but a child RDD is allowed to have multiple parent RDDs). "Wide dependencies" (e.g. group-by-keys, reduce-by-keys, sort-by-keys) means a parent RDD will be splitted with elements goes to different children RDDs based on their keys. Notice that RDD with narrow dependencies preserve the key partitioning between parent and child RDD. Therefore RDD can be co-partitioned with the same keys (parent key range to be a subset of child key range) such that the processing (generating child RDD from parent RDD) can be done within a machine with no data shuffling across network. On the other hand, RDD will wide dependencies involves data shuffling.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgE8hBs2qN8jpNyjlYwpVMt0QtcfHyoCAFoH3lEfLAcyobzMQhulxHIDUbOXy84NCHKr8yRhAadBjvukSs4_oakvjjbVOF0Jfg854PfoqukALsqTs_-4oS-0pHur79Hf5l6HsSt0aTvjo6w/s1600/P3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgE8hBs2qN8jpNyjlYwpVMt0QtcfHyoCAFoH3lEfLAcyobzMQhulxHIDUbOXy84NCHKr8yRhAadBjvukSs4_oakvjjbVOF0Jfg854PfoqukALsqTs_-4oS-0pHur79Hf5l6HsSt0aTvjo6w/s1600/P3.png" height="311" width="400" /></a></div>
<br />
Narrow transformation (involves no data shuffling) includes the following operators<br />
<ul>
<li>Map</li>
<li>FlatMap</li>
<li>Filter</li>
<li>Sample </li>
</ul>
Wide transformation (involves data shuffling) includes the following operators<br />
<ul>
<li> SortByKey</li>
<li>ReduceByKey</li>
<li>GroupByKey</li>
<li>CogroupByKey</li>
<li>Join</li>
<li>Cartesian </li>
</ul>
Action output the RDD to the external world and includes the following operators<br />
<ul>
<li>Collect</li>
<li>Take(n)</li>
<li>Reduce</li>
<li>ForEach</li>
<li>Sample</li>
<li>Count</li>
<li>Save </li>
</ul>
The scheduler will examine the type of dependencies and group the narrow dependency RDD into a unit of processing called a stage. Wide dependencies will span across consecutive stages within the execution and require the number of partition of the child RDD to be explicitly specified.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgkvVrePgWM7IOdKLOCehmnqdZ1LRb3rQVaSjkwZsiNplSndGVcg7Or5C3IEw9amt0Yp1UJDSrIN01fqnQ4HC2CnNCwee6w9b3A1clJcZ6Cfeiw5e5Q3tZ9pH1A4eFIwk2xxxTohVAaM0RC/s1600/p2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgkvVrePgWM7IOdKLOCehmnqdZ1LRb3rQVaSjkwZsiNplSndGVcg7Or5C3IEw9amt0Yp1UJDSrIN01fqnQ4HC2CnNCwee6w9b3A1clJcZ6Cfeiw5e5Q3tZ9pH1A4eFIwk2xxxTohVAaM0RC/s400/p2.png" height="301" width="400" /></a></div>
<br />
A typical execution sequence is as follows ...<br />
<ol>
<li>RDD is created originally from external data sources (e.g. HDFS, Local file ... etc)</li>
<li>RDD undergoes a sequence of TRANSFORMATION (e.g. map, flatMap, filter, groupBy, join), each provide a different RDD that feed into the next transformation.</li>
<li>Finally the last step is an ACTION (e.g. count, collect, save, take), which convert the last RDD into an output to external data sources</li>
</ol>
The above sequence of processing is called a lineage (outcome of the
topological sort of the DAG). Each RDD produced within the lineage is
immutable. In fact, unless if it is cached, it is used only once to
feed the next transformation to produce the next RDD and finally produce
some action output.<br />
<br />
In a classical distributed system, fault resilience is achieved by replicating data across different machines together with a active monitoring system. In case of any machine crashes, there is always another copy of data residing in a different machine from where recovery can take place. <br />
<br />
Fault resiliency in Spark takes a different approach. First of all, as a large scale compute cluster, Spark is not meant to be a large scale data cluster at all. Spark makes two assumptions of its workload.<br />
<ul>
<li>The processing time is finite (although the longer it takes, the cost of recovery after fault will be higher)</li>
<li>Data persistence is the responsibility of external data sources, which keeps the data stable within the duration of processing.</li>
</ul>
Spark has made a tradeoff decision that in case of any data lost during the execution, it will re-execute the previous steps to recover the lost data. However, this doesn't mean everything done so far is discarded and we need to start from scratch at the beginning. We just need to re-executed the corresponding partition in the parent RDD which is responsible for generating the lost partitions, in case of narrow dependencies, this resolved to the same machine. <br />
<br />
Notice that the re-execution of lost partition is exactly the same as the lazy evaluation of the DAG, which starts from the leaf node of the DAG, tracing back the dependencies on what parent RDD is needed and then eventually track all the way to the source node. Recomputing the lost partition is done is a similar way, but taking partition as an extra piece of information to determine which parent RDD partition is needed.<br />
<br />
However, re-execution across wide dependencies can touch a lot of parent RDD across multiple machines and may cause re-execution of everything. To mitigate this, Spark persist the intermediate data output from a Map phase before it shuffle them to different machines executing the reduce phase. In case of machine crash, the re-execution (from another surviving machine) just need to trace back to fetch the intermediate data from the corresponding partition of the mapper's persisted output. Spark also provide a checkpoint API to explicitly persist intermediate RDD so re-execution (when crash) doesn't need to trace all the way back to the beginning. In future, Spark will perform check-pointing automatically by figuring out a good balance between the latency of recovery and the overhead of check-pointing based on statistical result.<br />
<br />
Spark provides a powerful processing framework for building low latency, massively parallel processing for big data analytics. It supports API around the RDD abstraction with a set of operation for transformation and action for a number of popular programming language like Scala, Java and Python.<br />
<br />
In future posts, I'll cover other technologies in the Spark stack including real-time analytics using streaming as well as machine learning frameworks.Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com1tag:blogger.com,1999:blog-7994087232040033267.post-7219286423939692132013-12-12T13:23:00.000-08:002013-12-12T13:23:24.387-08:00Escape local optimum trapOptimization is a very common technique in computer science and machine learning to search for the best (or good enough) solution. Optimization itself is a big topic and involves a wide range of mathematical techniques in different scenarios.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-HJGaxfiUktxM5d1g_WCJyZqTR4jMQ4fl18cQp-tVst0_xwF75dSNLw6z0-qBVNdOCsDwzhzx1r_c0Hk6tO67TDGTSDGxiHxuFsqjBMyFIxAJjkFbxmSbTfCC6t6g_RBatZ-tihaokrZO/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="333" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-HJGaxfiUktxM5d1g_WCJyZqTR4jMQ4fl18cQp-tVst0_xwF75dSNLw6z0-qBVNdOCsDwzhzx1r_c0Hk6tO67TDGTSDGxiHxuFsqjBMyFIxAJjkFbxmSbTfCC6t6g_RBatZ-tihaokrZO/s400/p1.png" width="400" /></a></div>
<br />
In this post, I will be focusing in local search, which is a very popular technique in searching for an optimal solution based on a series of greedy local moves. The general setting of local search is as follows ...<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>1. Define an objective function
2. Pick an initial starting point
3. Repeat
3.1 Find a neighborhood
3.2 Locate a subset of neighbors that is a candidate move
3.3 Select a candidate from the candidate set
3.4 Move to the candidate
</code></pre>
<br />
One requirement is that the optimal solution need to be reachable by a sequence of moves. Usually this requires a proof that any arbitrary state is reachable by any arbitrary state through a sequence of moves.<br />
<br />
Notice that there are many possible strategies for each steps in 3.1, 3.2, 3.3. For example, one strategy can examine all members within the neighborhood, pick the best one (in terms of the objective function) and move to that. Another strategy can randomly pick a member within the neighborhood, and move to the member if it is better than the current state.<br />
<br />
Regardless of the strategies, the general theme is to move towards the members which is improving the objective function, hence the greedy nature of this algorithm.<br />
<br />
One downside of this algorithm is that it is possible to be trapped in a local optimum, whose is the best candidate within its neighborhood, but not the best candidate from a global sense.<br />
<br />
In the following, we'll explore a couple meta-heuristic techniques that can mitigate the local optimum trap.<br />
<br />
<h3>
Multiple rounds </h3>
We basically conduct k rounds of local search, each round getting a local optimum and then pick the best one out of these k local optimum.<br />
<br />
<h3>
Simulated Anealing</h3>
This strategy involves a dynamic combination of exploitation (better neighbor) and exploration (random walk to worse neighbor). The algorithm works in the following way ...<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>1. Pick an initial starting point
2. Repeat until terminate condition
2.1 Within neighborhood, pick a random member
2.2 If neighbor is better than me
move to the neighbor
else
With chance exp(-(myObj - neighborObj)/Temp)
move to the worse neighbor
2.3 Temp = alpha * Temp
</code></pre>
<br />
<h3>
Tabu Search</h3>
This strategy maintains a list of previously visited states (called Tabu list) and make sure these states will not be re-visited in subsequent exploration. The search will keep exploring the best move but skipping the previously visited nodes. This way the algorithm will explore the path that hasn't be visited before. The search also remember the best state obtained so far.<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>1. Initialization
1.1 Pick an initial starting point S
1.2 Initial an empty Tabu list
1.3 Set the best state to S
1.4 Put S into the Tabu list
2. Repeat until terminate condition
2.1 Find a neighborhood
2.2 Locate a smaller subset that is a candidate move
2.3 Remove elements that is already in Tabu list
2.4 Select the best candidate and move there
2.5 Add the new state to the Tabu list
2.6 If the new state is better that best state
2.6.1 Set the best state to this state
2.7 If the Tabu list is too large
2.7.1 Trim Tabu list by removing old items
</code></pre>
<br />Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-59854654324442415262013-11-09T23:12:00.002-08:002013-11-09T23:18:55.613-08:00Diverse recommenderThis is a continuation of <a href="http://horicky.blogspot.com/2011/09/recommendation-engine.html" target="_blank">my previous blog in recommendation systems</a>, which describes some basic algorithm for building recommendation systems. These techniques evaluate each item against user's interest independently and pick the topK items to construct the recommendation. However, it suffers from the lack of diversity. For example, the list may contain the same book with soft cover, hard cover, and Kindle version. Since human's interests are usually diverse, a better recommendation list should contain items that covers a broad spectrum of user's interests, even though each element by itself is not the most aligned with the user's interests.<br />
<br />
In this post, I will discuss a recommendation algorithm that consider diversity in its list of recommendation.<br />
<br />
<h3>
Topic Space </h3>
First of all, lets define a "topic space" where both the content and user will be map to. Having a "topic space" is a common approach in recommendation because it can reduce dimensionality and resulting in better system performance and improved generality.<br />
<br />
The set of topics in topic space can be extracted algorithmically using Text Mining techniques such as LDA, but for simplicity here we use a manual approach to define the topic space (topics should be orthogonal to each other, as highly correlated topics can distort the measures). Lets say we have the following topics defined ...<br />
<ul>
<li>Romance</li>
<li>Sports</li>
<li>Politics</li>
<li>Weather</li>
<li>Horror</li>
<li>...</li>
</ul>
<br />
<ul>
</ul>
<h3>
Content as Vector of topic weights </h3>
Once the topic space is defined, content author can assign topic weights to each content. For example, movie can be assigned with genres and web page can be assigned with topics as well. Notice that a single content can be assigned with multiple topics of different weights. In other words, each content can be described as a vector of topic weights.<br />
<br />
<h3>
User as Vector of topic weights</h3>
On the other hand, user can also be represented as a vector of topic weights based on their interaction of content, such as viewing a movie, visiting a web page, buying a product ... etc. Such interaction can have a positive or negative effect depends on whether the user like or dislike the content. If the user like the content, the user vector will have the corresponding topic weight associated with the content increases by multiplying alpha (alpha > 1). If the user dislike the content, the corresponding topic weight will be divided by alpha. After each update, the user vector will be normalized to a unit vector.<br />
<br />
<h3>
Diversifying the recommendation</h3>
We use a utility function to model the diversity of the document and then maximize the utility function.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJ0ajI_yYCD30n9EyAGqcWZjUWAkO9LBc1207VTxOTCg_EJv20jE7AmfKG9nuB4J6QFz1KkCJgcwJikk9WOioCjFSpkST3tKbMmtFFXKRSTZcEVNhKzS5u6ATrAGT5hQ5BoiVeGDn1wDbP/s1600/p1.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="207" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJ0ajI_yYCD30n9EyAGqcWZjUWAkO9LBc1207VTxOTCg_EJv20jE7AmfKG9nuB4J6QFz1KkCJgcwJikk9WOioCjFSpkST3tKbMmtFFXKRSTZcEVNhKzS5u6ATrAGT5hQ5BoiVeGDn1wDbP/s400/p1.png" width="400" /></a></div>
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
In practice, A is not computed from the full set of documents, which is usually huge. The full set of documents is typically indexed using some kind of <a href="http://horicky.blogspot.com/2013/02/text-processing-part-2-inverted-index.html" target="_blank">Inverted index technologies</a> using the set of topics as keywords, each c[j,k] is represented as tf-idf.<br />
<br />
User is represented as a "query", and will be sent to the inverted index as a search request. Relevant documents (based on cosine distance measures w.r.t. user) will be return as candidate set D (e.g. top 200 relevant content). <br />
<br />
To pick the optimal set of A out of D, we use a greedy approach as follows ...<br />
<ol>
<li>Start with an empty set A</li>
<li>Repeat until |A| > H </li>
</ol>
<ul>
<li>Pick a doc i from D such that by adding it to the set A will maximize the utility function</li>
<li>Add doc i into A and remove doc i from D</li>
</ul>
Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-45916525391463924462013-09-07T22:11:00.002-07:002013-09-07T22:12:36.750-07:00Exploration and Exploitation"Cold Start" is a common problem happens quite frequent in recommendation system. When a new item enters, there is no prior history that the recommendation system can use. Since recommendation is an optimization engine which recommends item that matches the best with the user's interests. Without prior statistics, the new item will hardly be picked up as recommendation and hence continuously lacking the necessary statistics that the recommendation system can use.<br />
<br />
One example is movie recommendation where a movie site recommends movies to users based on their past viewing history. When a new movie arrives the market, there isn't enough viewing statistics about the movie and therefore the new movie will not have a strong match score and won't be picked as a recommendation. Because we never learn from those that we haven't recommended, the new movies will continuously not have any statistics and therefore will never be picked in future recommendations.<br />
<br />
Another cold start example is online Ad serving when a new Ad enters the Ad repository.<br />
<br />
<h3>
Multilevel Granularity Prediction</h3>
One solution of cold-start problem is to leverage existing items that are "SIMILAR" to the new item; "similarity" is based on content attributes (e.g. actors, genres). Notice that here we are using a coarser level of granularity (group of similar items) for prediction, which can be less accurate than a fine-grain model that use view statistics history for prediction.<br />
<br />
In other words, we can make recommendation based on two models of different granularity. Fine-grain model based on instance-specific history data is preferred because it usually has higher accuracy. For cold-start problem when the new items don't have history data available, we will fall back to use the coarse-grain model based on other similar items to predict user's interests on the new items.<br />
<br />
A common approach is to combine both models of different granularity using different weights where the weights depends on the confidence level of the fine-grain model. For new items, the fine-grain model will have low confidence and therefore it gives more weights to the coarse-grain model.<br />
<br />
However, in case we don't have a coarser level of granularity, or the coarse level is too coarse and doesn't give good prediction. We have to use the fine-grain model to predict. But how can we build up the instance-specific history for the fine-grain model when we are not sure if the new items are good recommendation for the user ?<br />
<br />
<h3>
Optimization under Uncertainty</h3>
The core of our problem is we need to optimize under uncertainties. We have two approaches<br />
<ol>
<li>Exploitation: Make the most optimal choice based on current data. Because of uncertainty (high variation) the current data may deviate from its true expected value, we may end up picking a non-optimal choice.</li>
<li>Exploration: Make a random choice or choices that we haven't made before. The goal is to gather more data point and reduce the uncertainty. This may waste our cycles of picking the optimal choice. </li>
</ol>
Lets start with a simple, multi-bandit problem. There are multiple
bandit
in a Casino, each Bandit has a different probability to win. If you know the true underlying winning probability of each bandit, you will
pick the one with the highest winning probability and keep playing on that one.<br />
Unfortunately, you don't know the underlying probability and has only a limited number of rounds to play. How would you choose which bandit to play to maximize the total number of rounds you win.<br />
<br />
Our strategy should strike a good balance between exploiting and exploring. To measure how good the strategy is, there is a concept of "regret", which is the ratio of the two elements<br />
<ul>
<li>Value you obtain by following Batch Optimal strategy (after you have done batch analysis and have a clear picture in the underlying probability distribution)</li>
<li>Value you obtain by following the strategy</li>
</ul>
We'll pick our strategy to do more Exploration initially when you have a lot of uncertainty, and gradually tune down the ratio of Exploration (and leverage more on Exploitation) as we collected more statistics.<br />
<br />
<h3>
Epsilon-Greedy Strategy </h3>
In the <b>"epsilon-greedy"</b> strategy, at every play we throw a dice between explore and exploit.<br />
With probability p(t) = k/t (where k is a constant and t is the number of tries so far),we pick a bandit randomly with equal chance (regardless of whether the bandit has been picked in the past). And with probability 1 - p(t), we pick the bandit that has the highest probability of win based on passed statistics.<br />
<br />
Epsilon-greedy has the desirable property of spending more time to explore initially and gradually reduce the portion as time passes. However, it doesn't have a smooth transition between explore and exploit. Also while it explores, it picks each bandit uniformly without giving more weight to the unexplored bandits. While it exploits, it doesn't consider the confidence of probability estimation.<br />
<br />
<h3>
Upper Confidence Bound: UCB</h3>
In the more sophisticated UCB strategy, each bandit is associated with an estimated mean with a confidence interval. In every play, we choose the bandit whose upper confidence bound (ie: mean + standard deviation) is the largest.<br />
<br />
Initially each bandit has a zero mean and a large confidence interval. As time goes, we estimated the mean p[i] of bandit i based on how many time it wins since we play the bandit i. We also adjust the confidence interval (reducing deviation) as we play the bandit.<br />
e.g. standard deviation is (p.(1-p)/n)^0.5<br />
<br />
Notice that the UCB model can be used in a more general online machine learning setting. We require the machine learning model be able to output its estimation based on a confidence parameter. As a concrete example, lets say a user is visiting our movie site and we want to recommend a movie to the user, based on a bunch of input features (e.g. user feature, query feature ... etc.).<br />
<br />
We can do a first round selection (based on information retrieval technique) to identify movie candidate based on relevancy (ie: user's viewing history or user search query). For each movie candidate, we can invoke the ML model to estimated interest level, as well as the 68% confidence boundary (the confidence level is arbitrary and need to be hand-tuned, 68% is roughly one standard deviation of a Gaussian distribution). We then combine them by add the 68% confidence range as an offset to its estimation and recommend the movie that has the highest resulting value.<br />
<br />
After recommendation, we monitor whether user click on it, view it ... etc. and the response will be fed back to our ML model as a new training data. Our ML model is an online learning setting and will update the model with this new training data. Over time the 68% confidence range will be reduced over time as more and more data is gathered.<br />
<br />
<h3>
Relationship with A/B Testing</h3>
For most web sites, we run experiments continuously to improve user experience by trying out different layouts, or to improve user's engagement by recommending different types of contents, or by trying out different things. In general, we have an objective function that defines what aspects we are trying to optimize, and we run different experiments through A/B testing to try out different combinations of configuration to see which one will maximize our objective function.<br />
<br />
When the number of experiments (combinations of different configuration) is small, then A/B is exploration mainly. In a typical setting, we use the old user experience as a control experiment and use the new user experience as a treatment. The goal is to test if the treatment causes any significant improvement from the control. Certain percentage of production users (typically 5 - 10%) will be directed to the new experience and we measured whether the user engagement level (say this is our objective function) has increased significantly in a statistical sense. Such splitting is typically done by hashing the user id (or browser cookies), and based on the range of the hash code falls to determine whether the user should get the new experience. This hashing is consistent (same user will hash into the same bucket in subsequent request) and so the user will get the whole new user experience when visiting the web site.<br />
<br />
When the number of experiments is large and new experiments comes out dynamically and unpredictable, traditional A/B testing model described above will not be able to keep track of all pairs of control and treatment combination. In the case, we need to use the dynamic exploration/exploitation mechanism to find out the best user experience.<br />
<br />
Using the UCB approach, we can treat each user experience as a bandit that the A/B test framework can choose from. Throughout the process, A/B test framework will explore/exploit among different user experience to optimize for the objective function. At any time, we can query the A/B testing framework to find out the latest statistics of each user experience. This provides a much better way to look at large number of experiment result at the same time. Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com1tag:blogger.com,1999:blog-7994087232040033267.post-89931775918068556902013-08-17T23:37:00.003-07:002013-08-17T23:41:49.515-07:00Six steps in data science"Data science" and "Big data" has become a very hot term in last 2 years. Since the data storage price dropped significantly, enterprises and web companies has collected huge amount of their customer's behavioral data even before figuring out how to use them. Enterprises also start realizing that these data, if use appropriately, can turn into useful insight that can guide its business along a more successful path.<br />
<br />
From my observation, the effort of data science can be categorized roughly into the following areas.<br />
<ul>
<li>Data acquisition</li>
<li>Data visualization</li>
<li>OLAP, Report generation</li>
<li>Response automation</li>
<li>Predictive analytics</li>
<li>Decision optimization</li>
</ul>
<br />
<ul>
</ul>
<h3>
Data Acquisition</h3>
Data acquisition is about collecting data into the system. This is an important step before any meaningful processing or analysis can begin. Most companies start with collecting business transaction records from their OLTP system. Typically there is an ETL (Extract/Transform/Load) process involved to ingest the raw data, clean the data and transform them appropriately. Finally, the data is loaded into a data warehouse where the subsequent data analytics exercises are performed. In today's big data world, the destination has been shifted from traditional data warehouse to Hadoop distributed file system (HDFS).<br />
<br />
<h3>
Data Visualization</h3>
Data visualization is usually the first step of analyzing the data. It is typically done by plotting data in different ways to establish give a quick sense of its shape, in order to guide the data scientist to determine what subsequent analysis should be conducted. This is also where a more experience data scientist can be distinguished from an less experienced one based on how fast they can spot common patterns or anomalies from data. Most of the plotting package works only for data that fits into one single machine. Therefore, in the big data world, data sampling is typically conducted first to reduce the data size, and then import to a single machine where R, SAS, SPSS can be used to visualized the sample data.<br />
<br />
<h3>
OLAP / Reporting </h3>
OLAP is about aggregating transaction data (e.g. revenue) along different dimensions (e.g. Month, Location, Product) where the enterprise defines its KPI/business metrics that measures the companies' performance. This can be done either in an ad/hoc manner (OLAP), or in a predefined manner (Report template). Report writer (e.g. Tableau, Microstrategy) are use to produce the reports. The data is typically stored in regular RDBMS or a multidimensional cube which is optimizing for OLAP processing (ie: slice, dice, rollup, drilldown). In the big data world, Hive provides a SQL-like access mechanism and is commonly used to access data stored in HDFS. Most popular report writers have integrated with Hive (or declare plan to integrate with it) to access big data stored in HDFS.<br />
<br />
<h3>
Response Automation</h3>
Response automation is about leveraging domain-specific knowledge to encode a set of "rules" which include event/condition/action. The system monitors all events observed, matches them against the conditions, (which can be a boolean expression of event attributes, or a sequence of event occurrence), and trigger appropriate actions. In the big data world, automating such response is typically done by stream processing mechanism (such as Flume and Storm). Notice that the "rule" need to be well-defined and unambiguous.<br />
<br />
<h3>
Predictive Analytics</h3>
Prediction is about estimating unknown data based on observed data through statistical/probabilistic approach. Depends on the data type of the output, "prediction" can be subdivided into "classification" (when the output is a category) or "regression" (when the output is a number).<br />
<br />
Prediction is typically done by first "train" a predictive model using historic data (where all input and output value is known). This training is done via an iterative process where the performance of the model in each iteration is measured at the end of each iteration. Additional input data or different model parameters will be used in next round of iteration. When the predictive performance is good enough and no significant improvement is made between subsequent iterations, the process will stop and the best model created during the process will be used.<br />
<br />
Once we have the predictive model, we can use it to predict information we haven't observed, either this is information that is hidden, or hasn't happen yet (ie: predicting future) <br />
<br />
For a more detail description of what is involved in performing predictive analytics, please refer to my following blog.<br />
<ul>
<li><a href="http://horicky.blogspot.com.au/2012/05/predictive-analytics-overview-and-data.html" target="_blank">Overview and Data visualization</a></li>
<li><a href="http://horicky.blogspot.com.au/2012/05/predictive-analytics-data-preparation.html" target="_blank">Data Preparation</a></li>
<li><a href="http://horicky.blogspot.com.au/2012/05/predictive-analytics-generalized-linear.html" target="_blank">Generalized Linear Regression</a></li>
<li><a href="http://horicky.blogspot.com.au/2012/06/predictive-analytics-neuralnet-bayesian.html" target="_blank">NeuralNet, Bayesian, SVM, KNN</a></li>
<li><a href="http://horicky.blogspot.com.au/2012/06/predictive-analytics-decision-tree-and.html" target="_blank">Decision Tree and Ensembles</a></li>
<li><a href="http://horicky.blogspot.com.au/2012/06/predictive-analytics-evaluate-model.html" target="_blank">Evaluate Model Performance</a> </li>
</ul>
<br />
<h3>
Decision Optimization</h3>
Decision optimization is about making the best decision after carefully evaluating possible options against some measure of business objectives. The business objective is defined by some "objective function" which is expressed as a mathematical formula of some "decision variables". Through various optimization technique, the system will figure out what the decision variables should be in order ro maximize (or minimize) the value of the objective function. The optimizing technique for discrete decision variables is typically done using exhaustive search, greedy/heuristic search, integer programming technique, while optimization for continuous decision variables is done using linear/quadratic programming.<br />
<br />
From my observation, "decision optimization" is the end goal of most data science effort. But "decision optimization" relies on previous effort. To obtain the overall picture (not just observed data, but also hidden or future data) at the optimization phase, we need to make use of the output of the prediction. And in order to train a good predictive model, we need to have the data acquisition to provide clean data. All these efforts are inter-linked with each other in some sense. <br />
<br />Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-65756978278964439222013-07-29T13:02:00.003-07:002013-07-29T13:11:19.023-07:00OLAP operation in ROLAP (Online Analytical Processing) is a very common way to analyze raw transaction data by aggregating along different combinations of dimensions. This is a well-established field in Business Intelligence / Reporting. In this post, I will highlight the key ideas in OLAP operation and illustrate how to do this in R.<br />
<br />
<h3>
Facts and Dimensions</h3>
The core part of OLAP is a so-called "multi-dimensional data model", which contains two types of tables; "Fact" table and "Dimension" table<br />
<br />
A Fact table contains records each describe an instance of a transaction. Each transaction records contains categorical attributes (which describes contextual aspects of the transaction, such as space, time, user) as well as numeric attributes (called "measures" which describes quantitative aspects of the transaction, such as no of items sold, dollar amount).<br />
<br />
A Dimension table contain records that further elaborates the contextual attributes, such as user profile data, location details ... etc.<br />
<br />
In a typical setting of Multi-dimensional model ...<br />
<ul>
<li>Each fact table contains foreign keys that references the primary key of multiple dimension tables. In the most simple form, it is called a STAR schema.</li>
<li>Dimension tables can contain foreign keys that references other dimensional tables. This provides a sophisticated detail breakdown of the contextual aspects. This is also called a SNOWFLAKE schema.</li>
<li>Also this is not a hard rule, Fact table tends to be independent of other Fact table and usually doesn't contain reference pointer among each other.</li>
<li>However, different Fact table usually share the same set of dimension tables. This is also called GALAXY schema.</li>
<li>But it is a hard rule that Dimension table NEVER points / references Fact table</li>
</ul>
A simple STAR schema is shown in following diagram.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiaJzT_nbzOS4qj44oAvgiPCPFO21MKSnht0_XI5nilhR60vbdHGoow2LtQnBMpNf-yji6iIbHhc9SbotJ1dvCfBB19rhCYGM8sZ3Klt8juJkFg1GKjMc_lAAAg71RpWxEKMe42Sg5N95Ih/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="285" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiaJzT_nbzOS4qj44oAvgiPCPFO21MKSnht0_XI5nilhR60vbdHGoow2LtQnBMpNf-yji6iIbHhc9SbotJ1dvCfBB19rhCYGM8sZ3Klt8juJkFg1GKjMc_lAAAg71RpWxEKMe42Sg5N95Ih/s320/p1.png" width="320" /></a></div>
<br />
Each dimension can also be hierarchical so that the analysis can be done at different degree of granularity. For example, the time dimension can be broken down into days, weeks, months, quarter and annual; Similarly, location dimension can be broken down into countries, states, cities ... etc.<br />
<br />
Here we first create a sales fact table that records each sales transaction.<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code># Setup the dimension tables
state_table <-
data.frame(key=c("CA", "NY", "WA", "ON", "QU"),
name=c("California", "new York", "Washington", "Ontario", "Quebec"),
country=c("USA", "USA", "USA", "Canada", "Canada"))
month_table <-
data.frame(key=1:12,
desc=c("Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"),
quarter=c("Q1","Q1","Q1","Q2","Q2","Q2","Q3","Q3","Q3","Q4","Q4","Q4"))
prod_table <-
data.frame(key=c("Printer", "Tablet", "Laptop"),
price=c(225, 570, 1120))
# Function to generate the Sales table
gen_sales <- function(no_of_recs) {
# Generate transaction data randomly
loc <- sample(state_table$key, no_of_recs,
replace=T, prob=c(2,2,1,1,1))
time_month <- sample(month_table$key, no_of_recs, replace=T)
time_year <- sample(c(2012, 2013), no_of_recs, replace=T)
prod <- sample(prod_table$key, no_of_recs, replace=T, prob=c(1, 3, 2))
unit <- sample(c(1,2), no_of_recs, replace=T, prob=c(10, 3))
amount <- unit*prod_table[prod,]$price
sales <- data.frame(month=time_month,
year=time_year,
loc=loc,
prod=prod,
unit=unit,
amount=amount)
# Sort the records by time order
sales <- sales[order(sales$year, sales$month),]
row.names(sales) <- NULL
return(sales)
}
# Now create the sales fact table
sales_fact <- gen_sales(500)
# Look at a few records
head(sales_fact)
month year loc prod unit amount
1 1 2012 NY Laptop 1 225
2 1 2012 CA Laptop 2 450
3 1 2012 ON Tablet 2 2240
4 1 2012 NY Tablet 1 1120
5 1 2012 NY Tablet 2 2240
6 1 2012 CA Laptop 1 225
</code></pre>
<br />
<h3>
Multi-dimensional Cube</h3>
Now, we turn this fact table into a hypercube with multiple dimensions. Each cell in the cube represents an aggregate value for a unique combination of each dimension. <br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBkg9UlMQfpUXHGuz8yyw4wdBKRFdKUljcMNFd1ziid8ngH9la0vE2HXrRIrcxrqk_X3gsb3ySwhQ4_Iy6U7ET2hD8IKFnUTXSsn7Uu67T_vjNhxbsnhIyk2436lVcLUxKv9A3sT2CUjhZ/s1600/p2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="365" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBkg9UlMQfpUXHGuz8yyw4wdBKRFdKUljcMNFd1ziid8ngH9la0vE2HXrRIrcxrqk_X3gsb3ySwhQ4_Iy6U7ET2hD8IKFnUTXSsn7Uu67T_vjNhxbsnhIyk2436lVcLUxKv9A3sT2CUjhZ/s400/p2.png" width="400" /></a></div>
<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code># Build up a cube
revenue_cube <-
tapply(sales_fact$amount,
sales_fact[,c("prod", "month", "year", "loc")],
FUN=function(x){return(sum(x))})
# Showing the cells of the cude
revenue_cube
, , year = 2012, loc = CA
month
prod 1 2 3 4 5 6 7 8 9 10 11 12
Laptop 1350 225 900 675 675 NA 675 1350 NA 1575 900 1350
Printer NA 2280 NA NA 1140 570 570 570 NA 570 1710 NA
Tablet 2240 4480 12320 3360 2240 4480 3360 3360 5600 2240 2240 3360
, , year = 2013, loc = CA
month
prod 1 2 3 4 5 6 7 8 9 10 11 12
Laptop 225 225 450 675 225 900 900 450 675 225 675 1125
Printer NA 1140 NA 1140 570 NA NA 570 NA 1140 1710 1710
Tablet 3360 3360 1120 4480 2240 1120 7840 3360 3360 1120 5600 4480
, , year = 2012, loc = NY
month
prod 1 2 3 4 5 6 7 8 9 10 11 12
Laptop 450 450 NA NA 675 450 675 NA 225 225 NA 450
Printer NA 2280 NA 2850 570 NA NA 1710 1140 NA 570 NA
Tablet 3360 13440 2240 2240 2240 5600 5600 3360 4480 3360 4480 3360
, , year = 2013, loc = NY
.....
dimnames(revenue_cube)
$prod
[1] "Laptop" "Printer" "Tablet"
$month
[1] "1" "2" "3" "4" "5" "6" "7" "8" "9" "10" "11" "12"
$year
[1] "2012" "2013"
$loc
[1] "CA" "NY" "ON" "QU" "WA"
</code></pre>
<br />
<h3>
OLAP Operations</h3>
Here are some common operations of OLAP<br />
<ul>
<li>Slice</li>
<li>Dice</li>
<li>Rollup</li>
<li>Drilldown</li>
<li>Pivot </li>
</ul>
<b>"Slice"</b> is about fixing certain dimensions to analyze the remaining dimensions. For example, we can focus in the sales happening in "2012", "Jan", or we can focus in the sales happening in "2012", "Jan", "Tablet".<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code># Slice
# cube data in Jan, 2012
revenue_cube[, "1", "2012",]
loc
prod CA NY ON QU WA
Laptop 1350 450 NA 225 225
Printer NA NA NA 1140 NA
Tablet 2240 3360 5600 1120 2240
# cube data in Jan, 2012
revenue_cube["Tablet", "1", "2012",]
CA NY ON QU WA
2240 3360 5600 1120 2240
</code></pre>
<br />
<b> "Dice"</b> is about limited each dimension to a certain range of values, while keeping the number of dimensions the same in the resulting cube. For example, we can focus in sales happening in [Jan/ Feb/Mar, Laptop/Tablet, CA/NY].<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>revenue_cube[c("Tablet","Laptop"),
c("1","2","3"),
,
c("CA","NY")]
, , year = 2012, loc = CA
month
prod 1 2 3
Tablet 2240 4480 12320
Laptop 1350 225 900
, , year = 2013, loc = CA
month
prod 1 2 3
Tablet 3360 3360 1120
Laptop 225 225 450
, , year = 2012, loc = NY
month
prod 1 2 3
Tablet 3360 13440 2240
Laptop 450 450 NA
, , year = 2013, loc = NY
month
prod 1 2 3
Tablet 3360 4480 6720
Laptop 450 NA 225
</code></pre>
<br />
<b>"Rollup"</b> is about applying an aggregation function to collapse a number of dimensions. For example, we want to focus in the annual revenue for each product and collapse the location dimension (ie: we don't care where we sold our product). <br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>apply(revenue_cube, c("year", "prod"),
FUN=function(x) {return(sum(x, na.rm=TRUE))})
prod
year Laptop Printer Tablet
2012 22275 31350 179200
2013 25200 33060 166880
</code></pre>
<br />
<b>"Drilldown"</b> is the reverse of "rollup" and applying an aggregation function to a finer level of granularity. For example, we want to focus in the annual and monthly
revenue for each product and collapse the location dimension (ie: we
don't care where we sold our product).<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>apply(revenue_cube, c("year", "month", "prod"),
FUN=function(x) {return(sum(x, na.rm=TRUE))})
, , prod = Laptop
month
year 1 2 3 4 5 6 7 8 9 10 11 12
2012 2250 2475 1575 1575 2250 1800 1575 1800 900 2250 1350 2475
2013 2250 900 1575 1575 2250 2475 2025 1800 2025 2250 3825 2250
, , prod = Printer
month
year 1 2 3 4 5 6 7 8 9 10 11 12
2012 1140 5700 570 3990 4560 2850 1140 2850 2850 1710 3420 570
2013 1140 4560 3420 4560 2850 1140 570 3420 1140 3420 3990 2850
, , prod = Tablet
month
year 1 2 3 4 5 6 7 8 9 10 11 12
2012 14560 23520 17920 12320 10080 14560 13440 15680 25760 12320 11200 7840
2013 8960 11200 10080 7840 14560 10080 29120 15680 15680 8960 12320 22400
</code></pre>
<br />
<b>"Pivot"</b> is about analyzing the combination of a pair of selected dimensions. For example, we want to analyze the revenue by year and month. Or we want to analyze the revenue by product and location.<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>apply(revenue_cube, c("year", "month"),
FUN=function(x) {return(sum(x, na.rm=TRUE))})
month
year 1 2 3 4 5 6 7 8 9 10 11 12
2012 17950 31695 20065 17885 16890 19210 16155 20330 29510 16280 15970 10885
2013 12350 16660 15075 13975 19660 13695 31715 20900 18845 14630 20135 27500
apply(revenue_cube, c("prod", "loc"),
FUN=function(x) {return(sum(x, na.rm=TRUE))})
loc
prod CA NY ON QU WA
Laptop 16425 9450 7650 7425 6525
Printer 15390 19950 7980 10830 10260
Tablet 90720 117600 45920 34720 57120
</code></pre>
<br />
I hope you can get a taste of the richness of data processing model
in R.<br />
<br />
However, since R is doing all the processing in RAM. This requires your data to be small enough so it can fit
into the local memory in a single machine. <br />
<br />Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-26134218537402767422013-02-23T00:08:00.002-08:002013-02-23T00:11:44.849-08:00Text processing (part 2): Inverted IndexThis is the second part of my text processing series. In this blog, we'll look into how text documents can be stored in a form that can be easily retrieved by a query. I'll used the popular open source Apache Lucene index for illustration.<br />
<br />
There are two main processing flow in the system ...<br />
<ul>
<li>Document indexing: Given a document, add it into the index</li>
<li>Document retrieval: Given a query, retrieve the most relevant documents from the index.</li>
</ul>
The following diagram illustrate how this is done in Lucene.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiYqO_2WjKcKemjaECzKxOJyQNXm4Ua63PvN7mnSjWyog-GFcLUoFV5PvW_u8ou69WopgdaKFXH3m04eg9p_Rl2C3UrWAorA842Ah4NEo77QFE-S7-P7pWrbktThzZAUIfO7CzpG0HBoHht/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="257" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiYqO_2WjKcKemjaECzKxOJyQNXm4Ua63PvN7mnSjWyog-GFcLUoFV5PvW_u8ou69WopgdaKFXH3m04eg9p_Rl2C3UrWAorA842Ah4NEo77QFE-S7-P7pWrbktThzZAUIfO7CzpG0HBoHht/s400/p1.png" width="400" /></a></div>
<br />
<h3>
Index Structure</h3>
Both documents and query is represented as a bag of words. In Apache Lucene, "Document" is the basic unit for storage and retrieval. A "Document" contains multiple "Fields" (also call zones). Each "Field" contains multiple "Terms" (equivalent to words).<br />
<br />
To control how the document will be indexed across its containing fields, a Field can be declared in multiple ways to specified whether it should be analyzed (a pre-processing step during index), indexed (participate in the index) or stored (in case it needs to be returned in query result). <br />
<ul>
<li>Keyword (Not analyzed, Indexed, Stored)</li>
<li>Unindexed (Not analyzed, Not indexed, Stored)</li>
<li>Unstored (Analyzed, Indexed, Not stored)</li>
<li>Text (Analyzed, Indexed, Stored) </li>
</ul>
The inverted index is a core data structure of the storage. It is organized as an inverted manner from terms to the list of documents (which contain the term). The list (known as posting list) is ordered by a global ordering (typically by document id). To enable faster retrieval, the list is not just a single list but a hierarchy of skip lists. For simplicity, we ignore the skip list in subsequent discussion.<br />
<br />
This data structure is illustration below based on Lucene's implementation. It is stored on disk as segment files which will be brought to memory during the processing.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEioeu5kyAgfty28HHX2QHNDvLZu0BSdQK1oAmSj6xIXnC2xnlt-I4uhE_X4zVGsCclKolPDKpkUL7BlsJRFE7p-S_f2x-bd0VPCHurNfdB1ojoiPKPyhmIttgNC30rOboyyJ3q3e9Vqx9SJ/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="310" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEioeu5kyAgfty28HHX2QHNDvLZu0BSdQK1oAmSj6xIXnC2xnlt-I4uhE_X4zVGsCclKolPDKpkUL7BlsJRFE7p-S_f2x-bd0VPCHurNfdB1ojoiPKPyhmIttgNC30rOboyyJ3q3e9Vqx9SJ/s400/p1.png" width="400" /></a></div>
<br />
The above diagram only shows the inverted index. The whole index contain an additional forward index as follows.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjjp0b1UTkGjXDrYnL8yVseceuJXDCJlcVpc9G-4PyFnEz2vGgERGrvv2AIDVpZufg-yQFdHj2UqvDZzRJQVP4cUHlVfn95qMSEFa9DeXGxDinqfCgSaO5BVLjHrmxIcnDovNFrnnCaywem/s1600/p2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjjp0b1UTkGjXDrYnL8yVseceuJXDCJlcVpc9G-4PyFnEz2vGgERGrvv2AIDVpZufg-yQFdHj2UqvDZzRJQVP4cUHlVfn95qMSEFa9DeXGxDinqfCgSaO5BVLjHrmxIcnDovNFrnnCaywem/s320/p2.png" width="206" /></a></div>
<br />
<br />
<h3>
Document indexing</h3>
Document in its raw form is extracted from a data adaptor. (this can be making an Web API to retrieve some text output, or crawl a web page, or receiving an HTTP document upload). This can be done in a batch or online manner.<br />
<br />
When the index processing start, it parses each raw document and analyze its text content. The typical steps includes ...<br />
<ul>
<li>Tokenize the document (breakdown into words)</li>
<li>Lowercase each word (to make it non-case-sensitive, but need to be careful with names or abbreviations)</li>
<li>Remove stop words (take out high frequency words like "the", "a", but need to careful with phrases)</li>
<li>Stemming (normalize different form of the same word, e.g. reduce "run", "running", "ran" into "run")</li>
<li>Synonym handling. This can be done in two ways. Either expand the term to include its synonyms (ie: if the term is "huge", add "gigantic" and "big"), or reduce the term to a normalized synonym (ie: if the term is "gigantic" or "huge", change it to "big")</li>
</ul>
At this point, the document is composed with multiple terms. doc = [term1, term2 ...]. Optionally, terms can be further combined into n-grams. After that we count the term frequency of this document. For example, in a bi-gram expansion, the document will become ...<br />
doc1 -> {term1: 5, term2: 8, term3: 4, term1_2: 3, term2_3:1}<br />
<br />
We may also compute a "static score" based on some measure of quality of the document. After that, we insert the document into the posting list (if it exist, otherwise create a new posting list) for each terms (all n-grams), this will create the inverted list structure as shown in previous diagram.<br />
<br />
There is a boost factor that can be set to the document or field. The boosting factor effectively multiply the term frequency which effectively affecting the importance of the document or field.<br />
<br />
Document can be added to the index in one of the following ways; inserted, modified and deleted.<br />
Typically the document will first added to the memory buffer, which is organized as an inverted index in RAM.<br />
<ul>
<li>When this is a document insertion, it goes through the normal indexing process (as I described above) to analyze the document and build an inverted list in RAM.</li>
<li>When this is a document deletion (the client request only contains the doc id), it fetches the forward index to extract the document content, then goes through the normal indexing process to analyze the document and build the inverted list. But in this case the doc object in the inverted list is labeled as "deleted".</li>
<li>When this is a document update (the client request contains the modified document), it is handled as a deletion followed by an insertion, which means the system first fetch the old document from the forward index to build an inverted list with nodes marked "deleted", and then build a new inverted list from the modified document. (e.g. If doc1 = "A B" is update to "A C", then the posting list will be {A:doc1(deleted) -> doc1, B:doc1(deleted), C:doc1}. After collapsing A, the posting list will be {A:doc1, B:doc1(deleted), C:doc1}</li>
</ul>
<br />
As more and more document are inserted into the memory buffer, it will become full and will be flushed to a segment file on disk. In the background, when M segments files have been accumulated, Lucene merges them into bigger segment files. Notice that the size of segment files at each level is exponentially increased (M, M^2, M^3). This maintains the number of segment files that need to be search per query to be at the O(logN) complexity where N is the number of documents in the index. Lucene also provide an explicit "optimize" call that merges all the segment files into one.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIGSlA8f7ZqSvoSKY3QdzCI6eR4OtwMYazNboblp8CYtfwEoe2yjWC0i8g9ofuaMkc0TlAsgkdYlsnUNX-RCO2AKt1NM1gHlVb8cCAzg9ASAOBpUstO1k7-0ihKxER5i0pTjqKdfFasb2j/s1600/p3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="213" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIGSlA8f7ZqSvoSKY3QdzCI6eR4OtwMYazNboblp8CYtfwEoe2yjWC0i8g9ofuaMkc0TlAsgkdYlsnUNX-RCO2AKt1NM1gHlVb8cCAzg9ASAOBpUstO1k7-0ihKxER5i0pTjqKdfFasb2j/s400/p3.png" width="400" /></a></div>
<br />
<br />
Here lets detail a bit on the merging process, since the posting list is already vertically ordered by terms and horizontally ordered by doc id, merging two segment files S1, S2 is basically as follows<br />
<ul>
<li>Walk the posting list from both S1 and S2 together in sorted term order. For those non-common terms (term that appears in one of S1 or S2 but not both), write out the posting list to a new segment S3.</li>
<li>Until we find a common term T, we merge the corresponding posting list from these 2 segments. Since both list are sorted by doc id, we just walk down both posting list to write out the doc object to a new posting list. When both posting lists have the same doc (which is the case when the document is updated or deleted), we pick the latest doc based on time order.</li>
<li>Finally, the doc frequency of each posting list (of the corresponding term) will be computed.</li>
</ul>
<br />
<h3>
Document retrieval</h3>
Consider a document is a vector (each term as the separated dimension and the corresponding value is the tf-idf value) and the query is also a vector. The document retrieval problem can be defined as finding the top-k most similar document that match a query, where similarity is defined as the dot-product or cosine distance between the document vector and the query vector.<br />
<br />
tf-idf is a normalized frequency. TF (term frequency) represents how many time the term appears in the document (usually a compression function such as square root or logarithm is applied). IDF is the inverse of document frequency which is used to discount the significance if that term appears in many other documents. There are many variants of TF-IDF but generally it reflects the strength of association of the document (or query) with each term.<br />
<br />
Given a query Q containing terms [t1, t2], here is how we fetch the corresponding documents. A common approach is the "document at a time approach" where we traverse the posting list of t1, t2 concurrently (as opposed to the "term at a time" approach where we traverse the whole posting list of t1 before we start the posting list of t2). The traversal process is described as follows ...<br />
<ul>
<li>For each term t1, t2 in query, we identify all the corresponding posting lists.</li>
<li>We walk each posting list concurrently to return a sequence of documents (ordered by doc id). Notice that each return document contains at least one term but can also also contain multiple terms.</li>
<li>We compute the dynamic score which is dot product of the query to document vector. Notice that we typically don't concern the TF/IDF of the query (which is short and we don't care the frequency of each term). Therefore we can just compute the sum up all the TF score of the posting list that has a match term after dividing the IDF score (at the head of each posting list). Lucene also support query level boosting where a boost factor can be attached to the query terms. The boost factor will multiply the term frequency correspondingly.</li>
<li>We also look up the static score which is purely based on the document (but not the query). The total score is a linear combination of static and dynamic score.</li>
<li>Although the score we used in above calculation is based on computing the cosine distance between the query and document, we are not restricted to that. We can plug in any similarity function that make sense to the domain. (e.g. we can use machine learning to train a model to score the similarity between a query and a document).</li>
<li>After we compute a total score, we insert the document into a heap data structure where the topK scored document is maintained.</li>
</ul>
Here the whole posting list will be traversed. In case of the posting list is very long, the response time latency will be long. Is there a way that we don't have to traverse the whole list and still be able to find the approximate top K documents ? There are a couple strategies we can consider.<br />
<ol>
<li>Static Score Posting Order: Notice that the posting list is sorted based on a global order, this global ordering provide a monotonic increasing document id during the traversal that is important to support the "document at a time" traversal because it is impossible to visit the same document again. This global ordering, however, can be quite arbitrary and doesn't have to be the document id. So we can pick the order to be based on the static score (e.g. quality indicator of the document) which is global. The idea is that we traverse the posting list in decreasing magnitude of static score, so we are more likely to visit the document with the higher total score (static + dynamic score).</li>
<li>Cut frequent terms: We do not traverse the posting list whose term has a low IDF value (ie: the term appears in many documents and therefore the posting list tends to be long). This way we avoid to traverse the long posting list.</li>
<li>TopR list: For each posting list, we create an extra posting list which contains the top R documents who has the highest TF (term frequency) in the original list. When we perform the search, we perform our search in this topR list instead of the original posting list. </li>
</ol>
<br />
Since we have multiple inverted index (in memory buffer as well as the segment files at different levels), we need to combine the result them. If termX appears in both segmentA and segmentB, then the fresher version will be picked. The fresher version is determine as follows; the segment with a lower level (smaller size) will be considered more fresh. If the two segment files are at the same level, then the one with a higher number is more fresh. On the other hand, the IDF value will be the sum of the corresponding IDF of each posting list in the segment file (the value will be slightly off if the same document has been updated, but such discrepancy is negligible). However, the processing of consolidating multiple segment files incur processing overhead in document retrieval. Lucene provide an explicit "optimize" call to merge all segment files into one single file so there is no need to look at multiple segment files during document retrieval.<br />
<br />
<h3>
Distributed Index</h3>
For large corpus (like the web documents), the index is typically distributed across multiple machines. There are two models of distribution: Term partitioning and Document partitioning.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgOfChY0wxXRqnhC3o8-W5lif3wVoRqUu1KAmm5_El8aEBqwzNSlZYof1U31M2XY7bpVpWjx4CxB9PIvtHPpnZP3KYITmmZSF9MlAEL9iuyeOaaPMVPrZbdmtyCSrcsOyf8YEzuSORrZrlt/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="178" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgOfChY0wxXRqnhC3o8-W5lif3wVoRqUu1KAmm5_El8aEBqwzNSlZYof1U31M2XY7bpVpWjx4CxB9PIvtHPpnZP3KYITmmZSF9MlAEL9iuyeOaaPMVPrZbdmtyCSrcsOyf8YEzuSORrZrlt/s400/p1.png" width="400" /></a></div>
<br />
In document partitioning, documents are randomly spread across different partitions where the index is built. In term partitioning, the terms are spread across different partitions. We'll discuss document partitioning as it is more commonly used. Distributed index is provider by other technologies that is built on Lucene, such as ElasticSearch. A typical setting is as follows ...<br />
<br />
In this setting, machines are organized as columns and rows. Each column represent a partition of documents while each row represent a replica of the whole corpus.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGxitmbgZyLX8YIQuZK3uZ5vMFL0q6RvUcYeb2b4Q_XuYWmmfGIpOj2ulEXe_L0btNCSbffuwy9HkshwC7OeyQbGT3yCTzxbluXziM9qbcoxtm3hxbyaWWiRn7WjJa6UYem7PK-QEl49RS/s1600/p2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="327" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGxitmbgZyLX8YIQuZK3uZ5vMFL0q6RvUcYeb2b4Q_XuYWmmfGIpOj2ulEXe_L0btNCSbffuwy9HkshwC7OeyQbGT3yCTzxbluXziM9qbcoxtm3hxbyaWWiRn7WjJa6UYem7PK-QEl49RS/s400/p2.png" width="400" /></a></div>
<br />
<br />
During the document indexing, first a row of the machines is randomly selected and will be allocated for building the index. When a new document crawled, a column machine from the selected row is randomly picked to host the document. The document will be sent to this machine where the index is build. The updated index will be later propagated to the other rows of replicas.<br />
<br />
During the document retrieval, first a row of replica machines is selected. The client query will then be broadcast to every column machine of the selected row. Each machine will perform the search in its local index and return the TopM elements to the query processor which will consolidate the results before sending back to client. Notice that K/P < M < K, where K is the TopK documents the client expects and P is the number of columns of machines. Notice that M is a parameter that need to be tuned.<br />
<br />
One caveat of this distributed index is that as the posting list is split horizontally across partitions, we lost the global view of the IDF value without which the machine is unable to calculate the TF-IDF score. There are two ways to mitigate that ...<br />
<ol>
<li>Do nothing: here we assume the document are evenly spread across different partitions so the local IDF represents a good ratio of the actual IDF.</li>
<li>Extra round trip: In the first round, query is broadcasted to every column which returns its local IDF. The query processor will collected all IDF response and compute the sum of the IDF. In the second round, it broadcast the query along with the IDF sum to each column of machines, which will compute the local score based on the IDF sum.</li>
</ol>
Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com3tag:blogger.com,1999:blog-7994087232040033267.post-6466834849512449602013-02-15T22:59:00.000-08:002013-02-16T17:52:01.045-08:00Text Processing (part 1) : Entity RecognitionEntity recognition is commonly used to parse unstructured text document and extract useful entity information (like location, person, brand) to construct a more useful structured representation. It is one of the most common text processing to understand a text document.<br />
<br />
I am planning to write a blog series on text processing. In this first blog of a series of basic text processing algorithm, I
will introduce some basic algorithm for entity recognition. <br />
<br />
Given the sentence: Ricky is living in CA USA.<br />
Output: Ricky/SP is/NA living/NA in/NA CA/SL USA/CL<br />
<br />
Basically we want to tag each word with the entity, whose definition is domain specific. In this example, we define the following tags<br />
<ul>
<li>NA - Not Applicable</li>
<li>SP - Start of a person name</li>
<li>CP - Continue of a person name</li>
<li>SL - Start of a location name</li>
<li>CL - Continue of a location name</li>
</ul>
<br />
<h3>
Hidden Markov Model</h3>
Lets say there is a sequence of state, lets look at multiple probabilistic graph.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwwG22YaazzVhq1WQRXJfNYZKWSrh2UqqcmlQ2HDL3srArT_y_uP-CNCpeQmhIrPi1mDycyzVEcS6aEwjhN9xP6KRwCqYNPCFXyQRKGiwkIEbw83ATjHggdZAPbaKJvVMftyMbr5iop2VG/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="292" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwwG22YaazzVhq1WQRXJfNYZKWSrh2UqqcmlQ2HDL3srArT_y_uP-CNCpeQmhIrPi1mDycyzVEcS6aEwjhN9xP6KRwCqYNPCFXyQRKGiwkIEbw83ATjHggdZAPbaKJvVMftyMbr5iop2VG/s400/p1.png" width="400" /></a></div>
<br />
<br />
However, in our tagging example, we don't directly observe the tag. Instead, we only observe the words. In this case, we can use a hidden markov model (ie: HMM).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKOf0ZOYMevROIpvideQJoJdb7XkSkidQKOd87RMAzgsPPW5nd5B8HjbautyPA_nl432H8jYxr31ZZfqFYpNDXdjsPURL0oC1_bheq_0IoKp3BFF-MfcyTTvazSWhBRmFAppAuOGvddeOf/s1600/p2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="233" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKOf0ZOYMevROIpvideQJoJdb7XkSkidQKOd87RMAzgsPPW5nd5B8HjbautyPA_nl432H8jYxr31ZZfqFYpNDXdjsPURL0oC1_bheq_0IoKp3BFF-MfcyTTvazSWhBRmFAppAuOGvddeOf/s400/p2.png" width="400" /></a></div>
<br />
<br />
Now the tagging problem can be structured as follows.<br />
<br />
Given a sequence of words, we want to predict the most likely tag sequence.<br />
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
Find a tag sequence t1, t2, ... tn that maximize the probability of P(t1, t2, .... | w1, w2 ...)<br />
<br />
Using Bayes rules,<br />
P(t1, t2, .... | w1, w2 ...) = P(t1, t2, ... tn, w1, w2, ... wn) / P(w1, w2, ... wn)<br />
<br />
Since the sequence w1, w2 ... wn is observed and constant among all tag sequence. This is equivalent to maximize P(t1, t2, ... tn, w1, w2, ... wn) which is equal to P(t1|S)*P(t2|t1)…P(E|tn)*P(w1|t1)*P(w2|t2)…<br />
<br />
Now, P(t1|S), P(t2|t1) ... can be estimated by counting the occurrence within the training data.<br />
P(t2|t1) = count(t1, t2) / count(*, t2)<br />
<br />
Similarly, P(w1|t1) = count(w1, t1) / count(*, t1)<br />
<br />
<h3>
Viterbi Algorithm</h3>
Now the problem is find a tag sequence t1, ... tn to maximize<br />
P(t1|S)*P(t2|t1)…P(E|tn)*P(w1|t1)*P(w2|t2)…<br />
<br />
A naive method is to find all possible combination of tag sequence and then evaluate the above probability. The order of complexity will be O(|T|^n) where T is the number of possible tag values. Notice that this is exponential complexity with respect to the length of the sentence.<br />
<br />
However, there is a more effective Viterbi algorithm that leverage the Markov chain properties as well as dynamic programming technique.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxqBmiyAH3GkrLJ1YrH6WqyzKaEWtowwAkL0g7QTJYCBFj2PJL6n5JJ_ucxEW3O6alOHObp2zgjUbnxwsL6PvMBmGyS2_Ra9uPQGv_kBprUhrjPMRxMUxZ5Ae0w0_BnUIjTMahgMOWtWmG/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="368" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxqBmiyAH3GkrLJ1YrH6WqyzKaEWtowwAkL0g7QTJYCBFj2PJL6n5JJ_ucxEW3O6alOHObp2zgjUbnxwsL6PvMBmGyS2_Ra9uPQGv_kBprUhrjPMRxMUxZ5Ae0w0_BnUIjTMahgMOWtWmG/s400/p1.png" width="400" /></a></div>
<br />
<br />
The key element is M(k, L) which indicates the max probability of any length k sequence that ends at tk = L. On the other hand, M(k, L) is computed by looking back different choices of S of the length k-1 sequence, and pick the one that gives the maximum M(k-1, S)*P(tk=L | tk-1=S)*P(wk|tk=L). The complexity of this algorithm is O(n*|T|^2).<br />
<br />
To find the actual tag sequence, we also maintain a back pointer from every cell to S which leads to the cell. Then we can trace back the path from the max cell M(n, STOP) where STOP is the end of sentence. <br />
<br />
Notice that for some rare words that is not observed from the training data, P(wk|tk=L) will be zero and cause the whole term to be zero. Such words can be numbers, dates. One way to solve this problem is to group these rare words into patterns (e.g. 3 digits, year2012 ... etc) and then compute P(group(wk) | tk=L). However, such grouping is domain specific and has to be hand-tuned.<br />
<br />
<h3>
Reference</h3>
<a href="https://class.coursera.org/nlangp-001/class/index" target="_blank">NLP course from Michael Collins of Columbia Unversity</a> Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com1tag:blogger.com,1999:blog-7994087232040033267.post-79677165415870048282013-02-12T07:57:00.000-08:002013-02-12T07:57:21.987-08:00Basic Planning AlgorithmYou can think of planning as a graph search problem where each node
in the graph represents a possible "state" of the reality. A directed
edge from nodeA to nodeB representing an "action" is available to
transition stateA to stateB.<br /><br />Planning can be thought of as another form of a <a href="http://horicky.blogspot.com/2013/01/optimization-in-r.html" target="_blank">constraint optimization problem which is quite different from the one I described in my last blog</a>.
In this case, the constraint is the goal state we want to achieve,
where a sequence of actions needs to be found to meet the constraint.
The sequence of actions will incur cost and our objective is to minimize
the cost associated with our chosen actions<br /><br />
<h3>
Basic Concepts </h3>
A "domain" defined the structure of the problem.<br /><ul>
<li>A set of object types. e.g. ObjectTypeX, ObjectTypeY ... etc.</li>
<li>A set of relation types e.g. [ObjectTypeX RelationTypeA ObjectTypeY] or [ObjectTypeX RelationTypeA ValueTypeY]</li>
</ul>
A "state" is composed of a set of relation instances, It can either be a "reality state" or a "required state".<br /><br />A
reality state contains tuples of +ve atoms. e.g. [(personX in
locationA), (personX is male)]. Notice that -ve atoms will not exist in
reality state. e.g. If personX is NOT in locationB, such tuple will
just not show up in the state.<br /><br />A required state contains both +ve
and -ve atoms. e.g. [(personX in locationA), NOT(personX is male)]
The required state is used to check against the reality state. The
required state is reached if all of the following is true.<br /><ul>
<li>All +ve atoms in the required state is contained in the +ve atoms of the reality state</li>
<li>None of the -ve atoms in the required state is contained in the +ve atoms of the reality state</li>
</ul>
Notice that there can be huge (or even <a href="http://txt.couchware.com/medias/jump?hid=2887&cid=475&mid=995" target="">infinite</a>)
number of nodes and edges in the graph if we are to expand the whole
graph (with all possible states and possible actions). Normally we will
expressed only a subset of nodes and edges in an analytical way.
Instead of enumerating all possible states, we describe the state as a
set of relations that we care, in particular we describe the initial
state of the environment with all the things we observed and the goal
state as what we want to reach. Similarity, we are not enumerate every
possible edges, instead we describe actions with variables such that it
describe rules that can transition multiple situations of states.<br /><br /><br />An
"action" causes transition from one state to the other. It is defined
as action(variable1, variable2 ...) and contains the following
components.<br /><ul>
<li>Pre-conditions: a required state containing a set
of tuples (expressed by variables). The action is feasible if the
current reality state contains all the +ve atoms but not any -ve atoms
specified in the pre-conditions.</li>
<li>Effects: A set of +ve atoms and
-ve atoms (also expressed by variables). After the action is taken, it
removes all the -ve atoms from the current reality state and then
insert all the +ve atoms into the current reality state.</li>
<li>Cost of executing this actio.</li>
</ul>
Notice
that since actions contains variables but the reality state does not,
therefore before an action can be execution, we need to bind the
variables in the pre-conditions to a specific value such that it will
match the current reality state. This binding will propagate to the
variable in the effects of the actions and new atoms will be insert /
removed from the reality state.<br /><br /><h3>
Planning Algorithm</h3>
This
can be think of a Search problem. Given an initial state and a goal
state, our objective is to search for a sequence of actions such that
the goal state is reached.<br /><br /><br /><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEha46fRW72bcQkMtCnRYVY-XmZX2278YTkEgS_7KNtjXgYH1U_mbHqm-L9iK431tbnsjaxn4uMXioYd-iV3l5nO8QC2DCpHHKHjfAtryBzZopkL0V2FX6mRfftAn61DWUYdXHV87uyiel_i/s1600/p1.png"><img border="0" height="235" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEha46fRW72bcQkMtCnRYVY-XmZX2278YTkEgS_7KNtjXgYH1U_mbHqm-L9iK431tbnsjaxn4uMXioYd-iV3l5nO8QC2DCpHHKHjfAtryBzZopkL0V2FX6mRfftAn61DWUYdXHV87uyiel_i/s400/p1.png" width="400" /></a><br />We
can perform the search from the initial state, expand all the possible
states that can be reached by taking some actions, and check during this
process whether the goal state has been reached. If so, terminate the
process and return the path.<br /><br />Forward planning build the plan from the initial state. It works as follows ...<br /><ol>
<li>Put the initial state into the exploration queue, with an empty path.</li>
<li>Pick
a state (together with its path from initial state) from the
exploration queue as the current state according to some heuristics.</li>
<li>If
this current state is the goal state, then return its path that
contains the sequence of action and we are done. Else move on.</li>
<li>For
this current state, explore which action is possible by seeing whether
the current state meet the pre-conditions (ie: contains all +ve and no
-ve state specified in the action pre-conditions).</li>
<li>If the action
is feasible, compute the next reachable state, and the path (by adding
this action to the original path), insert the next state into the
exploration queue.</li>
<li>Repeat 5 for all feasible actions of current state.</li>
</ol>
<br />Alternatively,
we can perform the search from the goal state. We looked at what need
to be accomplished and identify what possible actions can accomplish
that (ie: the effect of the action meets the goal state). Then we
looked at whether those actions are feasible (ie: the initial state
meets the action's pre-conditions). If so we can execute the action,
otherwise we take the action's pre-conditions as our sub-goal and expand
our over goal state.<br /><br />Backward planning build the plan from the goal state. It works as follows ...<br /><ol>
<li>Put the goal state into the exploration queue, with an empty path.</li>
<li>Pick
a regression state (a state that can reach the goal state, can be
considered as a sub-goal) from the exploration queue according to some
heuristics.</li>
<li>If the regression state is contained in initial state, then we are done and return the path as the plan. Else move on.</li>
<li>From
this regression state, identify all "relevant actions"; those actions
who has some +ve effect is contained in the regression state; and all of
its +ve effect is not overlap with the -ve regression state; and all of
its -ve effect is not overlap with the +ve regression state.</li>
<li>If
the action is relevant, compute the next regression state by removing
the action effect from the current regression state and adding the
action pre-conditions into the current regression state, insert the next
regression state into the exploration queue.</li>
<li>Repeat 5 from all relevant actions of current regression state.</li>
</ol>
<br /><h3>
Heuristic Function</h3>
In above algorithms, to pick the next candidate from the exploration queue. We can employ many strategies.<br /><ul>
<li>If we pick the oldest element in the queue, this is a breathe-first search</li>
<li>If we pick the youngest element in the queue, this is a depth-first search</li>
<li>We can pick the best element in the queue based on some value function.</li>
</ul>
Notice
that what is "best" is very subjective and is also domain specific. A
very popular approach is using the A* search whose value function =
g(thisState) + h(thisState).<br /><br />Notice that g(thisState) is the
accumulative cost to move from initial state to "thisState", while
h(thisState) is a domain-specific function that estimate the cost from
"thisState" to the goal state. It can be proved that in order for A*
search to return an optimal solution (ie: the least cost path), the
chosen h(state) function must not over-estimate (ie: need to
underestimate) the actual cost to move from "thisState" to the goal
state.<br /><br /><a href="http://horicky.blogspot.com/2008/01/search.html" target="_blank">Here is some detail of A* search.</a>Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com0tag:blogger.com,1999:blog-7994087232040033267.post-88539166778078121152013-01-14T00:10:00.000-08:002013-01-14T00:10:31.165-08:00Optimization in ROptimization is a very common problem in data analytics. Given a set of variables (which one has control), how to pick the right value such that the benefit is maximized. More formally, optimization is about determining a set of variables x1, x2, … that maximize or minimize an objective function f(x1, x2, …).<br />
<br />
<h3>
Unconstrained optimization</h3>
In an unconstraint case, the variable can be freely selected within its full range.<br />
<br />
A typical solution is to compute the gradient vector of the objective function [∂f/∂x1, ∂f/∂x2, …] and set it to [0, 0, …]. Solve this equation and output the result x1, x2 … which will give the local maximum.<br />
<br />
In R, this can be done by a numerical analysis method.<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>> f <- function(x){(x[1] - 5)^2 + (x[2] - 6)^2}
> initial_x <- c(10, 11)
> x_optimal <- optim(initial_x, f, method="CG")
> x_min <- x_optimal$par
> x_min
[1] 5 6
</code></pre>
<br />
<h3>
Equality constraint optimization</h3>
Moving onto the constrained case, lets say x1, x2 … are not independent and then have to related to each other in some particular way: g1(x1, x2, …) = 0, g2(x1, x2, …) = 0.<br />
<br />
The optimization problem can be expressed as …<br />
Maximize objective function: <i><b>f(x1, x2, …)</b></i><br />
Subjected to equality constraints:<br />
<ul>
<li><i><b>g1(x1, x2, …) = 0</b></i></li>
<li><i><b>g2(x1, x2, …) = 0</b></i></li>
</ul>
A typical solution is to turn the constraint optimization problem into an unconstrained optimization problem using Lagrange multipliers.<br />
<br />
Define a new function F as follows ...<br />
F(x1, x2, …, λ1, λ2, …) = f(x1, x2, …) + λ1.g1(x1, x2, …) + λ2.g2(x1, x2, …) + …<br />
<br />
Then solve for ...<br />
[∂F/∂x1, ∂F/∂x2, …, ∂F/∂λ1, ∂F/∂λ2, …] = [0, 0, ….]<br />
<br />
<h3>
Inequality constraint optimization</h3>
In this case, the constraint is inequality. We cannot use the Lagrange multiplier technique because it requires equality constraint. There is no general solution for arbitrary inequality constraints.<br />
<br />
However, we can put some restriction in the form of constraint. In the following, we study two models where constraint is restricted to be a linear function of the variables:<br />
w1.x1 + w2.x2 + … >= 0<br />
<br />
<h3>
Linear Programming</h3>
Linear programming is a model where both the objective function and constraint function is restricted as linear combination of variables. The Linear Programming problem can be defined as follows ...<br />
<br />
Maximize objective function: <i><b>f(x1, x2) = c1.x1 + c2.x2</b></i><br />
<br />
Subjected to inequality constraints:<br />
<ul>
<li><i><b>a11.x1 + a12.x2 <= b1</b></i></li>
<li><i><b>a21.x1 + a22.x2 <= b2</b></i></li>
<li><i><b>a31.x1 + a32.x2 <= b3</b></i></li>
<li><i><b>x1 >= 0, x2 >=0</b></i></li>
</ul>
As an illustrative example, lets walkthrough a portfolio investment problem. In the example, we want to find an optimal way to allocate the proportion of asset in our investment portfolio.<br />
<ul>
<li>StockA gives 5% return on average</li>
<li>StockB gives 4% return on average</li>
<li>StockC gives 6% return on average</li>
</ul>
To set some constraints, lets say my investment in C must be less than sum of A, B. Also, investment in A cannot be more than twice of B. Finally, at least 10% of investment in each stock.<br />
<br />
To formulate this problem:<br />
<br />
Variable: x1 = % investment in A, x2 = % in B, x3 = % in C<br />
<br />
Maximize expected return: <i><b>f(x1, x2, x3) = x1*5% + x2*4% + x3*6%</b></i><br />
<br />
Subjected to constraints:<br />
<ul>
<li><i><b>10% < x1, x2, x3 < 100%</b></i></li>
<li><i><b>x1 + x2 + x3 = 1</b></i></li>
<li><i><b>x3 < x1 + x2</b></i></li>
<li><i><b>x1 < 2 * x2</b></i></li>
</ul>
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>> library(lpSolve)
> library(lpSolveAPI)
> # Set the number of vars
> model <- make.lp(0, 3)
> # Define the object function: for Minimize, use -ve
> set.objfn(model, c(-0.05, -0.04, -0.06))
> # Add the constraints
> add.constraint(model, c(1, 1, 1), "=", 1)
> add.constraint(model, c(1, 1, -1), ">", 0)
> add.constraint(model, c(1, -2, 0), "<", 0)
> # Set the upper and lower bounds
> set.bounds(model, lower=c(0.1, 0.1, 0.1), upper=c(1, 1, 1))
> # Compute the optimized model
> solve(model)
[1] 0
> # Get the value of the optimized parameters
> get.variables(model)
[1] 0.3333333 0.1666667 0.5000000
> # Get the value of the objective function
> get.objective(model)
[1] -0.05333333
> # Get the value of the constraint
> get.constraints(model)
[1] 1 0 0
</code></pre>
<br />
<h3>
Quadratic Programming</h3>
Quadratic programming is a model where both the objective function is a quadratic function (contains up to two term products) while
constraint function is restricted as linear combination of variables.<br />
<br />
The Quadratic Programming problem can be defined as follows ...<br />
<br />
Minimize quadratic objective function:<br />
<i><b>f(x1, x2) = c1.x12 + c2. x1x2 + c2.x22 - (d1. x1 + d2.x2) </b></i><br />
Subject to constraints<br />
<ul>
<li><i><b>a11.x1 + a12.x2 == b1</b></i></li>
<li><i><b>a21.x1 + a22.x2 == b2</b></i></li>
<li><i><b>a31.x1 + a32.x2 >= b3</b></i></li>
<li><i><b>a41.x1 + a42.x2 >= b4</b></i></li>
<li><i><b>a51.x1 + a52.x2 >= b5</b></i></li>
</ul>
Express the problem in Matrix form:<br />
<br />
Minimize objective <i><b>½(DTx) - dTx</b></i><br />
Subject to constraint <b><i>ATx >= b</i></b><br />
First k columns of A is equality constraint<br />
<br />
As an illustrative example, lets continue on the portfolio investment
problem. In the example, we want to find an optimal way to allocate the
proportion of asset in our investment portfolio.<br />
<ul>
<li>StockA gives 5% return on average</li>
<li>StockB gives 4% return on average</li>
<li>StockC gives 6% return on average</li>
</ul>
We also look into the variance of each stock (known as risk) as well as the covariance between stocks.<br />
<br />
For investment, we not only want to have a high expected return, but also a low variance. In other words, stocks with high return but also high variance is not very attractive. Therefore, maximize the expected return and minimize the variance is the typical investment strategy.<br />
<br />
One way to minimize variance is to pick multiple stocks (in a portfolio) to diversify the investment. Diversification happens when the stock components within the portfolio moves from their average in different direction (hence the variance is reduced).<br />
<br />
The Covariance matrix ∑ (between each pairs of stocks) is given as follows:<br />
1%, 0.2%, 0.5%<br />
0.2%, 0.8%, 0.6%<br />
0.5%, 0.6%, 1.2%<br />
<br />
In this example, we want to achieve a overall return of at least 5.2% of return while minimizing the variance of return<br />
<br />
To formulate the problem:<br />
<br />
Variable: x1 = % investment in A, x2 = % in B, x3 = % in C<br />
<br />
Minimize variance: <i><b>xT∑x</b></i><br />
<br />
Subjected to constraint:<br />
<ul>
<li><i><b>x1 + x2 + x3 == 1</b></i></li>
<li><i><b>X1*5% + x2*4% + x3*6% >= 5.2%</b></i></li>
<li><i><b>0% < x1, x2, x3 < 100%</b></i></li>
</ul>
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>> library(quadprog)
> mu_return_vector <- c(0.05, 0.04, 0.06)
> sigma <- matrix(c(0.01, 0.002, 0.005,
+ 0.002, 0.008, 0.006,
+ 0.005, 0.006, 0.012),
+ nrow=3, ncol=3)
> D.Matrix <- 2*sigma
> d.Vector <- rep(0, 3)
> A.Equality <- matrix(c(1,1,1), ncol=1)
> A.Matrix <- cbind(A.Equality, mu_return_vector,
diag(3))
> b.Vector <- c(1, 0.052, rep(0, 3))
> out <- solve.QP(Dmat=D.Matrix, dvec=d.Vector,
Amat=A.Matrix, bvec=b.Vector,
meq=1)
> out$solution
[1] 0.4 0.2 0.4
> out$value
[1] 0.00672
>
</code></pre>
<br />
<h3>
Integration with Predictive Analytics</h3>
Optimization is usually integrated with predictive analytics, which is another important part of data analytics. For an overview of <a href="https://www.kaggle.com/wiki/Tutorials" target="_blank">predictive analytics</a>, here is <a href="http://horicky.blogspot.com.au/2012/05/predictive-analytics-overview-and-data.html" target="_blank">my previous blog</a> about it.<br />
<br />
The overall processing can be depicted as follows:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgr0atak4BvkFS6muvBxJX7e4491Z3I5BRid5W9rnDD9shavoIYL1lyPbFPL4Gg8UP2PjzQOitpYYwtwzLniKIc9sdL8aVNaGC9MS0C2G_EIqcYEeIKV9HJRKO129tR3r_zyITJsLGBwnJ9/s1600/p1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="238" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgr0atak4BvkFS6muvBxJX7e4491Z3I5BRid5W9rnDD9shavoIYL1lyPbFPL4Gg8UP2PjzQOitpYYwtwzLniKIc9sdL8aVNaGC9MS0C2G_EIqcYEeIKV9HJRKO129tR3r_zyITJsLGBwnJ9/s400/p1.png" width="400" /></a></div>
<br />
In this diagram, we use machine learning to train a predictive model in batch mode. Once the predictive model is available, observation data is fed into it at real time and a set of output variables is predicted. Such output variable will be fed into the optimization model as the environment parameters (e.g. return of each stock, covariance ... etc.) from which a set of optimal decision variable is recommended. <br />
<br />Ricky Hohttp://www.blogger.com/profile/03793674536997651667noreply@blogger.com2