Stochastic Optimization as a mindset

Stochastic optimization (finding the best solution when you have randomness) is a tricky topic. As an example, think about picking the fastest route for driving home from work. Depending on the traffic, different paths might be fastest. It might make sense at first to say "I want to pick the path that will be the fastest today." But when that outcome has uncertainty, it is usually impossible to answer until after you actually have driven home.

There are a number of different ways people handle this issue in optimization. For driving home, it probably makes sense to pick the route with the lowest expected transit time. Over the years of driving that path, some days might take longer than you'd like, but in the long run you'll come out ahead. Other times when you have a dinner-appointment, it might make sense to pick the route that has the lowest probability of taking more than 25 minutes so you are not late. If you were managing the electric grid and avoiding power outages, you will account for the uncertainty in a different kind of way.

As you build a model of the world, different objectives will compress or amplify the effects of uncertainty. Frequently when you are driving somewhere, there will be several routes that have basically the same expected transit time. But the likely worst-case (say, average of the worst 5%) of driving times will often be very different across routes. In the first case, the uncertainties are a relatively small issue because they all get averaged away. In the latter case, extreme cases have a much bigger effect, and therefore the uncertainty will too.

Since models are just attempts to represent reality in a useful way, which model to use for a stochastic problem will depend a lot on your best guess of the costs of uncertainty. If you use an expected-value objective but care a lot about the worst-case tails, you are going to have a bad time when you implement your solution. On the other hand, if you optimize for the worst case for a low-stakes situation like how much inventory to order for a promotion, your company probably will not stay in business too long.

While I have been focusing on either worst-case or expected value as an objective, there are countless ways to design your stochastic optimization model. The short version is that in the field, we are typically trying to reduce the random outcome of our decisions to a single number which allows us to pick the "optimal" solution. While there are ways to optimize over "multiple objectives," they still tend to focus on either subjective decision making or weighting the objectives to obtain a single number.

I welcome comments either on the blog or directly to me. I'm getting this topic ready for a short talk, and I think this will be only my second talk on optimization to a room full of not-optimization people.

Rocky Mountain Datacon

I spent the previous two days at the first Rocky Mountain Datacon. I haven't yet figured out how to blog during a conference (I have two half-finished posts and a number of ideas), but it was a great experience and I learned a ton. All the talks were filmed, and it was successful enough that the organizers expect to do it again next year.

For the moment, I thought I would share a few thoughts of what I learned at the conference. Feel free to hit me up if you are interested in a discussion about any of them since that will help my eventual posts be more useful and articulate for everyone.

• Data has allegories to oil, currency, intellectual property, and inventory.
• Data is a tax-free asset (though it does cost money to keep it and use it).
• With the current technology and tools, we have distinct classes of big, medium, and small data. Accurately assessing what you have and will have in the future is important for picking the right technology stack.
• I picked up a lot of data science 101 including what all the titles should mean, what a technology stack is, how to pronounce the word "munging," what the technology options right now look like, how to "break into the field," and a ton of other things.
• And for the OR folks reading, very little of any of this is using optimization yet. Several people threw around "5 years" as the timeframe to get there, so it seems to be a pretty good time for us to join the data science world.

Evaluating health claims

There is a large body of evidence (along with personal anecdotes) that getting people to change beliefs is very difficult. Studies have found that providing people with contradictory evidence can make them even more confident in their views. Given these challenges, how should we go about reducing misinformation in the world?

One in-progress study is looking at teaching primary school students in Uganda how to evaluate health claims as well as the evidence they are based on. While I had previously thought that a basic understanding of statistics was our best option, this kind of education is more clearly and directly related to the goal. It will be interesting to see what the results of the study end up being, particularly if we eventually find that learning in one area spills over to increase scientific literacy in general.

Indicators and using noise as signal

​How should you use an indicator? When you look at the weather report, it seems pretty straightforward. Sunny means you do not need an umbrella. High of 36 means you should wear a coat. But what about when there is a 40% chance of rain? And what if you are trying to figure out if you can go for a hike this weekend?

When talking to my friend Chris Miller recently, he was trying to predict the weather before going on an aggressive hike. He mentioned that the noise in the forecast was part of his signal to decide how seriously he should take the report. If the forecast kept changing in the few days leading up to the proposed hike, that meant there was a decent chance that the weather would be unfavorable the day-of.

This got me thinking about the standard weather forecast as an indicator of the underlying data. I had a friend who was studying to be a meteorologist, and so she would go straight to the NOAA source data to predict the weather. For everyone else the weather report is basically a black box and all we have to work with are the indicators.

And when there are no indicators that answer your question? Or if it is simply impossible to  interpret the underlying data? That is when it is time to get creative with the information you do have.

Voting and an intro to some game theory ideas

My apartment complex decided to show a movie via projector and sent out a poll with 6 options. We were asked to rank the options and told that the movie that won would be shown at the movie night.

If management only got one response, it would be easy to decide how to vote and which movie won. However, assuming there was more than one response, how should the winner be determined? And given that there will be other voters, what should your vote be? In this game, management has decided on the rules for voting (rank the 6 options) as well as the rule for which movie is selected based on those votes (which they did not tell us). The voters are then left to decide how to vote, given their guess of the rules.

The most likely way to score such a set of votes is that management could give a set number of points for each possible rank-position (i.e., 5 points for being ranked 1st, 4 points for 2nd, etc) and then take the movie with the highest sum. However, there's no reason they couldn't pick the movie with the largest number of times being ranked 1st, and then use the later places as tie breakers. And in general, there can be truly crazy sets of rules. For example, if one movie is far-and-away the favorite in general, we could handicap that movie by saying any vote for it is actually only worth half a vote (this seems ludicrous... but in auction theory counting a "high-valuation" bidder's bid as a fraction of their actual bid is a standard tool to design an "optimal" auction).

Depending on the rules, an individual voter has different incentives. Further, depending on their guess as to how everyone else will vote, they will have additional incentives. An important notion in game theory is a "Nash Equilibrium." A NE is a set of votes for everyone so no individual person will choose to switch their vote. So if you knew that everyone else was following the NE, there is no benefit to you from not following the NE. But there are a lot of assumptions that go into the NE including that it is unique, that there will be no collusion (lets both list our shared second-favorite movie as 1st), and that somehow there being a NE actually leads people to vote accordingly (here is the Wikipedia link on when that will happen).

Given all this complexity, you might wonder how anyone ever decides anything. In a world where so much is uncertain though, a lot of decisions could be the best. If I vote my genuine ranking, I'm at least giving my preferred movie it's best shot to be selected. I could vote strategically and rank my 3rd favorite as top because I think my least favorite movies are the most popular. I could also not vote at all because I think the effort involved in voting is more than the difference between the outcome when I vote or not. Which of these guesses of uncertainty is right is impossible to say until after the votes are in, which are then influenced by what everyone else is guessing to be the case.

Hopefully, this gives a taste of some of the difficulty both in designing the rules of a game, and the subsequent decisions by the voters. Early on in learning about game theory I was told "the devil is in the details," which I have found to be absolutely true. First-past-the-post voting seems sensible, until you realize the incentive issues when there are more than two choices.

Feel free to send me any follow-up game theory questions you have and I will do my best to get them answered!

Classification problems

A friend asked me for ideas of a good analogy for classification problems in machine learning. In a classification problem, we have a collection of objects, and we somehow want to separate them into groups. Ideally, when designing this analogy there are a few things we want to convey:

• Not all properties of objects are equal when it comes to classification. Some will be highly predictive, while others just help you over-fit your model.
• Some properties will be highly correlated, so it can be a waste of energy / data effectiveness to include them all.
• Your desired classification informs which properties you should use for your classification.
• What do "properties" even look like, and how do they help us get at a classification?

The example I suggested is a person deciding what to eat at a potluck. I usually have two different classification problems to worry about when I'm filling my plate. First off, I want to decide which things I want to eat. In addition, I'm one of these people who will get a main course plate, eat that, and then go get dessert later. So as I survey the food, I have to decide both which things I think will be delicious, and which things I want to get later as dessert.

When trying to figure out what will be delicious, there are a lot of criteria I could use. Since I do not like cucumbers, anything with them is immediately excluded. Other properties besides ingredients could be smell, color, how much of it is available, how much was already eaten, the temperature of the food, anything! Some of these criteria are more helpful than others. I've had a lot of delicious brown things in my life at potlucks. And when I am trying to decide if something is dessert of not, how much people ate is not going to be very informative.

How do you classify food at a potluck? 

Organized Brainstorming

When you learn about brainstorming, there is often a focus on how "spontaneous" it should be. Don't worry if an idea is good or bad, just add it to the list! During undergrad I took several of Tau Beta Pi's "Engineering Futures" classes. One of the topics was a modified approach to brainstorming.

With the mindset they taught, the quality of the ideas are still unimportant, but you go about producing them in an organized way. Say you are trying to come up with the list of things you need to buy from the store. Instead of simply writing things down, you create categories and then fill in each category. For our shopping example, you might list each room in your house as a category and then think about what things you need for each room. If you are trying to figure out the best way to solve an engineering problem at work you might have categories like "new equipment" and "better software."

What are your thoughts on brainstorming? After a quick read through this link on the topic, it looks like I am describing a more task-oriented version of brainstorming. Which makes sense for an engineering-focused training on the subject.