On-line Portfolio Selection from Grant K

@Grant wrote an implementation of "On-Line Portfolio Selection with Moving Average Reversion"

I copied his source and made a small tweak to allow a no-operation backtest to complete, so others can clone his original. @Grant and @Thomas started the discussion here: https://www.quantopian.com/posts/share-algorithms-to-be-re-written-for-quantopian

70
Backtest from to with initial capital
Total Returns
--
Alpha
--
Beta
--
Sharpe
--
Sortino
--
Max Drawdown
--
Benchmark Returns
--
Volatility
--
 Returns 1 Month 3 Month 6 Month 12 Month
 Alpha 1 Month 3 Month 6 Month 12 Month
 Beta 1 Month 3 Month 6 Month 12 Month
 Sharpe 1 Month 3 Month 6 Month 12 Month
 Sortino 1 Month 3 Month 6 Month 12 Month
 Volatility 1 Month 3 Month 6 Month 12 Month
 Max Drawdown 1 Month 3 Month 6 Month 12 Month
#
# Algorithm based on this publication:
#

def initialize(context):
context.stocks = [sid(8554),sid(19920),sid(22739)]
context.price = {}
context.x_tilde = {}
context.b_t = {}
context.b = {}
context.b_norm = {}
context.eps = 1.1
def handle_data(data, context):
x_bar = 0.0
m = len(context.stocks)
sq_norm = 0.0
dot_prod = 0.0
b_tot = 0.0
# find relative moving average price for each security
for stock in context.stocks:
price = data[stock].price
x_tilde = float(data[stock].mavg(3))/price
if data.portfolio.positions_value > 0.0:
b_t = data.portfolio.positions[stock].amount * price
b_t = b_t/data.portfolio.positions_value
else:
b_t = 1.0/m
x_bar = x_bar + x_tilde
x_bar = x_bar/m  # average predicted relative price
for stock in context.stocks:
sq_norm = sq_norm + (x_tilde-x_bar)**2
dot_prod = dot_prod + b_t*x_tilde
lam = max(0,(context.eps-dot_prod)/sq_norm)
for stock in context.stocks:
b = b_t + lam*(x_tilde-x_bar)
b_tot = b_tot + b
for stock in context.stocks:
b_norm = b/b_tot  # new portfolio
context.b_norm[stock] = b_norm
This backtest was created using an older version of the backtester. Please re-run this backtest to see results using the latest backtester. Learn more about the recent changes.
There was a runtime error.
Disclaimer

The material on this website is provided for informational purposes only and does not constitute an offer to sell, a solicitation to buy, or a recommendation or endorsement for any security or strategy, nor does it constitute an offer to provide investment advisory services by Quantopian. In addition, the material offers no opinion with respect to the suitability of any security or specific investment. No information contained herein should be regarded as a suggestion to engage in or refrain from any investment-related course of action as none of Quantopian nor any of its affiliates is undertaking to provide investment advice, act as an adviser to any plan or entity subject to the Employee Retirement Income Security Act of 1974, as amended, individual retirement account or individual retirement annuity, or give advice in a fiduciary capacity with respect to the materials presented herein. If you are an individual retirement or other investor, contact your financial advisor or other fiduciary unrelated to Quantopian about whether any given investment idea, strategy, product or service described herein may be appropriate for your circumstances. All investments involve risk, including loss of principal. Quantopian makes no guarantees as to the accuracy or completeness of the views expressed in the website. The views are subject to change, and may have become unreliable for various reasons, including changes in market conditions or economic circumstances.

21 responses

In case folks need some light bedtime reading...here are some relevant links:

On-Line Portfolio Selection with Moving Average Reversion

PAMR: Passive aggressive mean reversion strategy for portfolio selection

http://www.cais.ntu.edu.sg/~chhoi/PAMR/

Efficient Projections onto the l1 -Ball for Learning in High Dimensions

Efficient learning of label ranking by soft projections onto polyhedra

Needless to say, it's pretty heavy stuff. As best I can tell, the secret sauce is in the last fairly recent paper cited above. I should be able to provide a full outline of the algorithm for comment, based on the above references. The implementation is not as complicated as the papers might suggest.

John - I just joined your site yesterday, so this might be a silly question, but why does your example above have no performance results for the Algorithm?

@Eric, Not a silly question at all -- The algo doesn't place orders yet!

You are probably wondering why :). A few people are working with Grant to round out the implementation, and he shared the source code before it was fully implemented to help speed the collaboration.

The posts in the forums with the blue sparkline charts are examples that have real returns. The sparkline is a compressed version of the returns. The grayscale charts are for algorithms that don't generate returns, which are usually code samples or proofs of concept like this one.

Here is a nice example of placing orders: https://www.quantopian.com/posts/papertrading-for-coursera-computational-finance-homework

fawce

Hello Thomas (& others),

I'm continuing our discussion from https://www.quantopian.com/posts/share-algorithms-to-be-re-written-for-quantopian.

I've realized that I'd benefit from some Python/Quantopian coding expertise (I don't have experience with Python...one of my motivations here is to get a feel for it). Here are some tasks:

1. Write a Python/Quantopian implementation of the MATLAB function "simplex_projection.m" found in this file: http://www.cais.ntu.edu.sg/~chhoi/PAMR/PAMR.zip. In the same .zip file, you will find "pamr_1_run.m" which shows how the simplex projection function is called. Note that the author is claiming copyright to his MATLAB code...not sure what that means in this context...I decided not to copy his code into this forum, but give the link instead.
2. As you suggested, write a function to rebalance/update a portfolio (in this context, submit orders to change the normalized portfolio vector from b_t to b_t+1.
3. Advise how to use vectors/matrices (and related operators/functions) in the context of Python/Quantopian. I think the code would be more readable. Also, there is a speed advantage in MATLAB when calculations can be vectorized...perhaps the same is true in Python?

Grant

Hi Grant,

Awesome to see this project progressing! Some reactions:

1. I'll give it a shot and will post the resulting code here. Doesn't look too crazy.
2. Yup, we'll definitely need that. If I have time I'll give it a shot but I think this could also be done by someone else. Any volunteers? (Happy to provide more details as to what needs to be done specifically).
3. Yes, there definitely is the same benefit in Python. Going over the code I think some of it should actually be doing matrix algebra where it isn't, so I'll take a closer look at that.

Will let keep you posted.

Thomas

Disclaimer

The material on this website is provided for informational purposes only and does not constitute an offer to sell, a solicitation to buy, or a recommendation or endorsement for any security or strategy, nor does it constitute an offer to provide investment advisory services by Quantopian. In addition, the material offers no opinion with respect to the suitability of any security or specific investment. No information contained herein should be regarded as a suggestion to engage in or refrain from any investment-related course of action as none of Quantopian nor any of its affiliates is undertaking to provide investment advice, act as an adviser to any plan or entity subject to the Employee Retirement Income Security Act of 1974, as amended, individual retirement account or individual retirement annuity, or give advice in a fiduciary capacity with respect to the materials presented herein. If you are an individual retirement or other investor, contact your financial advisor or other fiduciary unrelated to Quantopian about whether any given investment idea, strategy, product or service described herein may be appropriate for your circumstances. All investments involve risk, including loss of principal. Quantopian makes no guarantees as to the accuracy or completeness of the views expressed in the website. The views are subject to change, and may have become unreliable for various reasons, including changes in market conditions or economic circumstances.

Hello Thomas,

I continue to chip away at this project. One thing that is confusing is the authors' ad hoc "normalization" step at the end. If you have a look at p. 254 of PAMR: Passive aggressive mean reversion strategy for portfolio selection you'll find the basic outline of his solution to the OLMAR optimization problem (although the PAMR problem has different contraints, the math appears to be essentially the same). The murky part is captured in the authors' comment "that the non-negativity of portfolio b is not considered here since introducing this term causes too much complexity, and alternatively we project the resulting portfolio into a simplex to enforce the non-negativity constraint."

If you look at p. 1577 of Efficient learning of label ranking by soft projections onto polyhedra, the authors provide an example of how to incorporate the non-negativity constraint into the Lagrangian (the final term of the first equation on the page).

I figure that there ought to be a way to re-frame the optimization problem for clarity (although the final result is probably correct). I'll let you if I make any headway.

Hi Grant,

Yeah, this normalization is a little impractical. My guess is that the others spent quite some time to optimize with the Lagrangian multiplier that enforces b_i >= 0 but couldn't make it work. There is probably a way but I would imagine it to require some serious calculus-fu (because the authors couldn't figure it out themselves, despite having quite some incentive to do so). So my advice is (unless you really want to train using Lagrangian multipliers), just add the normalization. I ported the simplex_projection.m which seems to work just fine:

import numpy as np

def simplex_projection(v, z=1):
"""Projection vectors to the simplex domain

Implemented according to the paper: Efficient projections onto the
l1-ball for learning in high dimensions, John Duchi, et al. ICML 2008.
Implementation Time: 2011 June 17 by [email protected] AT pmail.ntu.edu.sg
Optimization Problem: min_{w}\| w - v \|_{2}^{2}
s.t. sum_{i=1}^{m}=z, w_{i}\geq 0

Input: A vector v \in R^{m}, and a scalar z > 0 (default=1)
Output: Projection vector w

:Example:
>>> proj = simplex_projection([.4 ,.3, -.4, .5])
>>> print proj
array([ 0.33333333,  0.23333333,  0.        ,  0.43333333])
>>> print proj.sum()
1.0

Original matlab implementation: Copyright 2011 by Bin
Python-port: Copyright 2012 by Thomas Wiecki ([email protected]).
"""

v = np.asarray(v)
p = len(v)
w = np.zeros_like(v)

# Sort v into u in descending order
u = np.sort(v)[::-1]
idx = np.argsort(v)[::-1]
# Find \rho = max{j \in [n]: u_{j}-(sum(u(1:j, 1))-z)/j >0  }
for j in range(p):
if (u[j] - (np.sum(u[:j])-z) / j <= 0):
break

# Define \theta = (sum(u(1:rho, 1))-z)/rho
theta = (np.sum(u[:j])-z) / j;

# w_{i}=max{ v_{i} - theta }
w[idx[:j]] = v[idx[:j]] - theta

return w


Thanks Thomas,

I've gathered from a book I borrowed and poking around the internet that the case of inequality constraints is not always so straightforward. It might not be for several days, but I'll keep plugging away at completing the full Python/Quantopian implementation.

Grant

@Grant: To better collaborate on this I'd like to try working on this on github. I uploaded what you posted, added the simplex_projection code and put it on github. The idea is that we'll give you access to that repo so that you and I (or other collaborators!) can push and pull code there.

One reason I'd like to try this is because we are thinking of ways to integrate github into quantopian so this can hopefully serve as a nice laboratory. Now we can only execute this on Quantopian so we'd have to copy&paste back and forth but this is something which will change once we figure out the right way to implement this. Would you be interested to help us out in that way?

Finally, if you don't have a github account, it's easy to create one. Just tell me your github name and we'll add you.

Thomas,

Sure, I'll give github a try. Please note that I don't expect to have a lot of time to pour into this on a consistent basis...but we'll see how it goes.

Grant

@Grant: Sure, there's no rush at all. Maybe we can even attract some contributors that way!

I just set up my github account (I think). So feel free to do whatever needs to be done there for us/others to continue working.

Great, what's your github username? You can also email me at [email protected] but it's not really secret :)

Just following up to share the address of the new public repo for algo scripts: https://github.com/quantopian/quantopian-algos

Thomas/Fawce,

1. Please consider the number of securities ("assets" in the paper) used for the authors' backtesting. If you see Table 3 on Page 6 of On-Line Portfolio Selection with Moving Average Reversion, the numbers range from 23 to 88. As I recall, Quantopian is limited to portfolios of 10 securities or fewer, correct?

2. The paper discusses combining multiple OLMAR portfolios (the basic algorithm), each optimized for a different look-back window, w (see the final paragraph of Section 4.3 on Page 5). The full portfolio is constructed by performance-weighting versus w, with w ranging from 3 to 30 days. Given that the Quantopian moving average transform cannot be called with a variable (e.g. mavg(3) works, but mavg(w) doesn't), the weighting over a variable look-back window could be kinda awkward to implement in Quantopian. Any ideas how to manage this in the code?

@Grant:

Re 1: This will be changed very soon with the universe selection.

Re 2: Agreed. I think we should just add an option to turn off the automagic registration of transforms and let users register transforms themselves (in zipline one can do this with self.register_transform).

An additional note (credit to Thomas who noted the divide-by-zero problem in the algorithm). See the top of Page 255 of:

PAMR: Passive aggressive mean reversion strategy for portfolio selection

It states "Note that in case of zero market volatility, that is, || x_t − x_bar_t 1 ||^2 = 0, we just set τ = 0."

I'm not sure how to implement this rule in the algorithm, since || x_t − x_bar_t 1 ||^2 ~ 0 will cause computation problems.

In the pamr_1_run.m MATLAB script posted at the site http://www.cais.ntu.edu.sg/~chhoi/PAMR/, the author tests for the zero volatility condition with this code:

% Step 4: Set parameters
x_bar = sum(data(t, :)) / N;
denominator = (data(t, :) - x_bar)*(data(t, :) - x_bar)';
if (~eq(denominator, 0.0)),
tau = min([C, ell/denominator]);
else
tau = 0;
end


Got to say gents, look how far you have come! Makes me all nostalgic revisiting this thread :)

Good fortune

Thanks Tybalt,

Still lots to learn and fun to be had! Looking forward to tinkering with the new research platform.

Grant