Synchronicity

In mathematics, functions are beautiful things. They represent lines, curves, surfaces, and things in higher dimensional spaces that defy verbal description. With applications in areas that span from practical statistics to abstruse string theory, no one can argue their importance to daily life.

In programming, functions are just as important (I would have said "if not more important", but that seemed needlessly tautological). Interesting, and sometimes overlooked though, are synchronicity aspects of function invocation in programming. Now that we already have a post on location based services, we can leverage that to make our points here more clearly. So let's embark on this journey.

Most functions in computer science are synchronous. By this we mean, we build a function, we call it with zero, one or more arguments, and it returns a value. The code we write that invokes the function populates the arguments, makes the function invocation, then waits patiently till the function call completes, assigns the returned variable to a program variable, and continues execution. Of course, depending on whether the variables were passed by value or by reference, and whether any global variables were also used, etc, there may be a number of other "side-effects" caused by the function invocation on other aspects of program execution but we blithely ignore these here for sake of simplicity.

Synchronous function execution is thus, the simplest, and most intuitive way that functions, and yes sub-routines, and the like are used. But is that all functions can be used for? Let's study a couple of other models.

Enter the Asynchronous function call
When we look at complex APIs - such as, for example the OSA/Parlay APIs for mobile network application development, these contain function calls where what the function is asked to do cannot be done immediately. It is unreasonable to expect a program to wait for as long as a function might take to return in such cases. A way out of this dilemma might be to embed this function call in a separate thread from the main thread of program execution, and have that thread block on the function while the rest of the program goes on its merry way. An arguably more elegant approach is through the use of asynchronous methods.

So how do these work? Software platforms like CORBA and Java RMI (does anyone still use this anymore?) permit one to invoke a function and register a "call-back". The call-back is a reference to a function in the main program that the called function (typically run across the network on another machine somewhere), can invoke on it. So the logic flow proceeds something like this:

1. main program A invokes function x on program B, passing along a call-back reference c.
2. B returns an immediate return value, typically indicating whether the function was well structured and     if it will be executed.
3. the function x returns synchronously to A the immediate return value from (2) above.
4. B continues executing the function, and when it has an update for A, passes this value to A by invoking call-back c. c returns immediately (i.e. c is synchronous to B)
5. at this point, c is either still open, or is closed based on pre-determined call-back protocol design between A and B specified in the API.

All this might seem needlessly complicated. But it can be extremely useful. So we look at an example below.

Using Asynchronous Functions - An Example

Let's say you (an application) want periodic location updates for a mobile handset. You could poll the network for location every 30 seconds or so synchronously, and speed up the poll interval if the handset is traveling faster, and slow down the interval if it is slower-moving. But this puts the burden on the application to keep timers etc., A more elegant way to implement this would be to have the application register a call-back with the underlying network node saying: "here's the terminal whose location I need: 555-555-1111. send it to me every 30 sec at this address http://updatesRUs/5555551111x will you? till I tell you to stop, thanks. and if you think it's not really moving that much, feel free to slow down updates a bit"

And the app can continue about its business and process updates as it receives them. When the user tied to the app decides he has for example, reached his destination and does not need location information anymore, the app can send another message to the network saying "remember my request for 555-555-1111? cancel that now please". And the call-back address specified above disappears, so the network cannot post any more updates. Useful, isn't it?

From callbacks to "recruiting"

An erstwhile colleague of mine (the author thanks A. Sahuguet) once showed me another model called "recruiting" that can be even more useful. The way this works is, A invokes a method on B, B on C, and C gets back directly to A. In other words, B "recruits" C to respond to A's request. Typically, networked software implementations require the request/response flow to be A->B->C->B->A, but this is shortened to A->B->C->A in this scenario. Of course there are issues with security etc, and yes, there are ways to address them, but we do not cover those here. How one might set up asynchronous function calls to support a recruiting model is left as an exercise to the reader.

Hope this made fun reading! 

Fifty Nifty Pytools

In this post, we look at several simple but useful python code snippets. While we say "fifty" in the post title, it is hoped that over time the count will grow much larger.

[Snippet 0001] Particularly while working in Finance, one needs very strong date libraries and tools. Python gives us datetime which is excellent, and additional functionality can be built atop that. When one has to tie together data from excel spreadsheets, databases e.g. MySQL, and other sources and maintain a single data set that can be used for data-mining or back-testing, having good date functions at hand becomes critical. An example of such is our first snippet below. More date-related snippets will likely follow.

import os, sys;
from datetime import *;


import os, sys;
from datetime import *;

def dtConv(x,s="OBJ"): # converts dates from one form to another
 def s2(n): # nested helper function. returns str form of n if >10 else "0"+str(n)
  if n<10: return "0"+str(n);
  return str(n);

 # first, parse the input depending on type, collecting year, month, day as int
 # styles (s) supported: 
 # s="OBJ" return type is a date object. the default return type
 # s="TXT" return type is of the form "yyyymmdd" e.g. "20120131"
 # s="XL"  return type is of the form "m/d/yyyy" e.g. "2/3/2012"
 # s="XL0" return type is of the form "mm/dd/yyyy" e.g. "02/03/2012"
 # s="DB"  return type is of the form "yyyy-m-d" e.g. "2012-2-3"
 # s="DB0" return type is of the form "yyyy-mm-dd" e.g. "2012-02-03"
 if type(x)==date: y,m,d=x.year,x.month,x.day;
 else: 
  if x.count("/")==2: y,m,d=int(x.split("/")[2]),int(x.split("/")[0]),int(x.split("/")[1]);
  if x.count("-")==2: y,m,d=int(x.split("/")[0]),int(x.split("/")[1]),int(x.split("/")[2]);
  if x.count("/")==0 and x.count("-")==0 and len(x)==8: y,m,d=int(x[:4]),int(x[4:6]),int(x[6:]);
  
 # next, we generate output in the form requested
 if s=="OBJ": return date(y,m,d);
 if s=="XL": return "/".join([str(m),str(d),str(y)]);
 if s=="DB": return "-".join([str(y),str(m),str(d)]);
 if s=="XL0": return "/".join([s2(m),s2(d),s2(y)]);
 if s=="DB0": return "-".join([s2(y),s2(m),s2(d)]);
 if s=="TXT": return s2(y)+s2(m)+s2(d);
 return -1;

Examples of use:
dtConv("1/2/2012") gives datetime.date(2012,1,2)
dtConv("1/2/2012","DB0") gives "2012-01-02"
dtConv("1/2/2012","TXT") gives "20120102"
dtConv("20120102") gives datetime.date(2012,1,2)

[Snippet 0002] Simple object example with output. We define a circular list for ordinary list objects, accessing beyond the end of list causes errors. clists overcome this problem through modular arithmetic on index location.

class clist(object):
# creates a circular list object
 num_inst=0; # enforces singleton pattern

 def __init__(self,arg1=[]): # constructor
  if clist.num_inst==0: 
   clist.num_inst+=1;
   self.L=arg1;
  else: 
   print "cannot have more than one instance of class clist";
   self.__del__();

 def __del__(self): # object destructor
  pass;

 def __len__(self): # get length of clist
  return len(self.L);

 def __getitem__(self,key): # get an item of clist
  pos=key%len(self.L);
  return self.L[pos];

 def __contains__(self,key):
  if key in self.L: return True;
  return False;

 def __reversed__(self): # reverse clist contents
  self.L.reverse();
  
 def content(self): # accessor for clist contents
  return self.L;

 def redef(self,L): # reset clist contents
  self.L=L;

# sample use:
>>> execfile("clist.py");
>>> b=clist([1,2,3,4,'a','b','c']);
>>> len(b)
7
>>> reversed(b)
>>> b.content();
['c', 'b', 'a', 4, 3, 2, 1]
>>> b.redef([1,2,3,4,5,6,7]);
>>> b.content();
[1, 2, 3, 4, 5, 6, 7]
>>> len(b);
7
>>> b[1]
2
>>> b.content()
[1, 2, 3, 4, 5, 6, 7]
>>> 'a' in b
False
>>> 1 in b
True
>>> c=clist([1,2,3]);

cannot have more than one instance of class clist
>>> b[-13]
2
>>> b[13]
7
>>>

[Snippet 0003] Here, we combine the previous two snippets to design a date class dt that behaves like the examples from snippet 0001 i.e. we can store the date any way we like and seamlessly convert from one form to another as desired. Notice how clean the Object Oriented approach looks in comparison to the purely procedural technique, though of course, for more complex examples, there is probably a greater up-front price to pay in designing things in the OO way as opposed to coding procedurally. The former is arguably easier to maintain however. The code (dt.py) and output follow:


import os, sys;
from datetime import *;

def s2(x): # returns "03" if x==3, or "10" if x==10
 if x<10: return "0"+str(x); # i.e. adds leading zeroes as needed
 else: return str(x);

class dt(object):
 # creates a dt object and provides means to view it in different ways

 def __init__(self,x): # constructor
  if type(x)==str and x.count('/')==2: # covers XL and XL0 types
   m,d,y=x.split("/");
   self.m,self.d,self.y=int(m),int(d),int(y);
  if type(x)==str and x.count('-')==2: # covers DB and DB0 forms
   m,d,y=x.split("-");
   self.m,self.d,self.y=int(m),int(d),int(y);
  if type(x)==date: self.y,self.m,self.d=x.year,x.month,x.day;
   # covers the date object format
  
 def __del__(self): # destructor
  pass;

 def OBJ(self): # returns the date object
  return date(self.y,self.m,self.d);

 def TXT(self): # returns the text representation
  m,d=s2(self.m),s2(self.d);  
  return str(self.y)+m+d;

 def XL(self): # returns the Excel date type
  return "/".join([str(self.m),str(self.d),str(self.y)]);

 def XL0(self): # returns Excel date type with leading 0s
  return "/".join([s2(self.m),s2(self.d),str(self.y)]);

 def DB(self): # returns the MySQL DB date type
  return "-".join([str(self.y),str(self.m),str(self.d)]);

 def DB0(self): # returns the MySQL DB date type with LZs
  return "-".join([str(self.y),s2(self.m),s2(self.d)]);

# sample output generated as below
>>> execfile("dt.py");
>>> a=dt("4/10/2012");
>>> a.OBJ();
datetime.date(2012, 4, 10)
>>> a.TXT();
'20120410'
>>> a.DB();
'2012-4-10'
>>> a.DB0();
'2012-04-10'
>>> a.XL0();
'04/10/2012'
>>> a=dt(date(2012,4,10));
>>> a.OBJ()
datetime.date(2012, 4, 10)
>>> a.TXT()
'20120410'
>>> a.XL0();
'04/10/2012'
>>> a.XL();
'4/10/2012'
>>> a.DB();
'2012-4-10'
>>> a.DB0();
'2012-04-10'
>>>

[Snippet 0004] Python provides native support for a number of different and useful data-types. However, sometimes we may need to solve problems for which the required data types are not readily available. For instance, sometimes we may want to store data in a tree or a trie. How would we go about doing this? Luckily, Python is very intuitive in its support for these kinds of derived data structures. We present a simple implementation below that can be used to build graphs, DAGs, tries etc along with some sample examples of its use.


class node(object): # the class that creates every node object
 allNodes=[]; # static class variable to store all nodes created

 def __init__(self,val=-1): # constructor that creates node with specified tag
  self.val=val;
  self.parent=[];
  self.child=[];
  node.allNodes+=[self];

 def getVal(self): # accessor function that returns the tag value of a node
  return self.val;

 def addChild(self,n): # mutator function that connects a node to a child
  if self.getVal()!=n.getVal():
   self.child+=[n];

 def addParent(self,n): # mutator function that connects a node to a parent
  self.parent+=[n];

 def getChildren(self): # returns a list of child nodes for a node
  return self.child;

 def getChildVals(self): # returns a list of child node values for a node
  t=self.getChildren();
  r=[i.getVal() for i in t];
  return r;

 def getChildByVal(self,val): # returns a particular child node of a node by value
  p=self.getChildren();
  q=self.getChildVals();
  if val not in q: return None;
  else: return p[q.index(val)];

# Example usage

a=node(2);
b=node(3);
c=node(4);
d=node(5);
e=node(6);
f=node(7);
g=node(8);

a.addChild(b);
a.addChild(c);
b.addChild(g);
c.addChild(d);
c.addChild(e);
e.addChild(f);

b.addParent(a);
c.addParent(a);
d.addParent(c);
e.addParent(c);
f.addParent(e);
g.addParent(b);


def getDFSChain(n): # get the depth first search chain of nodes and values
 if type(n)!=node: return -1;
 r=[n];
 c=n;
 for i in r: r+=i.getChildren();
 for i in r: print i.getVal(),;

getDFSChain(a);

# output follows:
2 3 4 8 5 6 7

[Snippet 0005] This is a very interesting code snippet I remember reading on the web somewhere. Comes from a Google software engineer with a screen name of "Tryptych". I don't remember which website I read it, but the idea was so clean and elegant I remember it clearly. It is an algorithm to factorize numbers. Code follows along with example output:

import os, sys;

def F(x): # this function factors a number x into its prime factors
 r=[];
 i=2;
 while x>1:
  while (x % i)==0: 
   r+=[i];
   x/=i;
  i+=1;
 return r;

print "prime factors of 100 are: ",F(100);
print "prime factors of 1024 are: ",F(1024);
print "prime factors of 1789 are: ",F(1789);
print "prime factors of 2013 are: ",F(2013);
print "prime factors of 11204243 are: ",F(11204243);
print "prime factors of 112042431 are: ",F(112042431);
print "prime factors of 1120424311 are: ",F(1120424311);

# output follows:
prime factors of 100 are:  [2, 2, 5, 5]
prime factors of 1024 are:  [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
prime factors of 1789 are:  [1789]
prime factors of 2013 are:  [3, 11, 61]
prime factors of 11204243 are:  [19, 23, 25639]

prime factors of 112042431 are:  [3, 3, 101, 123259]
prime factors of 1120424311 are:  [1120424311]

[Snippet 0006] 

On The Design of Location Based Services

In this post, we present a broad-brush, 10,000 foot level survey of developments in the Location Based Services domain. This post is a work in progress. There are several other ideas that merit coverage here including privacy and security concerns, other means of tracking user location, and leading edge location services application scenarios.

As mobile Internet devices become more prevalent, there is a larger pull for mobility characteristics to be blended into the end-user experience. Earlier, people would log into the nearest computer and find directions to the nearest ATM, restaurant, or POI (Point Of Interest) by providing their current geographical location. Later, they graduated to providing their location (i.e. the location of their computer) once, which the computer would "register" (either using cookies or by saving with the user profile on the application website) and send out seamlessly to applications that needed this information to provide value-added services.

This in turn gradually led to more "sophisticated" usage scenarios where applications would recognize the geographic location of the RAS (remote access server) or other IP address pool from which the user's computer was assigned an address and divine the user's location from that (though due to idiosyncracies of how some ISP networks are set up and the details of the underlying infrastructure used - DSL vs. Cable, with head-end locations etc, this can sometimes lead to embarrassing errors).

As Location Based Services (or LBS for short henceforth) evolved further, cellular networks employed technologies that factored in the time difference of arrival of signals from the handset, or the angle of arrival of the signal from a handset or combinations thereof to determine the location of a handset in 3-dimensional space relative to a network of stationary cell-phone towers. During this time, acronyms like PDEs (Position Determining Equipment), MPCs (Mobile Positioning Centers), GMLCs, TDOA (Time Difference Of Arrival), EFLT, AFLT, .... (and others too numerous to mention, and perhaps not all worth even googling for anymore) were widely prevalent. But once GPS-capable hardware became available in handsets, LBS really took off in a big way.

Aside: Note how the above describe scenarios where there are sets of mobile handsets that communicate with each other via a network of stationary nodes (cell towers). Of course, more ad-hoc implementations of a set of mobile handsets that talk directly to each other in true peer-to-peer fashion (like CB radios or walkie-talkies) or the kinds of networks covered under IETF MANET standards also exist, though for simplicity we ignore them here since location in such systems can get much more complicated. <end of Aside>

Some issues persisted even with GPS. A common problem in large metropolitan areas is that of an "urban canyon". This happens when between tall buildings, say in NYC, or within buildings where surrounded by sky-scrapers, there is limited access to satellites, so one has to revert to the older ways of determining location (see para 1 above for example) to be able to provide value-added services to consumers.

As Wifi proliferated, methods akin to those from the second paragraph above were employed at Wifi hotspots to determine the relative strengths of signals from different hotspots (if these were part of a single larger infrastructure network), and then used as a basis to compute the possible location of the mobile client. This alleviated to some extent, the problems with urban canyons, since hybrid technologies could now be employed to effectively location enable applications in areas where such coverage would previously not have been possible. Hybrid as in, use GPS where GPS is available, else, if a Wifi capability existed on the handset and Wifi networks were also located in the vicinity, utilize those to get either the fix, or improve the accuracy of a fix obtained by other methods. Once this base location capability was available, service logic could be overlaid atop this.

This is where we are today. I guess what matters more than the technologies used to support location data is the applications that reside atop the stack. Once can deploy some very useful or even some very "cool" (even if unuseful) applications today, all thanks to location. Examples include geocaching, location-based games, automated mobile tourist guides, of course, GPS-enabled driving directions, and even research projects like "street stories" (yes, this was very cool in 2002).

Facebook posts Sentiment Analysis

In a previous post, we examined the utility of mining social media such as the micro-blogging site Twitter. Unrestricted, light, friendly, uncensored, and sometimes trivial and uninteresting information is shared by people with one another on such media. However, at the same time, there are some insightful posts or tweets, reporting from the site of event occurrences, from people closest to the action etc., which gives this information a certain relevance, an immediacy, a currency, an accuracy, and even a certain un-pretentiousness that comes from it being delivered by ordinary people who want to get their voice out there, get heard, share a view etc., which makes social media so fascinating.

People don't usually care that Alice had chicken for dinner. Perhaps even Alice's closest friends do not. But people do care what someone - say a civilian - on the ground in a war-zone has to say about what she has seen, is experiencing, along with video footage where available, to break a news-story to the broader world. In this latter sense, social media's contribution to the world at large is immense.

In this post, we look at legally mining data from that other large social media engine, Facebook. As of this writing, Facebook has ~800M subscribers, which makes it the size of a medium size to large country if it were a geographic agglomeration of people. And these people tend to interact with each other, some quite frequently, and do so by posting messages, sharing photographs, using applications, "liking", "poking" and doing other Facebook specific actions, all with a view to having fun, "keeping in touch", and generally having a good time being social.

Mining Facebook data can be done in two ways:
1. Searching through Facebook public domain posts and messages. This does not require one to log into Facebook but can be achieved by merely using the published public domain Facebook API to access data that many Facebook users do not necessarily even know they have placed into public domain, though lately at least part of the user population seems to be growing up to data ownership and privacy issues.
2. Searching Facebook posts not publicly accessible - this requires that one log in, but provides a deeper access to the Facebook "graph" that connects various Facebook objects including messages, groups, pictures, links etc. all together into a structure that can be queried via a REST-ful API.

We implement a very simple version of (1) in the code below. Again, we note that mining data here can have various practical applications, such as for example, performing sentiment analysis of the user population towards world or local events e.g. the crisis in Europe or Greece, the Arab Spring, elections in the US, the price of oil, Madonna's performance during the Super-Bowl etc., Some sentiment analysis can even be used to help with marketing of products and services and even for applications like investment management. There have been news-stories of how sentiment analysis was used to predict the direction of Netflix stock.

Our implementation stops short of performing the actual sentiment analysis because we have already implemented simple sentiment analysis in our earlier Twitter post. The same approach can be replicated here by the interested reader with minimal effort. Several additional enhancements can also be made if (2) above is used to determine how "connected" a post-writer is to the rest of the Facebook graph (we can do this in the Twitter context using the number of followers one might have). Facebook also offers additional media like pictures that can be also used to add additional context to the story.

One issue we face while performing sentiment analysis in the Facebook context that we do not see with Twitter comes from the fact that Facebook posts tend to be longer on average and are not limited to the 140 characters of a typical Twitter micro-blog tweet. This means that even our simple sentiment analysis algorithm needs to be tweaked to compute the overall sentiment of a post by calculating the relative percentage of positive, negative, and neutral sentiment key-words, and then interpret these in the larger context of the post. Similarly an additional hurdle we face here is that larger posts offer greater capacity for one to express his/her creativity, and that might mean there are more posts that are sarcastic, satirical etc in nature, and text-based analysis unless very sophisticated, is likely to miss these nuances in meaning, making things more difficult from a classification stand-point.

Code for simple Facebook data-mining is posted below, for a sample query with the key-words "quantitative easing" and the generated output file. Enjoy!

Some other issues with the code (an optimist might have titled this section "Future Work" or "Next Steps"):

1. This is a very simple, unpretentious implementation focused on the core issue of mining Facebook posts for data and parsing the results into a human-readable, usable input form for sentiment analysis. It can easily be made much more sophisticated, but we just hit the highlights here and move on to other things.
2. I did not build in a processor for special characters in the larger unicode data set. So these appear as noise in the output.
3. I do not check for messages that repeat and filter them out, with good reason. Sometimes messages with minimal changes are re-posted by other people, sometimes with, and sometimes without attribution to the original post. I guess the general rules about plagiarism vs. original thought do not apply as much to social media. 

Sample Source Code:

import os, sys, urllib2; # include standard libraries of interest


# function that takes two lists as input, reads them,
# then returns a list of tuples (x,y) where the x is from the first
# list, and the second element y is the smallest number larger than x
# from the second list. we use this as a helper function to parse the
# output of the query to Facebook.
def L(a,b):  
 r=[];
 for i in a: 
  t=[j for j in b if j>i+2][0];
  r+=[(i+2,t)];
 return r;


# program sample usage is "python fbmine.py "quantitative easing" qe2.txt
# here fbmine.py is this source code file
# "quantitative easing" is the string of space separated keywords we mine for
# qe2.txt is the output file generated by this data-mining exercise.
wrds=sys.argv[1]; # wrds is the string of words we want to filter for
wrds=wrds.split(" ");
s="";
for i in wrds[:-1]: s+=i+"%20"; # populate the query 


s+=wrds[-1];
#print "query: http://graph.facebook.com/search?q="+s+"&type=post&limit=1000\n\n"; # create the query string and launch it
req=urllib2.Request("http://graph.facebook.com/search? q="+s+"&type=post&limit=1000");
response=urllib2.urlopen(req); # collect the query results
txt=response.read();
txt=txt.replace("\\n","").replace("\\",""); # some simple cleanup of read data


p=txt.split("\"");
m1=[i for i in range(len(p)) if p[i]=="message"]; # parsing the messages
m2=[i for i in range(len(p)) if p[i]==","];
R=L(m1,m2); # using the helper function
g=open(sys.argv[2],"w"); # generating and writing out the output
for i in R: 
 s="";
 for j in range(i[0],i[1]): s+=p[j]+" \n";
 g.write("-----------------------------------------------------------------\n");
 g.write(s+"\n");


g.write("------------------------------------------------------------------\n");


Sample Output File: (file was generated around 1815 hrs Friday Feb 10 2012)

--------------------------------------------------------------------------------
The Bank of England has announced another round of 'quantitative easing', this time printing u00a350 billion of money.Keep it up lads; at this rate soon we'll all be billionaires, just like everyone in Zimbabwe.Turns out that smashing a stake through a vampire's heart works, even if your neighbours cat's not a vampire. 


--------------------------------------------------------------------------------
The Bank of England has announced another round of 'quantitative easing', this time printing u00a350 billion of money.Keep it up lads; at this rate soon we'll all be billionaires, just like everyone in Zimbabwe. 


--------------------------------------------------------------------------------
Neat, expression, So why the blithering flip.....Very interesting article on printing money..  It's English, but applies equally here, I think:  (Be sure to read the last link in article)http://blogs.telegraph.co.uk/news/danielhannan/100136397/quantitative-easing-has-failed-and-failed-again-what-madness-has-seized-our-leaders/ 


--------------------------------------------------------------------------------
The Bank of England has announced another round of 'quantitative easing', this time printing u00a350 billion of money.Keep it up lads; at this rate soon we'll all be billionaires, just like everyone in Zimbabwe. 


--------------------------------------------------------------------------------
just saw ths funny joke....... The Bank of England has announced another round of 'quantitative easing', this time printing u00a350 billion of money.Keep it up lads; at this rate soon we'll all be billionaires, just like everyone in Zimbabwe. 


--------------------------------------------------------------------------------
http://www.zerohedge.com/news/obama-revises-cbo-deficit-forecast-predicts-110-debt-gdp-end-2013quantitative easing is not the panacea that Obama is hoping for 


--------------------------------------------------------------------------------
The system is FRAUD! 


--------------------------------------------------------------------------------
The Bank of England has announced another round of 'quantitative easing', this time printing u00a350 billion of money. Keep it up lads; at this rate soon we'll all be billionaires, just like everyone in Zimbabwe. 


--------------------------------------------------------------------------------
The bank of england has just announced another round of 'quantitative easing', this time printing u00a350 billion in notes.Keep it up lads, at this rate we'll soon all be billionaires. Just like everyone in zimbabwe. 


--------------------------------------------------------------------------------
u2018u201cQuantitative Easing is a transfer of wealth from the poor to the rich,u201d he says, u201cIt floods banks with money, which they use to pay themselves bonuses. The banks have money, and assets, so they can borrow easily. The poor guy, who is unemployed and can't borrow, is not going to benefit from it.u201d The QE process pushes asset prices up, he says, which is great for those who own stocks, shares and expensive houses. u201cBut the state is subsidising the rich. It is the top 1 per cent who benefit from Quantitative Easing, not the 99 per cent.u201du2019 -- Nassim Taleb 


--------------------------------------------------------------------------------
Quantitative easing is now more vile on the lips than any four letter word http://tgr.ph/zNpxTg 


--------------------------------------------------------------------------------
http://blogs.telegraph.co.uk/news/danielhannan/100136397/quantitative-easing-has-failed-and-failed-again-what-madness-has-seized-our-leaders/ 


--------------------------------------------------------------------------------

[...] I've truncated this to save space.

On the design of Recommender Systems

Recommender Systems or Recommendation Systems (henceforth RS) are the systems used in many popular websites today to drive up traffic, sales, and overall customer satisfaction. These are used successfully in many Internet Services websites like Amazon, Netflix etc., to generate more revenue. When implemented and used correctly, these systems can massively impact business metrics driving up growth, revenues, and yes, even profitability (though this last metric also depends on other business parameters). In this blog post, we study some design factors involved in the construction of such systems.


Disclaimer: we do not claim any of these ideas below are original. We will try and add references later for some of the more important ideas, as time permits, to help the interested reader along a voyage of discovery.


1. Frequent Itemsets
This idea comes from the field of marketing analytics. Did you know that beer and baby diaper sales in the US are highly correlated? Apparently when dads go (or are sent) to the nearby store to pick up baby diapers, they take it upon themselves to restock on their beer to make better use of the trip, help save the environment (drive to store once, buy more things ...), etc. Stores that have customer loyalty programs can pick up on these kinds of trends more easily, since they know the content of most "shopping baskets", and can decide which sets of items (called frequent itemsets), go together most often, and are purchased most frequently. This way, they can decide to upon appropriate marketing strategies to maximize their revenue - e.g. have sales on both beer and diapers at the same time, or say give out larger discounts on diapers than neighboring stores, but hike up the price of beer to compensate etc.,


Finding and tracking frequent itemsets is something of an art form, and requires data mining and statistical analysis. Different firms do this differently with different levels of sophistication, and more complex methods are not necessarily better all the time...


Online stores can capitalize on this idea in other different and interesting ways. An RS for Amazon or other online store can for example direct people who have purchased certain items, to other items people with similar purchasing histories may have bought or may have considered buying (e.g. by tracking their page views). Here, the website is using information about customers and prospective customers to guide others along the same path. 


The logic goes: "Buying a toy? Perhaps batteries are needed. 95% of people buying this toy also bought batteries at the same time. And oh, 40% of those buying this toy wanted this cool rubber casing with it too. And did you consider how much nicer this expensive toy would be with this mod so many others like to buy? ... " and so on. 


Or... like "Cool Hand Luke"? Maybe you will like other movies that people who liked this movie will like? Perhaps it is more likely you will like movies that others liked if they also liked most movies that you say you liked, and less of the movies you say you do not like? (this is where the user ratings come in handy at Netflix, so your "basket" is the set of all movies you have rated, and can be compared with other baskets to find those that have similar characteristics to locate those that have other items your's does not have, and recommend these as movies to watch).


Not too intrusive (not overtly anyway), but helpfully plugging just the right products for you to find. And of course, there is a search facility that lets you find not just what you need, but multiple options for similar things, all neatly indexed in decreasing order of potential relevance, with the option for you to sort things along other parameters you might like.


2. The Wisdom of Crowds
Ever wonder what makes Amazon.com so much more successful than other book stores with an online presence? A key factor is the facility that enables customers to share their experiences about a product or service sold through the store-front. For instance, if on site A, I can read all about a book I want to buy, see other customers' reviews of the same, see customer posted product pictures, also see other vendors' prices with the ability to comparison shop, and share my feedback either positive or negative with the larger body of consumers, why would I not pick this site over competitors', especially if I can also get better deals there?


MBAs are usually taught that some platforms are "multi-sided markets" (think credit cards, or development APIs for example). Developing such platforms from the ground up can be a challenge, because you need to simultaneously grow all communities around the platform. But once there is sufficient interest and a core ecosystem becomes functional, it takes off in a virtuous cycle and things can grow very rapidly and the business takes off. Of course, in an environment with increasing "clock-speed" (reduced cycle times), successes and failures typically become evident very quickly as well. Agile companies can just as quickly increase investment in ideas that seem to work, and kill those that seem to be doing badly. But we digress...


With the advent of media like Facebook and Twitter, many websites now permit users to share their purchases with friends from those and other communities. This creates a following... "I am more likely to like things my friends like, so perhaps I should check out the things they are buying..." and so on. This is kind of a subliminal recommendation system. Works on the sly. See model (5) below for more.


Wikipedia is, to date, perhaps the best positive example of the wisdom of crowds. But even there, the truly wise are very few... and there are far far more readers than writers. The same applies to product ratings. Most people will at best, only rate a product. People that write reviews will be a much smaller number. And those that do this without a hidden motive (there have been several reported instances of restaurants reviewing themselves over Yelp!, of authors reviewing their own books glowingly on Amazon etc) would be an even smaller subset.


3. Free Samples for All
This builds on ideas from (1) above. So much better to give people the option to "try before you buy". Consumption of books, movies, songs etc. require an investment of time, money, effort on part of the consumer. Can you make them understand that the 2 hrs it takes to watch this movie, the $12.95 it takes to buy it, is actually worth it, as opposed to, say doing something else with that money and time? Give them a free preview. Tell them "no pressure, we think this is something you'd like, and as you can see, it is really not that expensive. Check out how much other people are selling it for. And look how much other people like you seem to like it! just buy it now from us, and don't worry about it till it is time to pay your credit card bill". That's what free samples do. Of course, occasionally you will have free-loaders that will take your samples and never buy, but that's a chance you have to take.


4. A Thematic Match
Sometimes, it is also convenient and useful for systems to generate a thematic match. If you like certain movies for example, rather than look for movies that others who liked your favorites have watched (which requires gobs of data), why not recommend other movies with similar thematic elements that will in all likelihood interest you? Or perhaps you liked the movies you liked because of the actor or actors in them? So other movies with the same "elements" - defined as actors, story lines etc that are similar might interest you? Of course to find exactly what makes someone like a certain movie requires some deep statistical analysis of what similar elements exist across their viewing history, or (here's a novel idea!) asking them to tell you what kinds of movies they like. "Do you like to watch mysteries frequently? sometimes? never? What about dark, gritty, thrillers?" 


Thematic match is an interesting scheme that can get results quickly with more information from the public domain, and some patient customer prodding. Easier to get started with this, build a community of loyal users, then exploit the data they leave behind as they engage more actively with your website giving you more data to mine with models (1) and (2) above, giving you more sales, encouraging your content suppliers to give you more content with free samplers - model (3) - (now that your ecosystem is humming along), and so on...


5. Link to Social Media
Think also of social media used to create a buzz. This is a key new development in our age. "OMG! I just read Girl With The Dragon Tattoo and loved it!" someone tweets or posts on Facebook. And immediately her network of 132 people see this, some of whom will either buy or borrow this book and read it. Things go viral fast. Used to be that it takes years to build a reputation that takes only a moment to destroy. It seems these days you can build and destroy reputations (ok, marketing buzz) in minutes... and you can amplify this effect if there are groups set up around certain themes, because then the uptake for anything posted into this forum would be very high, and you could get a large spike in volumes (either sales or whatever else, depending on media) very quickly.


6. The Human Unchained
Most importantly of all, unleash the human within your consumer. Exploit their need to feel heard, to talk, to feel good about what they have found that makes them smarter, wiser, more beautiful, special in their own way when they compare themselves with those around them. Encourage them to "like" products. Use them to describe their experiences using these products. Then mine these descriptions for statistically improbable phrases (SIPs - see the post on tf-idf for more) that more likely and more readily associate themselves with particular products. Use these words or phrases to help you with your thematic match (model 4 above).


Captchas were a great invention to prevent bots from harvesting Internet information for unscrupulous use. However, crafty websites can leverage human intelligence by requiring humans to solve a "flow through" captcha to unlock information from the original website for bot consumption. These and related ideas can be used both for good and bad... so caution is warranted. 


Good implementations will mine data in the aggregate, or, if they use data tied to particular individuals, will irrevocably destroy the link between the identifying characteristics of the individual in question and the data set that pertains to them. Either of these conditions must be met for safe implementations of data mining for user-centric analytics.


Other examples of human factors use in similar systems: 


In India, the police have taken to using Facebook to permit people on the road to report traffic violations involving other people's vehicles. Photographs or video of offenders can be posted online via Facebook or other social media sites, and the law enforcement machinery will take action as and where deemed necessary. Be careful, Big Brother is watching you, and your big brothers are your fellow citizens - in a more than figurative fraternal sense.


Want to hear a weather report for free? Call us, then hear an ad and tell us what you think, service is "free".


7. Putting it all together
As we have remarked over the course of this discussion, some elements require less data and less user participation than others, and can be built more easily. Then, as one's business grows, one can leverage the larger data set gleaned from the user base to build more sophisticated analytics to better exploit their information to provide better service to increase loyalty, lock in these customers by increasing barries to switching, or provide deals tailored to consumer segments that make it more attractive for them to return time and again.


Sadly, building these kinds of systems, even rudimentary ones, requires a rather substantial amount of data, and this data is not easily available to people like us who are interested in exploring the leading edges of technology, so for now, we close this post with out a sample code while expressing the fond hope that when such data becomes available more freely (after all, it is only aggregate data, doesn't really violate privacy), we might revisit the discussion to provide a sample implementation of at least some of the above.

Genetic Algorithms

Conway's game of life simulates the behavior of a colony of living beings represented by pixels in a plane using a set of simple rules. It is amazing the complex interactions that result from such simple implementations. The Langton Ant is another such creation (for those interested, there is a not too simple Project Euler problem involving this). These examples of what we might generally interpret as "artificial life" are interesting, but can ideas like this be used to solve real problems?


Genetic Algorithms (GA for short henceforth) emulate the propagation of life in an attempt to leverage randomness and simple rules of reproduction and mutation to solve difficult problems more easily in some cases than more traditional techniques. These belong to a class of what are commonly referred to as Randomized Algorithms, which includes mathematical approximations of other physical phenomena as simulated annealing for example ("annealing" is the science of gradually cooling glass from its molten state when it is blown, to room temperature without fracturing it in the process). 


Genetic Algorithms have various applications in solving complex dynamic optimization problems, etc, but to illustrate the principles and have some fun in the process, we use these to solve simple Sudoku puzzles in our implementation below. As almost everyone knows, Sudoku is a mathematical puzzle whereby one is presented with a 9x9 grid of cells, some with numbers filled in. This grid is overlaid by a 3x3 grid of cells where each of the 3x3 grids is composed of the smaller 3x3 cells. The goal is to fill in the entire grid with numbers subject to the condition that every 3x3 grid uses the numbers 1 through 9 only once, with the same condition applying to each row and each column of the original 9x9 grid as well. There are thus a total of 9+9+9=27 conditions to the problem, and we can solve this effectively through constrained optimization or through creative use of GAs.


One issue with GAs is that given they are a randomized process, the time to convergence to a complete solution cannot be guaranteed. We see this with our implementation - simple Sudoku puzzles are solved easily by our program, but for the more devious or "evil" level ones, the program thrashes around trying to find a solution, but convergence is very slow. Performance can be improved a lot by building a hybrid method - i.e. employ mathematical or other logical heuristics to fill in some other cells in the harder problems before handing it off to the GAs to solve, to ensure faster convergence, but we do not do that here because our focus is on building a sample implementation of GAs, not boiling the ocean. So, let's stick to the idea at hand, and get right to solving the problem.


How to solve Sudoku with GAs? Here is the approach we will use:

1. generate a "board" in string form. this is a string that is 81 characters long, with numbers where there are numbers, and "x" elsewhere to denote empty spaces. a correctly solved board should have all digits from 1 to 9 exactly 9 times, so the sum of the digits in the string in a solved board must always equal (1+2+...+9)*9 =45*9=405.
2. "unfold" the string to gather all constraints into a sequential string - this string now has 81+81+81 characters (the first 81 indicates the row constraints, the second 81, the column constraints, and the last 81, the block constraints) for a total of 243 characters.
3. generate random "chromosomes", let's say 1000 at a time for our base gene pool. these chromosomes fill in the "x" locations from our base gene in (2) with numbers from 1 through 9, randomly. collect these chromosomes. collect only those chromosomes that meet the requirements of a proper solution - let's say the sum of all digits within should be 405. more stringent conditions here will lead to better chromosomes that take longer to compute. lenient conditions here will generate worse chromosomes that are computed quickly.
4. rank the chromosomes in the gene pool based on how well they approximate what might be a correct solution to the Sudoku problem - are all digits used 9 times each, none more, none less? is the grid sum close to 405? what conditions we use here in the "fitness" constraint depend on what conditions we used in (3) above in the gene pool generation process.
5. after the gene pool is created and chromosomes ranked for fitness, use Darwin's idea of "survival of the fittest" to keep only the top 25% of the pool, discarding the rest. then, use mutation and crossover to generate the next version of the pool.
6. at each iteration of the pool, check to see if any chromosome meets all the criteria of the correct solution. if it does, then that chromosome is the correct solution to the puzzle and we stop there. if none does, keep iterating with more generations of the gene pool till a complete solution is found.
7. print the final solution and exit.

Before going too far though, we first have to explain what mutation and crossover are. Mutation is a small change in the chromosome. Some small subset of bits can be changed arbitrarily - i.e. some digits may be randomly changed to other digits in one or more locations in the chromosome. Crossover is a simulation of sexual reproduction. We take two chromosomes (call them "parents") and generate two off-spring from them by slicing the parents into parts and splicing these parts together keeping in mind the required length constraints of the generated off-spring. Recall from (5) above that we only allow the top 5% of the gene pool to reproduce. What % of the gene pool is newly randomly generated, vs. generated by mutation or by crossover is a design choice, and some tweaking here with a view to optimizing run time, could greatly enhance the performance of the GA implementation.


Code follows along with a sample input and output file. A couple of optimizations can be made to the code below to make it even more efficient. For instance, each new chromosome can be generated by first filling in the empty spaces with the smallest number of options available, then moving on to the harder empty cells, just like humans solve the puzzle. This is left as an exercise to the reader :-)



import os, sys, operator;
from itertools import *;
from random import *;


def getCol(x,n): # get column n from grid x
 r=[];
 r+=[i[n] for i in x];
 return r;


def mkInt(c): # convert all numbers into ints in a list
 r=[];
 for i in c: r+=[[int(j) if j!='x' else j for j in i]];
 return r;


def genConstraints(x):
 # collect the constraints now
 constraints=[i for i in x]; # horizontal constraints
 for i in range(9): constraints+=[getCol(x,i)]; # vertical constraints
 # finally, the block constraints
 b=[[0,1,2],[3,4,5],[6,7,8]];
 for i in product([0,1,2],repeat=2):
  p,q=i;
  #print "p,q => ",p,q;
  c=[];
  for i in b[p]:
   t=[];
   for j in b[q]: t+=[x[i][j]];
   #print t;
   c+=t;
  constraints+=[c];
 # now we have all 27 constraints: 9 horizontal, 9 vertical, 9 block
 return mkInt(constraints);


def mkGrid(s): # convert a puzzle string to a grid
 r=[];
 for i in range(9): r+=[s.split(",")[i*9:(i+1)*9]];
 return r;


def grabDigit(x): # get a random digit from a list of digits
 shuffle(x);
 return x[0];


def genChr(x): # generate a chromosome
 r=[];
 for j in range(9):
  nums=[int(k) for k in x[j] if k!='x'];
  missing_nums=list(set(range(1,10)).difference(set(nums)));
  t=[];
  for i in range(9): 
   if x[j][i]!='x': t+=[int(x[j][i])]
   else:
    m=list(set(fx[(j,i)]).intersection(set(missing_nums)));
    if len(m)==0: m=fx[(j,i)];
    a=grabDigit(m); 
    t+=[a];
    if a in missing_nums: missing_nums.remove(a);
  r+=[t];
 return r;


def validChr(x): # is it a valid chromosome? not used for efficiency
 #for i in range(9): 
 # p=getCol(x,i);
 # if sum(p)!=45: return False;
 # if list(set(p))!=9: return False;
 return True;


def scoreChr(x): # score the chromosome
 t=genConstraints(x);
 score=0;
 for i in t: 
  if len(list(set(i)))==9: score+=1;
  #if sum(i)==45: score+=1;
 return score;
  
def printGrid(x): # print the grid 
 for i in x: 
   print " ".join(map(str,i));
 return;


def xover(a,b): # cross-over two chromosomes, get two descendants
 splice_loc=randint(1,7);
 ta=a[:splice_loc]+b[splice_loc:];
 tb=b[:splice_loc]+a[splice_loc:];
 return (ta,tb);


def xover2(a,b): # another method for cross-over
 speed=randint(1,6);
 ta,tb=a[:],b[:];
 for j in range(speed):
  x_loc=randint(1,7);
  t=ta[x_loc]; 
  ta[x_loc]=tb[x_loc];
  tb[x_loc]=t;
 return (ta,tb);


def mutate(a): # mutation
 speed=randint(1,6); # how many mutations in one go
 for i in range(speed):
  gene_seg=randint(0,8); # which gene segment to change
  x=genChr(g);
  a[gene_seg]=x[gene_seg];
 return a;   


p=open("s4.txt","r"); # open the puzzle file
pc=p.readlines(); # read it
pc=[i.replace("\n","") for i in pc];
pstr=",".join([i for i in pc]);
g=mkGrid(pstr);
mx=genConstraints(g);


# collect all the constraints by cell... 
# find which numbers might fit in each cell. use it for
b=[[0,1,2],[3,4,5],[6,7,8]];
cx,fx={},{};
for i in range(0,9):
 for j in range(0,9):
  for k in range(0,3):
   if i in b[k]: x=k;
   if j in b[k]: y=k;
   block_id=x*3+y;
   cx[(i,j)]=(i,9+j,18+block_id);
   fx[(i,j)]=list(set(range(1,10)).difference(set(mx[i]).union(set(mx[9+j])).union(set(mx[18+block_id]))));
# now fx is a dict that contains all possible values for each empty cell
t=fx.values();
for i in range(len(t)):
 if len(t[i])==1: 
  posx,posy=fx.keys()[i];
  if g[posx][posy]=='x': g[posx][posy]=t[i][0];


# all constraint strings must have all digits from 1 to 9 just once
# all constraint strings must add up to 9*10/2=45 
poolsz=5000; # size of gene pool
gene_pool=[];
while len(gene_pool)!=poolsz: # generate chromosomes to fill pool
 seed();
 t=genChr(g);
 while not validChr(t): t=genChr(g);
 if t not in gene_pool: gene_pool+=[t];


seen=gene_pool[:]; # keeps track of all seen chromosomes


# set the parameters for new generations
retain_pct=0.05;
mutate_pct=0.35;
xover_pct=0.55;
new_dna=1-retain_pct-mutate_pct-xover_pct;
generation,solved=0,0;
scores=[]; # store best scores in each generation


# solve the puzzle
while solved==0:
 genes=[];
 for i in gene_pool: genes+=[(i,scoreChr(i))];
 genes=sorted(genes,key=operator.itemgetter(1),reverse=True);
 if genes[0][1]==27: 
  print "puzzle solved";
  printGrid(genes[0][0]);
  solved=1;
 else:
  if len(scores)>3 and len(list(set(scores[-3:])))==1: 
   seed(); 
   jumpahead(randint(1,100000));
   poolsz=randint(poolsz,poolsz+500);
   retain_pct=0.1;
   mutate_pct=round(uniform(0.25,0.3),2);
   xover_pct=0.95-mutate_pct;
   new_dna=1-retain_pct-mutate_pct-xover_pct;
  print "generation: ",generation,"pool size: ",len(genes)," max score: ",genes[0][1];
  #printGrid(genes[0][0]);
  scores+=[genes[0][1]];
  generation+=1;
  seed();
  chr_retained=int(poolsz*retain_pct);
  new_pool=[j[0] for j in genes[:chr_retained]]; # 250 genes to retain
  for k in range(int(xover_pct*poolsz/2.)): # generate 450 cross-over genes
   seed();
   a,b=new_pool[randint(0,len(new_pool)-1)][:],new_pool[randint(0,len(new_pool)-1)][:];
   toss=randint(0,1);
   if toss==0: ta,tb=xover(a,b);
   else: ta,tb=xover2(a,b);
   if ta not in seen: new_pool+=[ta];
   if tb not in seen: new_pool+=[tb];
  for k in range(int(mutate_pct*poolsz)): # generate 150 mutated genes
   seed();
   a=new_pool[randint(0,len(new_pool)-1)][:];
   ta=mutate(a);
   if ta not in seen: new_pool+=[ta];
  while len(new_pool)<poolsz: # new genetic material
   seed();
   ta=genChr(g);
   if ta not in seen: new_pool+=[ta];
  gene_pool=new_pool[:];
  seen+=gene_pool[:];


sys.exit(0);


  
Input File: 
7,9,x,x,x,x,3,x,x
x,x,x,x,x,6,9,x,x
8,x,x,x,3,x,x,7,6
x,x,x,x,x,5,x,x,2
x,x,5,4,1,8,7,x,x
4,x,x,7,x,x,x,x,x
6,1,x,x,9,x,x,x,8
x,x,2,3,x,x,x,x,x
x,x,9,x,x,x,x,5,4




Output File:
generation:  0 pool size:  5000  max score:  12
generation:  1 pool size:  5000  max score:  15
generation:  2 pool size:  5000  max score:  17
generation:  3 pool size:  5000  max score:  19
generation:  4 pool size:  5000  max score:  22
generation:  5 pool size:  5000  max score:  25
generation:  6 pool size:  5000  max score:  25
generation:  7 pool size:  5000  max score:  25


puzzle solved
7 9 6 8 5 4 3 2 1
2 4 3 1 7 6 9 8 5
8 5 1 2 3 9 4 7 6
1 3 7 9 6 5 8 4 2
9 2 5 4 1 8 7 6 3
4 6 8 7 2 3 5 1 9
6 1 4 5 9 7 2 3 8
5 8 2 3 4 1 6 9 7
3 7 9 6 8 2 1 5 4