You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@stratos.apache.org by Lahiru Sandaruwan <la...@wso2.com> on 2014/11/11 11:28:53 UTC
[Autoscaling] [Improvement] Introducing "curve fitting" for stat
prediction algorithm of Autoscaler
Hi all,
This contains the content i already sent to Stratos dev. Idea is to
highlight and separate the new improvement.
*Current implementation*
Currently CEP calculates average, gradient, and second derivative and send
those values to Autoscaler. Then Autoscaler predicts the values using S =
u*t + 0.5*a*t*t.
In this method CEP calculation is not very much accurate as it does not
consider all the events when calculating the gradient and second
derivative. Therefore the equation we apply doesn't yield the best
prediction.
*Proposed Implementation*
*CEP's task*
I think best approach is to do "curve fitting"[1] for received event sample
in a particular time window. Refer "Locally weighted linear regression"
section at [2] for more details.
We would need a second degree polynomial fitter for this, where we can use
Apache commons math library for this. Refer the sample at [3], we can run
this with any degree. e.g. 2, 3. Just increase the degree to increase the
accuracy.
E.g.
So if get degree 2 polynomial fitter, we will have an equation like below
where value(v) is our statistic value and time(t) is the time of event.
Equation we get from received events,
v = a*t*t + b*t + c
So the solution is,
- Find memberwise curves that fits events received in specific
window(say 10 minutes) at CEP
- Send the parameters of fitted line(a, b, and c in above equation) with
the timestamp of last event(T) in the window, to Autoscaler
*Autoscaler's task*
- Autoscaler use *v = a*t*t + b*t + c *function to predict the value in
any timestamp from the last timestamp
E.g. Say we need to find the value(v) after 1 minute(assuming we carried
all the calculations in milliseconds),
v = a * (T+60000) * (T+60000) + b * (T+60000) + c
- So we have memberwise predictions and we can find clusterwise
prediction by averaging all the memberwise values.
Please send your thoughts.
Thanks.
[1] http://en.wikipedia.org/wiki/Curve_fitting
[2] http://cs229.stanford.edu/notes/cs229-notes1.pdf
[3] http://commons.apache.org/proper/commons-math/userguide/fitting.html
--
--
Lahiru Sandaruwan
Committer and PMC member, Apache Stratos,
Senior Software Engineer,
WSO2 Inc., http://wso2.com
lean.enterprise.middleware
email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
Re: [Autoscaling] [Improvement] Introducing "curve fitting" for stat
prediction algorithm of Autoscaler
Posted by Seshika Fernando <se...@wso2.com>.
Hi Lahiru,
svn location of the decaying window can be found in this jira -
https://wso2.org/jira/browse/CEP-968
seshika
On Tue, Nov 11, 2014 at 10:10 PM, Lahiru Sandaruwan <la...@wso2.com>
wrote:
> This is cool Lasantha!
>
> I will definitely evaluate/study this and come back.
>
> On Tue, Nov 11, 2014 at 8:51 PM, Lasantha Fernando <lasantha.fdo@gmail.com
> > wrote:
>
>> Hi Lahiru,
>>
>> Would it be possible to use linear regression already available as
>> Siddhi extensions in [1] or maybe improve on that existing extensions
>> to extend it to fit polynomial curves? The code is available here [2].
>>
>> I think forecasting is also available which can be useful in this
>> usecase. WDYT? Just sharing my 2 cents.. :-)
>>
>> [1] http://mail.wso2.org/mailarchive/architecture/2014-March/015696.html
>> [2]
>> https://github.com/wso2-dev/siddhi/tree/master/modules/siddhi-extensions
>>
>> Thanks,
>> Lasantha
>>
>> On Tue, Nov 11, 2014 at 3:58 PM, Lahiru Sandaruwan <la...@wso2.com>
>> wrote:
>> > Hi all,
>> >
>> > This contains the content i already sent to Stratos dev. Idea is to
>> > highlight and separate the new improvement.
>> >
>> > Current implementation
>> >
>> > Currently CEP calculates average, gradient, and second derivative and
>> send
>> > those values to Autoscaler. Then Autoscaler predicts the values using S
>> =
>> > u*t + 0.5*a*t*t.
>> >
>> > In this method CEP calculation is not very much accurate as it does not
>> > consider all the events when calculating the gradient and second
>> derivative.
>> > Therefore the equation we apply doesn't yield the best prediction.
>> >
>> > Proposed Implementation
>> >
>> > CEP's task
>> >
>> > I think best approach is to do "curve fitting"[1] for received event
>> sample
>> > in a particular time window. Refer "Locally weighted linear regression"
>> > section at [2] for more details.
>> >
>> > We would need a second degree polynomial fitter for this, where we can
>> use
>> > Apache commons math library for this. Refer the sample at [3], we can
>> run
>> > this with any degree. e.g. 2, 3. Just increase the degree to increase
>> the
>> > accuracy.
>> >
>> > E.g.
>> > So if get degree 2 polynomial fitter, we will have an equation like
>> below
>> > where value(v) is our statistic value and time(t) is the time of event.
>> >
>> > Equation we get from received events,
>> > v = a*t*t + b*t + c
>> >
>> > So the solution is,
>> >
>> > Find memberwise curves that fits events received in specific window(say
>> 10
>> > minutes) at CEP
>> > Send the parameters of fitted line(a, b, and c in above equation) with
>> the
>> > timestamp of last event(T) in the window, to Autoscaler
>> >
>> > Autoscaler's task
>> >
>> > Autoscaler use v = a*t*t + b*t + c function to predict the value in any
>> > timestamp from the last timestamp
>> >
>> > E.g. Say we need to find the value(v) after 1 minute(assuming we
>> carried all
>> > the calculations in milliseconds),
>> >
>> > v = a * (T+60000) * (T+60000) + b * (T+60000) + c
>> >
>> > So we have memberwise predictions and we can find clusterwise
>> prediction by
>> > averaging all the memberwise values.
>> >
>> >
>> > Please send your thoughts.
>> >
>> > Thanks.
>> >
>> > [1] http://en.wikipedia.org/wiki/Curve_fitting
>> > [2] http://cs229.stanford.edu/notes/cs229-notes1.pdf
>> > [3]
>> http://commons.apache.org/proper/commons-math/userguide/fitting.html
>> >
>> >
>> > --
>> > --
>> > Lahiru Sandaruwan
>> > Committer and PMC member, Apache Stratos,
>> > Senior Software Engineer,
>> > WSO2 Inc., http://wso2.com
>> > lean.enterprise.middleware
>> >
>> > email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
>> > linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>> >
>>
>
>
>
> --
> --
> Lahiru Sandaruwan
> Committer and PMC member, Apache Stratos,
> Senior Software Engineer,
> WSO2 Inc., http://wso2.com
> lean.enterprise.middleware
>
> email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
> linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>
>
Re: [Autoscaling] [Improvement] Introducing "curve fitting" for stat
prediction algorithm of Autoscaler
Posted by Lahiru Sandaruwan <la...@wso2.com>.
This is cool Lasantha!
I will definitely evaluate/study this and come back.
On Tue, Nov 11, 2014 at 8:51 PM, Lasantha Fernando <la...@gmail.com>
wrote:
> Hi Lahiru,
>
> Would it be possible to use linear regression already available as
> Siddhi extensions in [1] or maybe improve on that existing extensions
> to extend it to fit polynomial curves? The code is available here [2].
>
> I think forecasting is also available which can be useful in this
> usecase. WDYT? Just sharing my 2 cents.. :-)
>
> [1] http://mail.wso2.org/mailarchive/architecture/2014-March/015696.html
> [2]
> https://github.com/wso2-dev/siddhi/tree/master/modules/siddhi-extensions
>
> Thanks,
> Lasantha
>
> On Tue, Nov 11, 2014 at 3:58 PM, Lahiru Sandaruwan <la...@wso2.com>
> wrote:
> > Hi all,
> >
> > This contains the content i already sent to Stratos dev. Idea is to
> > highlight and separate the new improvement.
> >
> > Current implementation
> >
> > Currently CEP calculates average, gradient, and second derivative and
> send
> > those values to Autoscaler. Then Autoscaler predicts the values using S =
> > u*t + 0.5*a*t*t.
> >
> > In this method CEP calculation is not very much accurate as it does not
> > consider all the events when calculating the gradient and second
> derivative.
> > Therefore the equation we apply doesn't yield the best prediction.
> >
> > Proposed Implementation
> >
> > CEP's task
> >
> > I think best approach is to do "curve fitting"[1] for received event
> sample
> > in a particular time window. Refer "Locally weighted linear regression"
> > section at [2] for more details.
> >
> > We would need a second degree polynomial fitter for this, where we can
> use
> > Apache commons math library for this. Refer the sample at [3], we can run
> > this with any degree. e.g. 2, 3. Just increase the degree to increase the
> > accuracy.
> >
> > E.g.
> > So if get degree 2 polynomial fitter, we will have an equation like below
> > where value(v) is our statistic value and time(t) is the time of event.
> >
> > Equation we get from received events,
> > v = a*t*t + b*t + c
> >
> > So the solution is,
> >
> > Find memberwise curves that fits events received in specific window(say
> 10
> > minutes) at CEP
> > Send the parameters of fitted line(a, b, and c in above equation) with
> the
> > timestamp of last event(T) in the window, to Autoscaler
> >
> > Autoscaler's task
> >
> > Autoscaler use v = a*t*t + b*t + c function to predict the value in any
> > timestamp from the last timestamp
> >
> > E.g. Say we need to find the value(v) after 1 minute(assuming we carried
> all
> > the calculations in milliseconds),
> >
> > v = a * (T+60000) * (T+60000) + b * (T+60000) + c
> >
> > So we have memberwise predictions and we can find clusterwise prediction
> by
> > averaging all the memberwise values.
> >
> >
> > Please send your thoughts.
> >
> > Thanks.
> >
> > [1] http://en.wikipedia.org/wiki/Curve_fitting
> > [2] http://cs229.stanford.edu/notes/cs229-notes1.pdf
> > [3] http://commons.apache.org/proper/commons-math/userguide/fitting.html
> >
> >
> > --
> > --
> > Lahiru Sandaruwan
> > Committer and PMC member, Apache Stratos,
> > Senior Software Engineer,
> > WSO2 Inc., http://wso2.com
> > lean.enterprise.middleware
> >
> > email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
> > linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
> >
>
--
--
Lahiru Sandaruwan
Committer and PMC member, Apache Stratos,
Senior Software Engineer,
WSO2 Inc., http://wso2.com
lean.enterprise.middleware
email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
Re: [Autoscaling] [Improvement] Introducing "curve fitting" for stat
prediction algorithm of Autoscaler
Posted by Seshika Fernando <se...@wso2.com>.
Hi Lahiru,
My comments below.
On Tue, Nov 11, 2014 at 11:30 PM, Lahiru Sandaruwan <la...@wso2.com>
wrote:
> Also this is a good read to learn how Netflix use these algorithms for
> scaling.
>
> http://techblog.netflix.com/search/label/prediction
>
> On Tue, Nov 11, 2014 at 11:07 PM, Lahiru Sandaruwan <la...@wso2.com>
> wrote:
>
>> Hi Seshika,
>>
>> Thanks for the detailed response,
>>
>> On Tue, Nov 11, 2014 at 10:08 PM, Seshika Fernando <se...@wso2.com>
>> wrote:
>>
>>> Hi all,
>>>
>>> I have 2 comments.
>>>
>>> a. The timeseries extension to CEP which supports uni-variate and
>>> multi-variate linear regression [1] can be used for this. We can use the
>>> multi-variate regression to solve the curve fitting stated in Lahiru's
>>> email. Basically what we need to do is use *t *and *t^2* as x1 and x2.
>>> There by if we run linear regression we get a,b,c such that V=a+b*t+c*t^2.
>>>
>>
>> Nice to see this exists in CEP already :)
>>
>> +1 for using multi-variate regression to the curve fitting. Is it
>> available in CEP 3.1.0? or can we plug it to 3.1.0?
>>
>
> Its not available in CEP3.1.0, but since its an extension it can be easily
>> plugged in.
>>
>>
>>> As Lasantha has mentioned we do have a forecasting facility as well, but
>>> currently it only works for uni-variate regression, which is not the case
>>> here. But if you really need it I might be able to extend it for this
>>> use-case, for the moment. You can still use the existing regression
>>> facility to determine the coefficients and do the forecasting yourself
>>> (which is just plugging those values in to the above equation, with the
>>> relevant t values.
>>> Let me also just mention, that even though the function is 'linear'
>>> regression, we can use linear regression to fit polynomial curves as long
>>> as we know the degree of the polynomial function (which in this case we do).
>>>
>>>
>> In Stratos case, i would like to have the forecasting flexibility in
>> Autoscaler side. Because then we can let the user decide prediction time
>> duration even in runtime.
>>
>> BTW. Is it possible to do this in CEP, by redeploying execution plans or
>> so?
>>
> Well currently we have a forecast function for univariate regression.
Where you can provide the y stream and the x stream and a value for the x
value you want to predict for. So for example,
timeseries:forecast(x+5, y, x) - will use y and x streams to compute the
regression equation and then provide the forecast y value for x+5, so you
can provide the prediction time here. However, the current implementation
only caters to 1 independent variable scenario. So if you want to do this
on CEP side you can simply get the coefficients using the
timeseries:regress() function and then write a further siddhi query, where
you get the v = at + bt^2 + c value for any incoming t value.
>
>> b. Can't we also consider using exponentially weighted moving averages
>>> for the previous approach. So instead of using average gradient and average
>>> second derivative we can use 'decaying windows' in CEP and get the
>>> exponentially weighted moving average of the gradient and second
>>> derivative. This will eliminate the spawning of new instances due to sudden
>>> 'spikes' as we can control the decaying factor such that we give a
>>> practically acceptable weightage to the most recent events compared to
>>> older events.
>>>
>>>
>> A great thought. Exponentially weighted moving average filter would be a
>> good addition for spike avoidance.
>>
>> Thanks.
>>
>>
>>> Seshika
>>>
>>> 1. https://docs.wso2.com/display/CEP400/Regression
>>>
>>> On Tue, Nov 11, 2014 at 8:51 PM, Lasantha Fernando <
>>> lasantha.fdo@gmail.com> wrote:
>>>
>>>> Hi Lahiru,
>>>>
>>>> Would it be possible to use linear regression already available as
>>>> Siddhi extensions in [1] or maybe improve on that existing extensions
>>>> to extend it to fit polynomial curves? The code is available here [2].
>>>>
>>>> I think forecasting is also available which can be useful in this
>>>> usecase. WDYT? Just sharing my 2 cents.. :-)
>>>>
>>>> [1]
>>>> http://mail.wso2.org/mailarchive/architecture/2014-March/015696.html
>>>> [2]
>>>> https://github.com/wso2-dev/siddhi/tree/master/modules/siddhi-extensions
>>>>
>>>> Thanks,
>>>> Lasantha
>>>>
>>>> On Tue, Nov 11, 2014 at 3:58 PM, Lahiru Sandaruwan <la...@wso2.com>
>>>> wrote:
>>>> > Hi all,
>>>> >
>>>> > This contains the content i already sent to Stratos dev. Idea is to
>>>> > highlight and separate the new improvement.
>>>> >
>>>> > Current implementation
>>>> >
>>>> > Currently CEP calculates average, gradient, and second derivative and
>>>> send
>>>> > those values to Autoscaler. Then Autoscaler predicts the values using
>>>> S =
>>>> > u*t + 0.5*a*t*t.
>>>> >
>>>> > In this method CEP calculation is not very much accurate as it does
>>>> not
>>>> > consider all the events when calculating the gradient and second
>>>> derivative.
>>>> > Therefore the equation we apply doesn't yield the best prediction.
>>>> >
>>>> > Proposed Implementation
>>>> >
>>>> > CEP's task
>>>> >
>>>> > I think best approach is to do "curve fitting"[1] for received event
>>>> sample
>>>> > in a particular time window. Refer "Locally weighted linear
>>>> regression"
>>>> > section at [2] for more details.
>>>> >
>>>> > We would need a second degree polynomial fitter for this, where we
>>>> can use
>>>> > Apache commons math library for this. Refer the sample at [3], we can
>>>> run
>>>> > this with any degree. e.g. 2, 3. Just increase the degree to increase
>>>> the
>>>> > accuracy.
>>>> >
>>>> > E.g.
>>>> > So if get degree 2 polynomial fitter, we will have an equation like
>>>> below
>>>> > where value(v) is our statistic value and time(t) is the time of
>>>> event.
>>>> >
>>>> > Equation we get from received events,
>>>> > v = a*t*t + b*t + c
>>>> >
>>>> > So the solution is,
>>>> >
>>>> > Find memberwise curves that fits events received in specific
>>>> window(say 10
>>>> > minutes) at CEP
>>>> > Send the parameters of fitted line(a, b, and c in above equation)
>>>> with the
>>>> > timestamp of last event(T) in the window, to Autoscaler
>>>> >
>>>> > Autoscaler's task
>>>> >
>>>> > Autoscaler use v = a*t*t + b*t + c function to predict the value in
>>>> any
>>>> > timestamp from the last timestamp
>>>> >
>>>> > E.g. Say we need to find the value(v) after 1 minute(assuming we
>>>> carried all
>>>> > the calculations in milliseconds),
>>>> >
>>>> > v = a * (T+60000) * (T+60000) + b * (T+60000) + c
>>>> >
>>>> > So we have memberwise predictions and we can find clusterwise
>>>> prediction by
>>>> > averaging all the memberwise values.
>>>> >
>>>> >
>>>> > Please send your thoughts.
>>>> >
>>>> > Thanks.
>>>> >
>>>> > [1] http://en.wikipedia.org/wiki/Curve_fitting
>>>> > [2] http://cs229.stanford.edu/notes/cs229-notes1.pdf
>>>> > [3]
>>>> http://commons.apache.org/proper/commons-math/userguide/fitting.html
>>>> >
>>>> >
>>>> > --
>>>> > --
>>>> > Lahiru Sandaruwan
>>>> > Committer and PMC member, Apache Stratos,
>>>> > Senior Software Engineer,
>>>> > WSO2 Inc., http://wso2.com
>>>> > lean.enterprise.middleware
>>>> >
>>>> > email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
>>>> > linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>>>> >
>>>>
>>>
>>>
>>
>>
>> --
>> --
>> Lahiru Sandaruwan
>> Committer and PMC member, Apache Stratos,
>> Senior Software Engineer,
>> WSO2 Inc., http://wso2.com
>> lean.enterprise.middleware
>>
>> email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
>> linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>>
>>
>
>
> --
> --
> Lahiru Sandaruwan
> Committer and PMC member, Apache Stratos,
> Senior Software Engineer,
> WSO2 Inc., http://wso2.com
> lean.enterprise.middleware
>
> email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
> linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>
>
Re: [Autoscaling] [Improvement] Introducing "curve fitting" for stat
prediction algorithm of Autoscaler
Posted by Lahiru Sandaruwan <la...@wso2.com>.
Also this is a good read to learn how Netflix use these algorithms for
scaling.
http://techblog.netflix.com/search/label/prediction
On Tue, Nov 11, 2014 at 11:07 PM, Lahiru Sandaruwan <la...@wso2.com>
wrote:
> Hi Seshika,
>
> Thanks for the detailed response,
>
> On Tue, Nov 11, 2014 at 10:08 PM, Seshika Fernando <se...@wso2.com>
> wrote:
>
>> Hi all,
>>
>> I have 2 comments.
>>
>> a. The timeseries extension to CEP which supports uni-variate and
>> multi-variate linear regression [1] can be used for this. We can use the
>> multi-variate regression to solve the curve fitting stated in Lahiru's
>> email. Basically what we need to do is use *t *and *t^2* as x1 and x2.
>> There by if we run linear regression we get a,b,c such that V=a+b*t+c*t^2.
>>
>
> Nice to see this exists in CEP already :)
>
> +1 for using multi-variate regression to the curve fitting. Is it
> available in CEP 3.1.0? or can we plug it to 3.1.0?
>
>
>
>> As Lasantha has mentioned we do have a forecasting facility as well, but
>> currently it only works for uni-variate regression, which is not the case
>> here. But if you really need it I might be able to extend it for this
>> use-case, for the moment. You can still use the existing regression
>> facility to determine the coefficients and do the forecasting yourself
>> (which is just plugging those values in to the above equation, with the
>> relevant t values.
>> Let me also just mention, that even though the function is 'linear'
>> regression, we can use linear regression to fit polynomial curves as long
>> as we know the degree of the polynomial function (which in this case we do).
>>
>>
> In Stratos case, i would like to have the forecasting flexibility in
> Autoscaler side. Because then we can let the user decide prediction time
> duration even in runtime.
>
> BTW. Is it possible to do this in CEP, by redeploying execution plans or
> so?
>
> b. Can't we also consider using exponentially weighted moving averages for
>> the previous approach. So instead of using average gradient and average
>> second derivative we can use 'decaying windows' in CEP and get the
>> exponentially weighted moving average of the gradient and second
>> derivative. This will eliminate the spawning of new instances due to sudden
>> 'spikes' as we can control the decaying factor such that we give a
>> practically acceptable weightage to the most recent events compared to
>> older events.
>>
>>
> A great thought. Exponentially weighted moving average filter would be a
> good addition for spike avoidance.
>
> Thanks.
>
>
>> Seshika
>>
>> 1. https://docs.wso2.com/display/CEP400/Regression
>>
>> On Tue, Nov 11, 2014 at 8:51 PM, Lasantha Fernando <
>> lasantha.fdo@gmail.com> wrote:
>>
>>> Hi Lahiru,
>>>
>>> Would it be possible to use linear regression already available as
>>> Siddhi extensions in [1] or maybe improve on that existing extensions
>>> to extend it to fit polynomial curves? The code is available here [2].
>>>
>>> I think forecasting is also available which can be useful in this
>>> usecase. WDYT? Just sharing my 2 cents.. :-)
>>>
>>> [1] http://mail.wso2.org/mailarchive/architecture/2014-March/015696.html
>>> [2]
>>> https://github.com/wso2-dev/siddhi/tree/master/modules/siddhi-extensions
>>>
>>> Thanks,
>>> Lasantha
>>>
>>> On Tue, Nov 11, 2014 at 3:58 PM, Lahiru Sandaruwan <la...@wso2.com>
>>> wrote:
>>> > Hi all,
>>> >
>>> > This contains the content i already sent to Stratos dev. Idea is to
>>> > highlight and separate the new improvement.
>>> >
>>> > Current implementation
>>> >
>>> > Currently CEP calculates average, gradient, and second derivative and
>>> send
>>> > those values to Autoscaler. Then Autoscaler predicts the values using
>>> S =
>>> > u*t + 0.5*a*t*t.
>>> >
>>> > In this method CEP calculation is not very much accurate as it does not
>>> > consider all the events when calculating the gradient and second
>>> derivative.
>>> > Therefore the equation we apply doesn't yield the best prediction.
>>> >
>>> > Proposed Implementation
>>> >
>>> > CEP's task
>>> >
>>> > I think best approach is to do "curve fitting"[1] for received event
>>> sample
>>> > in a particular time window. Refer "Locally weighted linear regression"
>>> > section at [2] for more details.
>>> >
>>> > We would need a second degree polynomial fitter for this, where we can
>>> use
>>> > Apache commons math library for this. Refer the sample at [3], we can
>>> run
>>> > this with any degree. e.g. 2, 3. Just increase the degree to increase
>>> the
>>> > accuracy.
>>> >
>>> > E.g.
>>> > So if get degree 2 polynomial fitter, we will have an equation like
>>> below
>>> > where value(v) is our statistic value and time(t) is the time of event.
>>> >
>>> > Equation we get from received events,
>>> > v = a*t*t + b*t + c
>>> >
>>> > So the solution is,
>>> >
>>> > Find memberwise curves that fits events received in specific
>>> window(say 10
>>> > minutes) at CEP
>>> > Send the parameters of fitted line(a, b, and c in above equation) with
>>> the
>>> > timestamp of last event(T) in the window, to Autoscaler
>>> >
>>> > Autoscaler's task
>>> >
>>> > Autoscaler use v = a*t*t + b*t + c function to predict the value in any
>>> > timestamp from the last timestamp
>>> >
>>> > E.g. Say we need to find the value(v) after 1 minute(assuming we
>>> carried all
>>> > the calculations in milliseconds),
>>> >
>>> > v = a * (T+60000) * (T+60000) + b * (T+60000) + c
>>> >
>>> > So we have memberwise predictions and we can find clusterwise
>>> prediction by
>>> > averaging all the memberwise values.
>>> >
>>> >
>>> > Please send your thoughts.
>>> >
>>> > Thanks.
>>> >
>>> > [1] http://en.wikipedia.org/wiki/Curve_fitting
>>> > [2] http://cs229.stanford.edu/notes/cs229-notes1.pdf
>>> > [3]
>>> http://commons.apache.org/proper/commons-math/userguide/fitting.html
>>> >
>>> >
>>> > --
>>> > --
>>> > Lahiru Sandaruwan
>>> > Committer and PMC member, Apache Stratos,
>>> > Senior Software Engineer,
>>> > WSO2 Inc., http://wso2.com
>>> > lean.enterprise.middleware
>>> >
>>> > email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
>>> > linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>>> >
>>>
>>
>>
>
>
> --
> --
> Lahiru Sandaruwan
> Committer and PMC member, Apache Stratos,
> Senior Software Engineer,
> WSO2 Inc., http://wso2.com
> lean.enterprise.middleware
>
> email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
> linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>
>
--
--
Lahiru Sandaruwan
Committer and PMC member, Apache Stratos,
Senior Software Engineer,
WSO2 Inc., http://wso2.com
lean.enterprise.middleware
email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
Re: [Autoscaling] [Improvement] Introducing "curve fitting" for stat
prediction algorithm of Autoscaler
Posted by Lahiru Sandaruwan <la...@wso2.com>.
Hi Seshika,
Thanks for the detailed response,
On Tue, Nov 11, 2014 at 10:08 PM, Seshika Fernando <se...@wso2.com> wrote:
> Hi all,
>
> I have 2 comments.
>
> a. The timeseries extension to CEP which supports uni-variate and
> multi-variate linear regression [1] can be used for this. We can use the
> multi-variate regression to solve the curve fitting stated in Lahiru's
> email. Basically what we need to do is use *t *and *t^2* as x1 and x2.
> There by if we run linear regression we get a,b,c such that V=a+b*t+c*t^2.
>
Nice to see this exists in CEP already :)
+1 for using multi-variate regression to the curve fitting. Is it available
in CEP 3.1.0? or can we plug it to 3.1.0?
> As Lasantha has mentioned we do have a forecasting facility as well, but
> currently it only works for uni-variate regression, which is not the case
> here. But if you really need it I might be able to extend it for this
> use-case, for the moment. You can still use the existing regression
> facility to determine the coefficients and do the forecasting yourself
> (which is just plugging those values in to the above equation, with the
> relevant t values.
> Let me also just mention, that even though the function is 'linear'
> regression, we can use linear regression to fit polynomial curves as long
> as we know the degree of the polynomial function (which in this case we do).
>
>
In Stratos case, i would like to have the forecasting flexibility in
Autoscaler side. Because then we can let the user decide prediction time
duration even in runtime.
BTW. Is it possible to do this in CEP, by redeploying execution plans or so?
b. Can't we also consider using exponentially weighted moving averages for
> the previous approach. So instead of using average gradient and average
> second derivative we can use 'decaying windows' in CEP and get the
> exponentially weighted moving average of the gradient and second
> derivative. This will eliminate the spawning of new instances due to sudden
> 'spikes' as we can control the decaying factor such that we give a
> practically acceptable weightage to the most recent events compared to
> older events.
>
>
A great thought. Exponentially weighted moving average filter would be a
good addition for spike avoidance.
Thanks.
> Seshika
>
> 1. https://docs.wso2.com/display/CEP400/Regression
>
> On Tue, Nov 11, 2014 at 8:51 PM, Lasantha Fernando <lasantha.fdo@gmail.com
> > wrote:
>
>> Hi Lahiru,
>>
>> Would it be possible to use linear regression already available as
>> Siddhi extensions in [1] or maybe improve on that existing extensions
>> to extend it to fit polynomial curves? The code is available here [2].
>>
>> I think forecasting is also available which can be useful in this
>> usecase. WDYT? Just sharing my 2 cents.. :-)
>>
>> [1] http://mail.wso2.org/mailarchive/architecture/2014-March/015696.html
>> [2]
>> https://github.com/wso2-dev/siddhi/tree/master/modules/siddhi-extensions
>>
>> Thanks,
>> Lasantha
>>
>> On Tue, Nov 11, 2014 at 3:58 PM, Lahiru Sandaruwan <la...@wso2.com>
>> wrote:
>> > Hi all,
>> >
>> > This contains the content i already sent to Stratos dev. Idea is to
>> > highlight and separate the new improvement.
>> >
>> > Current implementation
>> >
>> > Currently CEP calculates average, gradient, and second derivative and
>> send
>> > those values to Autoscaler. Then Autoscaler predicts the values using S
>> =
>> > u*t + 0.5*a*t*t.
>> >
>> > In this method CEP calculation is not very much accurate as it does not
>> > consider all the events when calculating the gradient and second
>> derivative.
>> > Therefore the equation we apply doesn't yield the best prediction.
>> >
>> > Proposed Implementation
>> >
>> > CEP's task
>> >
>> > I think best approach is to do "curve fitting"[1] for received event
>> sample
>> > in a particular time window. Refer "Locally weighted linear regression"
>> > section at [2] for more details.
>> >
>> > We would need a second degree polynomial fitter for this, where we can
>> use
>> > Apache commons math library for this. Refer the sample at [3], we can
>> run
>> > this with any degree. e.g. 2, 3. Just increase the degree to increase
>> the
>> > accuracy.
>> >
>> > E.g.
>> > So if get degree 2 polynomial fitter, we will have an equation like
>> below
>> > where value(v) is our statistic value and time(t) is the time of event.
>> >
>> > Equation we get from received events,
>> > v = a*t*t + b*t + c
>> >
>> > So the solution is,
>> >
>> > Find memberwise curves that fits events received in specific window(say
>> 10
>> > minutes) at CEP
>> > Send the parameters of fitted line(a, b, and c in above equation) with
>> the
>> > timestamp of last event(T) in the window, to Autoscaler
>> >
>> > Autoscaler's task
>> >
>> > Autoscaler use v = a*t*t + b*t + c function to predict the value in any
>> > timestamp from the last timestamp
>> >
>> > E.g. Say we need to find the value(v) after 1 minute(assuming we
>> carried all
>> > the calculations in milliseconds),
>> >
>> > v = a * (T+60000) * (T+60000) + b * (T+60000) + c
>> >
>> > So we have memberwise predictions and we can find clusterwise
>> prediction by
>> > averaging all the memberwise values.
>> >
>> >
>> > Please send your thoughts.
>> >
>> > Thanks.
>> >
>> > [1] http://en.wikipedia.org/wiki/Curve_fitting
>> > [2] http://cs229.stanford.edu/notes/cs229-notes1.pdf
>> > [3]
>> http://commons.apache.org/proper/commons-math/userguide/fitting.html
>> >
>> >
>> > --
>> > --
>> > Lahiru Sandaruwan
>> > Committer and PMC member, Apache Stratos,
>> > Senior Software Engineer,
>> > WSO2 Inc., http://wso2.com
>> > lean.enterprise.middleware
>> >
>> > email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
>> > linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>> >
>>
>
>
--
--
Lahiru Sandaruwan
Committer and PMC member, Apache Stratos,
Senior Software Engineer,
WSO2 Inc., http://wso2.com
lean.enterprise.middleware
email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
Re: [Autoscaling] [Improvement] Introducing "curve fitting" for stat
prediction algorithm of Autoscaler
Posted by Seshika Fernando <se...@wso2.com>.
Hi all,
I have 2 comments.
a. The timeseries extension to CEP which supports uni-variate and
multi-variate linear regression [1] can be used for this. We can use the
multi-variate regression to solve the curve fitting stated in Lahiru's
email. Basically what we need to do is use *t *and *t^2* as x1 and x2.
There by if we run linear regression we get a,b,c such that V=a+b*t+c*t^2.
As Lasantha has mentioned we do have a forecasting facility as well, but
currently it only works for uni-variate regression, which is not the case
here. But if you really need it I might be able to extend it for this
use-case, for the moment. You can still use the existing regression
facility to determine the coefficients and do the forecasting yourself
(which is just plugging those values in to the above equation, with the
relevant t values.
Let me also just mention, that even though the function is 'linear'
regression, we can use linear regression to fit polynomial curves as long
as we know the degree of the polynomial function (which in this case we do).
b. Can't we also consider using exponentially weighted moving averages for
the previous approach. So instead of using average gradient and average
second derivative we can use 'decaying windows' in CEP and get the
exponentially weighted moving average of the gradient and second
derivative. This will eliminate the spawning of new instances due to sudden
'spikes' as we can control the decaying factor such that we give a
practically acceptable weightage to the most recent events compared to
older events.
Seshika
1. https://docs.wso2.com/display/CEP400/Regression
On Tue, Nov 11, 2014 at 8:51 PM, Lasantha Fernando <la...@gmail.com>
wrote:
> Hi Lahiru,
>
> Would it be possible to use linear regression already available as
> Siddhi extensions in [1] or maybe improve on that existing extensions
> to extend it to fit polynomial curves? The code is available here [2].
>
> I think forecasting is also available which can be useful in this
> usecase. WDYT? Just sharing my 2 cents.. :-)
>
> [1] http://mail.wso2.org/mailarchive/architecture/2014-March/015696.html
> [2]
> https://github.com/wso2-dev/siddhi/tree/master/modules/siddhi-extensions
>
> Thanks,
> Lasantha
>
> On Tue, Nov 11, 2014 at 3:58 PM, Lahiru Sandaruwan <la...@wso2.com>
> wrote:
> > Hi all,
> >
> > This contains the content i already sent to Stratos dev. Idea is to
> > highlight and separate the new improvement.
> >
> > Current implementation
> >
> > Currently CEP calculates average, gradient, and second derivative and
> send
> > those values to Autoscaler. Then Autoscaler predicts the values using S =
> > u*t + 0.5*a*t*t.
> >
> > In this method CEP calculation is not very much accurate as it does not
> > consider all the events when calculating the gradient and second
> derivative.
> > Therefore the equation we apply doesn't yield the best prediction.
> >
> > Proposed Implementation
> >
> > CEP's task
> >
> > I think best approach is to do "curve fitting"[1] for received event
> sample
> > in a particular time window. Refer "Locally weighted linear regression"
> > section at [2] for more details.
> >
> > We would need a second degree polynomial fitter for this, where we can
> use
> > Apache commons math library for this. Refer the sample at [3], we can run
> > this with any degree. e.g. 2, 3. Just increase the degree to increase the
> > accuracy.
> >
> > E.g.
> > So if get degree 2 polynomial fitter, we will have an equation like below
> > where value(v) is our statistic value and time(t) is the time of event.
> >
> > Equation we get from received events,
> > v = a*t*t + b*t + c
> >
> > So the solution is,
> >
> > Find memberwise curves that fits events received in specific window(say
> 10
> > minutes) at CEP
> > Send the parameters of fitted line(a, b, and c in above equation) with
> the
> > timestamp of last event(T) in the window, to Autoscaler
> >
> > Autoscaler's task
> >
> > Autoscaler use v = a*t*t + b*t + c function to predict the value in any
> > timestamp from the last timestamp
> >
> > E.g. Say we need to find the value(v) after 1 minute(assuming we carried
> all
> > the calculations in milliseconds),
> >
> > v = a * (T+60000) * (T+60000) + b * (T+60000) + c
> >
> > So we have memberwise predictions and we can find clusterwise prediction
> by
> > averaging all the memberwise values.
> >
> >
> > Please send your thoughts.
> >
> > Thanks.
> >
> > [1] http://en.wikipedia.org/wiki/Curve_fitting
> > [2] http://cs229.stanford.edu/notes/cs229-notes1.pdf
> > [3] http://commons.apache.org/proper/commons-math/userguide/fitting.html
> >
> >
> > --
> > --
> > Lahiru Sandaruwan
> > Committer and PMC member, Apache Stratos,
> > Senior Software Engineer,
> > WSO2 Inc., http://wso2.com
> > lean.enterprise.middleware
> >
> > email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
> > linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
> >
>
Re: [Autoscaling] [Improvement] Introducing "curve fitting" for stat
prediction algorithm of Autoscaler
Posted by Lasantha Fernando <la...@gmail.com>.
Hi Lahiru,
Would it be possible to use linear regression already available as
Siddhi extensions in [1] or maybe improve on that existing extensions
to extend it to fit polynomial curves? The code is available here [2].
I think forecasting is also available which can be useful in this
usecase. WDYT? Just sharing my 2 cents.. :-)
[1] http://mail.wso2.org/mailarchive/architecture/2014-March/015696.html
[2] https://github.com/wso2-dev/siddhi/tree/master/modules/siddhi-extensions
Thanks,
Lasantha
On Tue, Nov 11, 2014 at 3:58 PM, Lahiru Sandaruwan <la...@wso2.com> wrote:
> Hi all,
>
> This contains the content i already sent to Stratos dev. Idea is to
> highlight and separate the new improvement.
>
> Current implementation
>
> Currently CEP calculates average, gradient, and second derivative and send
> those values to Autoscaler. Then Autoscaler predicts the values using S =
> u*t + 0.5*a*t*t.
>
> In this method CEP calculation is not very much accurate as it does not
> consider all the events when calculating the gradient and second derivative.
> Therefore the equation we apply doesn't yield the best prediction.
>
> Proposed Implementation
>
> CEP's task
>
> I think best approach is to do "curve fitting"[1] for received event sample
> in a particular time window. Refer "Locally weighted linear regression"
> section at [2] for more details.
>
> We would need a second degree polynomial fitter for this, where we can use
> Apache commons math library for this. Refer the sample at [3], we can run
> this with any degree. e.g. 2, 3. Just increase the degree to increase the
> accuracy.
>
> E.g.
> So if get degree 2 polynomial fitter, we will have an equation like below
> where value(v) is our statistic value and time(t) is the time of event.
>
> Equation we get from received events,
> v = a*t*t + b*t + c
>
> So the solution is,
>
> Find memberwise curves that fits events received in specific window(say 10
> minutes) at CEP
> Send the parameters of fitted line(a, b, and c in above equation) with the
> timestamp of last event(T) in the window, to Autoscaler
>
> Autoscaler's task
>
> Autoscaler use v = a*t*t + b*t + c function to predict the value in any
> timestamp from the last timestamp
>
> E.g. Say we need to find the value(v) after 1 minute(assuming we carried all
> the calculations in milliseconds),
>
> v = a * (T+60000) * (T+60000) + b * (T+60000) + c
>
> So we have memberwise predictions and we can find clusterwise prediction by
> averaging all the memberwise values.
>
>
> Please send your thoughts.
>
> Thanks.
>
> [1] http://en.wikipedia.org/wiki/Curve_fitting
> [2] http://cs229.stanford.edu/notes/cs229-notes1.pdf
> [3] http://commons.apache.org/proper/commons-math/userguide/fitting.html
>
>
> --
> --
> Lahiru Sandaruwan
> Committer and PMC member, Apache Stratos,
> Senior Software Engineer,
> WSO2 Inc., http://wso2.com
> lean.enterprise.middleware
>
> email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
> linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>