Hernan Amiune Blog

Greed is good. But usually far from optimal.

2019-09-16 19:07:13.039952

The mathematical or algorithmic definition of greed is the following:
A greedy algorithm or acting in a greedy way, which is the same, consist in always making the choice that looks best at the moment. That is, making a locally optimal choice in the hope that this choice will lead to a globally optimal solution.

By definition we can affirm that greed is not only a good solution but also a locally optimal one. This means that for a given state in a system about which we don’t have full information ; then being greed is the best thing we can do. But this doesn’t mean that a greedy action takes us to a globally optimal solution. Unfortunately we can discover this once we have more information.

To better illustrate this,let’s use the famous knapsack problem: Indiana Jones has a knapsack in which he can carry until 10 kilograms of weight,but he is in a cave full of treasures which is about to fall apart. Indiana must choose which objects he should carry in his knapsack in a way that these objects don’t exceed 10 kilograms in weight but he also wants to choose the objects that have the greatest value.

Now lets think about the following scenario where Indiana is running towards the exit of the cave:

1. Indiana runs ten meters and find two objects:
Objet1: value = U$S 3M; weight = 5kg
Objet2: value = U$S 5M; weight = 7kg

2. Indiana runs another ten meters and find another two objects:
Objet3: value = U$S 4M; weight = 4kg
Objet4: value = U$S 1M; weight = 3kg

3. Indiana runs another ten meters and gets to the exit of the cave which falls apart behind him.

If Indiana is greedy, he will choose the optimal option at each moment. So he will choose the Object2 for a value of U$S 5M in the first stop and then the Object4 for a value of U$S 1M in the second stop, giving him a total value of U$S 6M. Now if he had chosen the Object1 in the first stop, he would have been able to choose the Object 3 in the second stop giving him a total value of U$S 7M.

With this very simple example we can observe that being greedy does not always take us to the best outcome. Achieving globally optimal solutions is a very complex problem and when we don’t have all the necessary information we can say that is almost impossible.

If this simple example is so hard to solve optimally then we can only imagine the complexity of the world economy where multiple participants participate each one valuing things differently and where the information is never complete and almost always asymmetrical. The complexity of predicting which decisions will have a better impact in the future is enormous. The good news is that the more information we have the better predictions we can do and even being greedy we can escape from the local optimum we have found in the past leading us to a better economy and a better society. This way of improving is called Tabu Search.

References:
http://en.wikipedia.org/wiki/Greedy_algorithm
http://en.wikipedia.org/wiki/Tabu_search
https://www.coursera.org/course/optimization
http://oyc.yale.edu/economics/econ-159
https://www.coursera.org/course/gametheory

Bonus Videos :)
http://www.youtube.com/watch?v=ONXpaBQnBvE
http://www.youtube.com/watch?v=RWsx1X8PV_A

Defining Luck Mathematically

2014-04-25 03:02:41.937649

I have watched and read some discussions about luck. Most of them trying to figure out if success is determined by luck and, if this is the case, how much can we influence.

I'm going to try to define luck as precisely as I can so we can then derive some conclusions. You can agree with my definition or not. I hope you do.

Based on the following definition of luck provided by google: "success or failure apparently brought by chance rather than through one's own actions."

We can then define luck mathematically as following:

Luck(x) = 1 - P(x)

The luck of an event is equal to one minus the probability of that event.

This means that the more probable the event is the lower the luck you need for that event to happen and the less probable the event is the higher the luck you need for that event to happen.

Conclusion: In this way the success depends on how much you can increase the probability of an event to happen. If you can increase the probability you need less luck and if you decrease the probability you will need more luck.

We can now separate luck in two types:
1. Good luck: success apparently brought by chance
2. Bad luck: failure apparently brought by chance

Almost Mathematically:
1. Good luck: when a good event happens given it probability is low
2. Bad luck: when a bad event happens given it probability is low

Let's propose three very illustrative examples to show how this works:

1. Finding Gold: http://en.wikipedia.org/wiki/California_Gold_Rush
In the gold rush you can be very lucky and find gold by just digging in your garden or you can try to increase your probabilities, as many did, by going to California with the proper tools, in this case you will need less luck.

2. Dating a Supermodel: http://thestartuptoolkit.com/blog/2011/10/how-to-date-a-supermodel-or-get-dealflow-or-find-cofounders/
You can be so lucky that a supermodel randomly walks near you and suddenly falls in love with you or as the linked article suggest you can increase your probabilities by showing up where the supermodels are and try to talk with them. In the later case you will need less luck.

3. Winning the lottery
Usually the probabilities to win the lottery are around 0.00000001 so you need a lot of luck, by our definition exactly 0.99999999 of luck and that's a lot. What is worst in this case is that there isn't much you can do to increase your probabilities of winning.

Can we increase the probability of an event to 1 so we need no luck?

No. This is impossible because of the way statistics and probability work and the way the world works. Watch these videos for some very nice explanations of very well known physicists: https://www.youtube.com/v/jhnKBKZvb_U?&start=1066&end=1132&version=3
https://www.youtube.com/watch?v=2OU_f7vYDys
But the good news is that we almost always can increase our probabilities by working hard and sometimes we can get very close to one.

Just remember there is always a chance

Artificial Stupidity

2014-01-26 19:16:01.708826

The first step towards creating good and useful artificial intelligence programs is to realize that we aren't as smart as we think we are. Maybe if I can convince myself that I'm very very stupid then maybe I can create an algorithm that performs better than the human brain in those few fields where the human brain is still better.

The first thing I want to point out to myself is that if I have an infinitely big database that matches every possible input with the best output then I can solve any problem. This means that I'm not smarter than an infinite lookup table.

Lets show a very stupid example to illustrate in a very simple way how a lookup table works. Lets create the algorithm for a robot that plays rock-paper-scissors where the robot knows what the adversary is going to play like the video shows
The algorithm is very simple, it has only 3 possible inputs: rock, paper or scissors and you need to play the following output in order to win:
if input = rock then output = paper
if input = paper then output = scissors
if input = scissors then output = rock
And that's all, for every input I specify an output and I have a perfect machine. This method can be extended to solve any complex problem. If you don't belive this principle can be extended to solve more complex problems please watch this video for a wonderful explanation

Now I know that in order to create a machine that is as smart as God I just need to save every possible input for a problem with its corresponding best output.

Of course there are some obvious problems with this approach:
1. The input data we measure is noisy and contains measurement errors so probably we will end mapping an input with a wrong output.
2. We don't have infinite storage in our computers to save an infinite number of inputs/outputs and also we don't have infinitely fast computer processors to search on those databases.
3. In most cases is impossible to obtain every possible input/output so most of the time I will need to deal with missing information.

So how humans and computers can deal with these problems?

1. Noise and Measurement Errors
There are some statistical techniques that can help humans and computers to detect and clean these errors but the best thing you can do is to be as careful and precise as possible when you measure. Also getting a lot of input/output data will help to detect the errors.

2. Storing an Infinite Amount of Input/Output pairs
This seems like a big deal but actually it isn't. The same way you compress a big file to make it small you can compress huge number of input/output pairs to make them small and you can even compress an infinite number of data to make it finite. Don't believe me watch this: while(true) print 1 That statement of 19 characters compress an infinite sequence.
The good news are you can always do this, the bad news is that sometimes you will lose information after the compression. The hard optimization problem is to find the best function to compress the information as much as possible without losing much information.

3. Missing Information
This is one of the most interesting problems. What happens when you have a new input and that input is not in your input/output pairs database? Then you will search in your database to find the "most similar" saved input and return the corresponding output. The hard optimization problem is to find the best function to compare the inputs in order to provide the most accurate prediction.

Conclusion: I just need to focus in finding the best "compression function" and the best "comparison function".

Of course these functions are not easy to find. For some state of the art algorithms to find this functions read this paper Learning Deep Architectures for Artificial Intelligence

I don't know the world very well, but that's what I think

2013-12-21 18:23:50.145402

The other day a friend asked me how is studying maths and physics helpful in daily life.
Even when you don't understand almost anything about equations and calculus you will have the advantage of having find out:

how hard it is to really know something
how careful you have to be about checking the experiments
how easy it is to make mistakes and fool yourself

So the next time someone will try to fool you it won't be that easy

Twitter vs GitHub. Idols vs Ideals

2013-12-01 22:40:03.620489

There is a very wise quote that says "follow the ideal not the idol". Something I never liked about Twitter is that it promotes exactly the opposite. I guess this is why it gets along so well with TV. While it started with a very different purpose it ended up being the perfect way for TV idols to keep their zombie fanbase on the internet or at least that's the part that it is making money so I expect they continue moving in that direction.

On the other side of the tech industry is GitHub, a place where people don't follow idols they follow projects, they follow ideals. People work on the projects and improve them, adding a lot of value for them and the community.

It would be nice if what GitHub achieves for programming can be replicated with ideas, politics and other fields where people still follow idols instead of ideals.

This is just a thought. It's probably flawed. I would like to upload on GitHub and let other people improve it.

Courses To Learn How Not To Do Things

2013-09-30 21:47:52.850955

I hate those small courses that are everywhere that some unknown teacher charges you to tell you how to do something. Probably on the internet there is one better for free. I did a couple of these courses after I finished college and they weren't worth the money at all. But I guess at that time there wasn't the quality material that you can find today on the internet.

Anyways what I want to talk about in this post is about another kind of course that I consider it really worth to pay for and these are the "courses to learn how not to do things". I realized very recently that I've been paying a lot of this courses after I started my own company. Everytime I try to do something new and I do it wrong I lose money. It sucks but I learn a lesson. At the beginning I spent a lot of time regretting myself. Now my thinking is more positive, I still regret a little but my thinking is the following: I have learned something and I have paid a fair price for that knowledge.

So if you are paying for the first type of courses I mentioned then try the second ones. There is no final exam or diploma but the lesson sticks to your brain forever.

I Never Met a Genius

2013-09-14 05:17:46.895942

I consider myself a normal guy, an average guy regarding my intelligence. I was never the top of my class. There was always at least a couple of guys that were better than me, and my brothers are way smarter than me. But I never met a genius.

One time I got a call from Microsoft to do an interview for a developer job. The interview was in Brazil, Rio de Janeiro. They paid the trip, it was awesome. I did a very bad interview, I was intimidated, I thought only geniuses work at Microsoft and I wasn't a genius. But I never met a genius. The next year they called me again. I did it great.

A couple of times I was lucky enough to get to the finals of a programming contest. Free trips again, Las Vegas and Orlando, really awesome. I met incredible guys in those trips. These guys were light years smarter than me. I met 16 years old guys who knew more math than my University teachers. They can solve a problem and code an algorithm ten times faster than me. But I never met a genius.

I always wanted to meet a genius like those from the movies, the ones that seem to have supernatural skills that everything seems so easy for them, like if they were born knowing everything. But I never met a genius.

I met a lot of amazingly smart people in my life but they all seemed to share something in common:
1. They all trained and studied a lot.
2. They were great at some specific fields but not very good in other fields.

I'm a little disappointed... in movies.

Fundamental Theorem of Entrepreneurship

2013-09-01 21:36:50.909829

It doesn't matter how beautiful your product is, it doesn't matter how smart you are. If people don't buy it, it's worthless.

Adaptation from Richard Feynman's quote:
First you guess. Don't laugh, this is the most important step. Then you compute the consequences. Compare the consequences to experience. If it disagrees with experience, the guess is wrong. In that simple statement is the key to science. It doesn't matter how beautiful your guess is or how smart you are or what your name is. If it disagrees with experiment, it's wrong. That's all there is to it.

PhD vs Startup

2013-05-26 04:01:48.012714

Both take at least five years.
Both require hard work and perseverance.

If someone told you something different it is probably a lie or at least incredibly improbable. Getting your PhD or creating a successful Startup takes at least five long years of hard work and a lot of comebacks from failures.

In a PhD you have a scholarship and a tutor that tells you what to do.
In a Startup, unless you bootstrap, you have investors and a board that tells you what to do.

If you don’t like bosses then the PhD and the Startup are good choices in comparison with regular jobs, specially the bootstrapped startup or the PhD with a tutor that gives you some freedom to do your research. Just remember that a good tutor is better than no tutor and no tutor is better than a bad tutor.

A PhD is safer. If you don’t do so well, you are going to get the title anyways.
A Startup is riskier. If you don’t do very well (90% of the time), you can end broke.

If you are afraid of ending without a penny after those five years then the Startup is not for you; but take into account that you will learn a lot and you will probably be able to get a job easily or start a new Startup with funding. The PhD is safer and a job at the end it’s guaranteed; but you will be also broke at the end of those five years.

In a PhD you learn a lot about an specific subject.
In a Startup you learn a lot about life and also about your business.

This is an interesting difference, while doing a PhD is awesome and you learn a lot, you are somewhat isolated inside the university environment. In a Startup you have to fight to earn your money so you will learn a lot of lessons about life, and by lessons about life I mean how people make a living and what things they do for money. Probably in a PhD you also see this but in a smaller scale inside the research community.

If what you want to do is to change the world, go with the PhD.
If you want loads of money go with the Startup.

This is my favorite difference because everybody says they start a company because they want to change the world. While this can be somewhat true (we want to change our world by making a lot of money :), you can have a greater impact by doing research. At least that's my opinion. I have tons of respect for entrepreneurs like Henry Ford or Larry Page but can you compare their contributions to the ones of Carl Friedrich Gauss or Alan Turing?

In the end I think both are great life choices and some lucky guys can do both.

Ask Others For Their Experience. Ask Yourself For Advice.

2013-02-09 18:48:33.719379

My first steps as an entrepreneur remember me a lot the episode Homer and Apu from “The Simpsons” where Homer accompanies Apu to the Kwik-E-Mart head office in India. Once they arrive, they meet with the head of the Kwik-E-Mart corporation, who says that they can ask him three questions. Unfortunately, Homer wastes the three questions ("Are you really the head of the Kwik-E-Mart?!", "Really?!" and "You?!"), and the head of the Kwik-E-Mart does not help Apu with his problems.

When my cofounder and I started our company we were eager for advice, we were looking for the experienced guys to give us some advice about how to do things right, about how to be successful, what to do, where to go. In a few words we were two young guys looking for that holy advice that would lead us to success.

One day we were lucky enough. One of the most known entrepreneurs of our country gave us a meeting, so we could just chat a couple of minutes and ask him a few questions. We were thrilled, that was our opportunity, that was going to be the first day of our successful lives as entrepreneurs. So we immediately bought two of the cheapest bus tickets to the big city, scheduled a couple of more meetings with potential customers, dressed up with our cheap suits and began our ten hour bus trip. Oh, let me clear this now, we wore suits because our potential customers were banks.

The ten hour bus ride was during the night, the bus seats were incredibly uncomfortable, the guy next to me was snoring loudly and a cold wind was entering from some hole in the bus that I couldn't find and made me miss the usual hoodie that I use in this kind of trips. So we arrived to the big city without sleeping, we didn't care, we were just too excited, we were on time for the meeting so we skipped breakfast, caught the metro, walked a couple of blocks and we finally arrived. We were a little dizzy and we realized we shouldn't have skipped breakfast but it didn't matter, the building was beautiful, the location exceptional. We knew we were at the right place: the guy knew what he was doing.

We entered to his newly founded company and we presented ourselves to his secretary, she was beautiful, really beautiful. It was for sure, we were about to talk to the right guy. After thirty minutes waiting he received us very very kindly in the meeting room of the company with another guy who was his assistant. Before we could said anything he said to us “OK I will give you a piece of advice” and I thought,” this is it, here it comes the enlightenment.” We didn't even say anything and the guy already saw some mistakes that we were doing, and his exact words were “Never wear suits for a meeting in the tech industry”. We then had a small chat for three to five minutes and he had a TV interview so he left us with his assistant. That was all and we went back to the bus again.

Now four years later, I put myself in the shoes of this entrepreneur and I can't help thinking how kind he was to receive two idiots (sorry partner) and gave us five minutes of his time. I really mean it. We didn't even know what we were looking for. He received us when he could have just ignored us like the rest of the successful entrepreneurs. We made that trip because of him and we learned a lot from that trip. The most important thing that I've learned after trying to guess what kind of advice we were looking for, is that I should never ever give someone some advice because I don't know their problems as well as they do, the most helpful thing I can think of is that I can share my experiences and mistakes as true, original and detailed as possible so they can have their own conclusions and advice for themselves.

The title of this article might look like some advice for you but it is just some advice for myself. This was just my experience. It is up to you to decide if you can use it.