One word review: visionary

This is my review of the book "Zero to One - Notes on startups , or how to build the future" by Peter Thiel. Its quite an ambition title, but the book delivers on its promise (except the last two chapters with the weird illustrations) . I was excited to read this book primarily because of its author. Peter Theil is co-founder of Paypal (which recently separated from eBay and went IPO) and Palantir and was an early investor in Facebook. He is a extremely successful venture capitalist, his firm Founders Fund has an impressive portfolio including Strip and ZocDoc (ZocDoc being one of the most promising health tech startups to come out of New York city in a while).

The main premise of the book is to reinforce the belief that investing in technology (not just computers) will lead to a better future. The book has lots of nuggets of wisdom, but here are my favorites:

1. To go from 0 to 1 is to build something new: To go from 1 to n is to iteratively improve or build upon existing technology. Going from 0 to 1 will lead to a better future, going from 1 to n turns you into HP or Microsoft.
   
2. Chance has very little to do with success (sorry Malcolm Gladwell) :  People succeed not necessarily because of their upbringing but because they rise to the occasion, invent and work hard.
3. The geek shall inherit the world. But the geek must learn to work with others: Only a classic piece of literature could be made in isolation. To build an industry you need a team.
4. The smaller, the more focused the team the greater the chances of success: This is something I 100% agree with. The agile software manifesto also talks about the same notion.
   
5. To be weird, peculiar and unique is good: Geeks are weird, socially awkward, sometimes plain crazy. They defy conventional wisdom and this is why they take the less beaten path and succeed. They are less vulnerable to preconceived notions. They are less likely to repeat other peoples mistakes.
   
6. Everyone sells: Engineers must learn not to underestimate the importance of sales and delivery. No matter how good your product is, you still need to convince people to use it.
7. Monopoly is a good thing, undifferentiated competition is bad: A startup must choose a specific user base (Paypal for example chose eBay sellers) and dominate that space and then look to expand. Facebook chose Harvard students, Tesla chose the the luxury green market.
8. Planned Optimism is the key to the future: Believe in miracle of technology, but have a plan. A bad plan is better than no plan. To be agile means to adapt. But you still need to have a plan. It was unplanned optimism that lead to the dot com bubble.
9. Build a valuable company that no one is building: A company should add value but must also be valuable. This basically means that your company must have a useful product but must also generate revenue. People must be willing to pay for your product.
10. A framework to evaluate your startup/idea/project
    1. Is it innovative? This is the key!
    2. Is now a good time for this product?
    3. Will it be a monopoly in a small segment?
    4. Do you have the right team?
    5. Do you have Sales and Delivery?
    6. Will your product last? Or will an existing big player make it worthless. This is a crucial point and reminds me of a bunch of e-commerce startups that failed.
       
    7. Do you have a secret? Does your product have a killer feature that no other product in the market have?
       

Overall I would strongly suggest technology enthusiasts read this book. It is not a very long read and this book will make you think and invent and believe in the power of technology.

This article is meant to be an introduction on Multi Arm Bandits, without getting into too much  into the mathematical details (I'll leave that for a followup article!). We'll talk about reinforcement learning, multi arm bandit optimization and the exploration/exploitation trade off.

What is Reinforcement Learning?
From Wikipedia : "Reinforcement learning is an area of machine learning inspired by behaviorist psychology, concerned with how software agents ought to take actions in an environment so as to maximize some notion of cumulative reward." . Let us break this definition down:

• Reinforcement Learning Maps situations to actions to maximize a numerical reward.
• Unlike supervised learning, the learner is not told which actions to take but must discover which actions yield the most reward by trying them.
• Highly useful in cases of significant uncertainty about the environment

In Reinforcement learning an agent simultaneously attempts to acquire new knowledge (called "exploration") and optimizes its decision based on existing knowledge (called "exploitation"). Multi Arm Bandits is a class of sequential resource allocation that embody the exploration/exploitation dilemma.

What are Multi Arm Bandits (MAB)?
“Bandit problems embody in essential form a conflict evident in all human action: choosing actions which yield immediate reward vs. choosing actions (e.g. acquiring information or preparing the ground) whose benefit will come only later” - P. Whittle (1980).
MAB is best understood through this analogy:
A gambler at a row of slot machines has to decide which machines to play, how many times to play each machine and in which order to play them. When played, each machine provides a reward from a distribution specific to that machine. The objective is to maximize the sum of rewards earned through a sequence of lever pulls.

Some real world exploration/exploitation examples:
Restaurant Selection

• Exploitation : Go to your favorite restaurant
• Exploration: Try a new restaurant

Oil Drilling

• Exploitation : Continue using existing well
• Exploration: Drill at a new location
  

Online Banner Advertisements

• Exploitation: Show the most successful advert
• Exploration :Show a different advert
  

Lets get formal and introduce some notation (but not too much!):
•Lets Index the arms by a, and the probability distribution over possible rewards r for each arm a can be written as pa(r) .
• We have to find the arm with the largest mean reward  μa=Ea[r]
•In practice pa(r) are non-stationary

So how does one come up with an optimal (albeit approximate) strategy to explore and exploit so as to reap maximum rewards? There are two classes of well known strategies in literature:

• Greedy :  the best lever (based on previous trials) is always pulled except when a (uniformly) random action is taken. A popular example of a Greedy strategy is called Epsilon Greedy.
  
• Probabilistic Matching : the number of pulls for a given lever should match its actual probability of being the optimal lever. Example: Thompson Sampling
  

Lets look at both these options briefly:

Epsilon Greedy
Select the best lever most of the time, pull a random lever some of the time (show random ads sometimes, and the best
ad most of the time). In this strategy we choose to pull a new lever (explore) with a frequency of epsilon (hence the name). Hence epsilon is the fraction of times we sample a lever randomly and 1- epsilon is the fraction of times we choose optimally. An epsilon value of 1.0 will cause it to always explore, while a value of 0.0 will cause it to always exploit the best preforming lever.

Key Advantages:

• Very easy to implement.
  
• Will not get stuck in some local optimal state.
  
• The best performing arm will be used most of the time.
  

Disadvantages:

• How do you pick the value epsilon? This is a tricky problem to solve and the wrong epsilon value could lead to either 0 exploration or too much exploration.
  

Thompson Sampling

Thompson Sampling is a randomized algorithm based on Bayesian ideas. The first version of this Bayesian heuristic is more than 80 years old, dating to Thompson (1933). It is a member of the family of randomized probability matching
algorithms. The basic idea is to assume a simple prior distribution on the underlying parameters of the reward distribution of every lever, and at every time step, play a lever according to its posterior probability of being the best arm.

In other words, we encode our belief about where the expected reward μa is for lever a in probability distribution  p(μa|data). For example, if each lever is an advert, p(μa|data) could be the probability distribution of the mean CTR of the advert given historical data about the advert. When the reward is a binomial (click Vs no click) a Beta-Binomial model is usually a convenient choice.

Key Advantages:

•  Easy to implement.
  
• Robust against delayed feedback: Often feedback about rewards is not immediately available. Imagine each lever being a product on sale on an eCommerce site. The reward is sold Vs not sold. The knowledge that a product was sold may not be immediately available to the bandit system. In this case, Thompson Sampling (being randomized) will keep exploring (because its randomized) instead of being stuck showing a sub performing product.
  

Disadvantages:

• Exploration may cease to exist if the algorithm converges quickly. Continuing with the previous example, a product that gets a few sales may continue getting more sales (simply because its shown more) and may overwhelm new products for being shown. Thompson sampling hence needs careful tuning and experimentation.
  

That's it for now! I will follow up this article with a deeper look into Thompson Sampling and performance evaluation of Bandit Algorithms.

References

1. Kuleshov, Volodymyr, and Doina Precup. "Algorithms for multi-armed bandit problems." arXiv preprint arXiv:1402.6028 (2014).
   
2. Chapelle, Olivier, and Lihong Li. "An empirical evaluation of thompson sampling." Advances in neural information processing systems. 2011.
   
3. Agrawal, Shipra, and Navin Goyal. "Analysis of Thompson sampling for the multi-armed bandit problem." arXiv preprint arXiv:1111.1797 (2011).
   
4. https://en.wikipedia.org/wiki/Multi-armed_bandit
   

As an avid user of Reddit, I was inspired to study the network structure of Reddit for a  social network analysis class. 

Reddit is a social news website driven by user content. Reddit is a data-rich website with a complex network structure.  Reddit comment threads may trail for more than two weeks and one single post can easily exceed 1000 comments, which are mainly replies to other comments rather than direct responses to the original posts. There is hence an implicit relationship based on shared interests between the comments, and between the comment and the post, which can be used to construct a social network.

Step 1: Data Collection
Currently no large Reddit datasets exist. Thus a key part of this project was to crawl Reddit and retrieve the content. There are three parts to crawling Reddit:
1. Get list of subreddits
2. Get list of submissions for each subreddit
3. Get content and comments for each submission

Reddit’s threaded comment system provides the most interesting data. Each comment contains the user, a timestamp, a list of replies in the form of comments, and the score (up votes minus down votes) for that individual comment. At the end of the crawling phase, I collected the profiles of 229254 users, with 696165 comments from 6864 posts.
The crawler was written using Python and the PRAW library. PRAW, an acronym for “Python Reddit API Wrapper”, is a python package that allows for simple access to Reddit’s API. PRAW aims to be as easy to use as possible and is designed to follow all of reddit’s API rules. 

Step2 : Visualizing the Discussion Structure : Radial Tree to the Rescue

Even though Reddit has a convenient interface for participating in discussions, the ability to examine the structure of the comments from the comment list is very limited. However, a special tree representation (as shown in [Gomez et. al.] for the post comments provides a convenient way to visualize the discussion structure. The central node is defined as the post itself. Any comments made directly on this post are attached as children in a radial pattern around this central node. Nested comments are attached similarly to their parent until the entire comment tree is visible. This tree structure grows outward from the central node as the discussion takes place over time. The figure below shows a fairly popular post that received over 750 comments represented with the radial tree structure. The next figure shows a post with a similar number of comments, however, this post has very few discussions reaching deeper nesting levels, and almost all of the comments appear as direct replies to the post. 

The structure of the trees is highly heterogeneous. For some posts, the tree reaches a high depth with very few comments due to intense discussion among a few users. In other posts, there are hundreds of comments in the first two nesting levels and very few outside of that. Sometimes the majority of the discussion actually happens in one of the child threads and the tree has a skewed appearance. 

Next, we plot the distribution of comment depths for all posts. As you can see, the majority of comments are made in the first few nesting levels, however, we can see that there is a substantial amount of discussion going on in the deeper levels.

Step 3: Measuring Controversy

What is Reddit without controversy? But how exactly do we capture "controversy"? Reddit allows you to sort posts in several ways. “Top” lists the most popular posts by number of comments, “Hot” lists recently popular posts, and “Controversial” lists posts with a lot of up-votes and down-votes but a low overall score.  

There are many ways to define how controversial a post is. Perhaps the most simple is to define it as the total number of comments. Posts that triggered a lot of discussion are probably controversial. However, while a post might have lots of comments, there may not be much reciprocal discussion. The maximum depth a post reaches, therefore, seems like a better measure. This too has problems however. If two users get engaged in a long discussion, the corresponding post will be considered highly controversial even if all the other comments appear in the first few nesting levels. We would like a method to account for these two types of bias. The measure we will use is h-index, as shown in [Gomez et.al.].

What is the h-index?

We used the following adapted version of h-index: The h-index of a post is the deepest nesting level of the radial tree with at least h comments. For example, the post in Figure 2 has an h-index of 4. If ranking just by number of comments, it would be 2nd, however, using h-index, it’s ranking falls to 153. This post is one of many that have a low h-index despite having a large number of comments. The h-index captures the difference between Figure 1 and Figure 2, unlike using the number of comments or the maximum depth.
When ranking posts by h-index, we need a way to break the ties because many posts have the same h-index values. I used the same method as [Gomez et.al], which is to prioritize the posts which have reached higher h-index values with fewer comments.

Here the white nodes are those not marked as visited, the gray nodes are those marked as visited and that are in frontier, and the black nodes are visited nodes no longer in frontier. Rather than having a visited flag, we can keep track of a node's distance in the field v.distance. When a new node is discovered, its distance is set to be one greater than its predecessor v.
Basically, when frontier is a first-in, first-out (FIFO) queue, we get breadth-first search.  All the nodes on the queue have a minimum path length within one of each other. In general, there is a set of nodes to be popped off, at some distance k from the source, and another set of elements, later on the queue, at distance k+1.