Hill Climb­ing and Cost Func­tions

If you’re climb­ing a hill, you know you’ve reached the top when you can’t take any fur­ther steps that lead to a high­er el­e­va­tion. But if the hill is ac­tu­al­ly a plateau with a flat top, the top­most point you reach can de­pend large­ly on where you start­ed climb­ing. In this post, I elab­o­rate on the top­ic of my pre­vi­ous post ti­tled Es­ti­mat­ing the Weights of Bi­ased Coins. This post presents the re­sults of an im­proved hill climb­ing al­go­rithm and al­so some ideas for rank­ing the dif­fer­ent so­lu­tions that fall on a plateau of valid val­ues.

Hill Climb­ing Al­go­rithm

The hill climb­ing al­go­rithm used in my pre­vi­ous post is a sto­chas­tic hill climb­ing al­go­rith­m. It ran­dom­ly choos­es a small in­cre­ment to one of the weights and then ei­ther ac­cepts or re­jects the move, de­pend­ing on whether or not the ad­just­ment brings the com­put­ed out­come clos­er to that of the tar­get dis­tri­b­u­tion.

In­stead of ran­dom­ly pick­ing a sin­gle move, we can con­sid­er the set of all pos­si­ble moves and pick the one with the steep­est as­cent up the hill. To do this, we can in­cre­ment each one of the weights in both the pos­i­tive and the neg­a­tive di­rec­tion. If there are three weight­s, there are six pos­si­ble moves. We can com­pute the val­ue of a cost func­tion for each move and then choose the best one. This process can be re­peat­ed un­til none of the pos­si­ble moves of­fers an im­prove­ment to the val­ue of the cost func­tion as­so­ci­at­ed with the pre­vi­ous es­ti­mate. To il­lus­trate, con­sid­er the fol­low­ing tar­get dis­tri­b­u­tion:

Sup­pose this rep­re­sents the ex­pect­ed out­come of play­ing the weight­ed coin toss game with four toss­es, as de­scribed in my pre­vi­ous post. The tar­get val­ues are thus:

We want to fig­ure out what weights of the bi­ased coins will give us an ex­pect­ed out­come that match­es this tar­get dis­tri­b­u­tion. We start by mak­ing an ini­tial guess. Sup­pose we start with an ini­tial guess of all fair­ly weight­ed coin­s, as il­lus­trat­ed be­low:

These weights can be rep­re­sent­ed us­ing the fol­low­ing no­ta­tion:

Giv­en this ini­tial guess, we can cal­cu­late what the ex­pec­ta­tion of the coin toss game would be if the coins were weight­ed ac­cord­ing to our ini­tial es­ti­mate. Re­call the fol­low­ing equa­tions de­rived in the pre­vi­ous post:

Plug­ging in the num­bers and do­ing the math, here are the com­put­ed val­ues based on the ini­tial es­ti­mate of the weight­s:

This does not match our tar­get val­ues, so we know that our ini­tial guess is not cor­rec­t. But how in­cor­rect is it? Can we quan­ti­fy the fit­ness of our es­ti­mate? In­deed, we can use a cost func­tion to de­ter­mine how close our es­ti­mate is to the de­sired re­sult. In this ex­am­ple, we use the sum of squared er­rors as our cost func­tion:

Our ob­jec­tive is to re­vise the es­ti­mate to min­i­mize the val­ue of the cost func­tion. Low­er val­ues in­di­cate a more fa­vor­able es­ti­mate. A ze­ro val­ue is the most ide­al. In­cre­ment­ing each one of the es­ti­mat­ed weights by a small step size, in both the pos­i­tive and neg­a­tive di­rec­tion, there are six pos­si­ble re­vi­sions we can make to our ini­tial es­ti­mate:

The pro­posed re­vi­sion with the low­est val­ue for the cost func­tion is the move with the steep­est as­cent up the hill. If we choose the pro­posed re­vi­sion with the low­est val­ue for the cost func­tion, our re­vised es­ti­mate then be­comes:

Us­ing this re­vised es­ti­mate as our new base­line, we can re­peat this process again and again un­til none of the pro­posed re­vi­sions of­fers an im­prove­ment to the val­ue of the cost func­tion as­so­ci­at­ed with the pre­vi­ous es­ti­mate. Af­ter many it­er­a­tions, we con­verge on the fol­low­ing val­ues:

Here is a vi­su­al rep­re­sen­ta­tion of the fi­nal re­sult:

If we play the coin toss game with these weight­s, the ex­pect­ed out­come match­es the tar­get dis­tri­b­u­tion. How­ev­er, as demon­strat­ed in a pre­vi­ous study, this is not the on­ly so­lu­tion pos­si­ble for the giv­en tar­get dis­tri­b­u­tion.

Dif­fer­ent Start­ing Points

In­stead of start­ing with an ini­tial es­ti­mate of all fair­ly weight­ed coin­s, what would hap­pen if we ap­plied the hill climb­ing al­go­rithm de­scribed above start­ing with a dif­fer­ent set of weights for the ini­tial guess? Re­call the tar­get dis­tri­b­u­tion we are try­ing to find the weights for:

Now sup­pose we start with the fol­low­ing ini­tial es­ti­mate:

These are as­cend­ing weights in­stead of equal weight­s. If we re­vise the es­ti­mate re­peat­ed­ly over many it­er­a­tions, fol­low­ing the same steps de­scribed in the pre­vi­ous sec­tion, the es­ti­mate even­tu­al­ly con­verges on the fol­low­ing val­ues:

As you can see, the fi­nal re­sults found by the hill climb­ing al­go­rithm de­pend on the ini­tial es­ti­mate of the weight­s. Since there are many valid so­lu­tion­s, the hill we want to climb is ac­tu­al­ly a plateau that is flat at the top. To vi­su­al­ize, con­sid­er the fol­low­ing il­lus­tra­tion:

A hik­er wants to get to the top of a hill. If he starts at the base of the hill and al­ways takes steps in the di­rec­tion that leads to a high­er el­e­va­tion, he will even­tu­al­ly reach the top of the hill. Once at the top, the hik­er can­not take any ad­di­tion­al steps that would lead to a high­er el­e­va­tion. In the il­lus­tra­tion above, the hik­er starts on the east side of the hill. Look at what hap­pens if the hik­er starts on the west side of the hill:

Re­gard­less of start­ing po­si­tion, the hik­er al­ways winds up in the same po­si­tion at the top of the hill. But this on­ly hap­pens with cer­tain types of hill­s. Con­sid­er what hap­pens if the hill is ac­tu­al­ly a plateau with a flat top:

When start­ing from the base on the east side of the plateau, the hik­er reach­es the top­most point lo­cat­ed on the east­ern rim. At this point, the hik­er can­not take any fur­ther steps that would lead to a high­er el­e­va­tion. Now look what hap­pens if the hik­er starts at the base on the west side of the plateau:

In this case, the top­most point reached by the hik­er is lo­cat­ed on the west­ern rim of the plateau. When the hill is re­al­ly a plateau, the hill climb­ing al­go­rithm does not con­verge to the same so­lu­tion for dif­fer­ent start­ing po­si­tion­s. How­ev­er, it might be pos­si­ble to adapt the cost func­tion in such a way that would give pref­er­ence to some valid so­lu­tions over oth­er­s. For ex­am­ple, a scor­ing func­tion might be used to give pref­er­ence to cer­tain val­ues based on prox­im­i­ty to the edge of the plateau.

Scor­ing Val­ues on the Plateau

Here I want to con­sid­er two dif­fer­ent scor­ing func­tions that can be used to rank the val­ues on a plateau of pos­si­ble so­lu­tions for the weight­ed coin toss game. Each of these scor­ing func­tions could be used as a sec­ondary cost func­tion in cas­es where the pri­ma­ry cost func­tion re­turns the most op­ti­mal val­ue of ze­ro.

The first scor­ing func­tion I want to con­sid­er gives pref­er­ence to weights that are near­est to the cen­ter of the range of pos­si­ble weight­s:

The sec­ond scor­ing func­tion I want to con­sid­er gives pref­er­ence to weights that are near­est to their neigh­bor­ing weight­s:

Now let’s con­sid­er the first set of weights we found for the tar­get dis­tri­b­u­tion af­ter ap­ply­ing the hill climb­ing al­go­rithm start­ing with an ini­tial guess of all fair­ly weight­ed coin­s:

Plug­ging these weights in­to the scor­ing func­tion­s:

Now let’s con­sid­er the sec­ond set of weights we found for the tar­get dis­tri­b­u­tion af­ter ap­ply­ing the hill climb­ing al­go­rithm start­ing with an ini­tial guess of as­cend­ing weight­s:

Plug­ging these weights in­to the scor­ing func­tion­s:

While both sets of weights are valid so­lu­tions for the giv­en tar­get dis­tri­b­u­tion, the scor­ing func­tions give pref­er­ence to one over the oth­er. In this case, both scor­ing func­tions give pref­er­ence to the sec­ond set of weight­s. But these two sets of weights are just two pos­si­ble so­lu­tions in an en­tire range of pos­si­ble so­lu­tions in which the pri­ma­ry cost func­tion eval­u­ates to ze­ro.

If we on­ly con­sid­er the range of pos­si­ble so­lu­tions in which the pri­ma­ry cost func­tion eval­u­ates to ze­ro, which are the on­ly valid so­lu­tions for the giv­en tar­get dis­tri­b­u­tion, how do we go about find­ing the one with the most op­ti­mal score for each of the two scor­ing func­tion­s? We can start by plot­ting the scores across the range of pos­si­ble val­ues. Based on the re­sults de­rived in the pre­vi­ous post, the weights of the bi­ased coins in the +2 and +3 states can be stat­ed in terms of the weight of the coin in the +1 state:

Ad­di­tion­al­ly, the val­ue of the weight of the bi­ased coin in the +1 state is lim­it­ed to a range with a low­er and up­per bound:

The min­i­mum val­ue at the low­er bound is:

The max­i­mum val­ue at the up­per bound is:

From this, we can rep­re­sent the range of all valid so­lu­tions for the tar­get dis­tri­b­u­tion on a sin­gle ax­is. We can plot the weights on the hor­i­zon­tal ax­is and the scores on the ver­ti­cal ax­is. Re­call the val­ues of the tar­get dis­tri­b­u­tion pre­sent­ed ear­lier:

Here is the plot of the first scor­ing func­tion for all weights in which the pri­ma­ry cost func­tion eval­u­ates to ze­ro for the tar­get dis­tri­b­u­tion:

The most op­ti­mal point can be found by tak­ing the de­riv­a­tive of the scor­ing func­tion and find­ing the root:

Here is the most op­ti­mal set of weights de­ter­mined by the scor­ing func­tion:

Here is the plot of the sec­ond scor­ing func­tion for all weights in which the pri­ma­ry cost func­tion eval­u­ates to ze­ro for the tar­get dis­tri­b­u­tion:

The most op­ti­mal point can be found by tak­ing the de­riv­a­tive of the scor­ing func­tion and find­ing the root:

Here is the most op­ti­mal set of weights de­ter­mined by the scor­ing func­tion:

These two re­sults are dif­fer­ent than those found by the hill climb­ing al­go­rith­m. For both scor­ing func­tions above, I used a nu­mer­i­cal root-find­ing method to find the root of the de­riv­a­tive. I don’t think a closed-form so­lu­tion is pos­si­ble in ei­ther of these two cas­es. This ap­proach to find­ing the op­ti­mal val­ues may not work if the scor­ing func­tion is not dif­fer­en­tiable at all points that fall with­in the low­er and up­per bound.

Next Steps

The vari­a­tion of the hill climb­ing al­go­rithm pre­sent­ed here con­verges to a so­lu­tion very quick­ly in a fi­nite num­ber of it­er­a­tions. How­ev­er, it does not con­verge to a unique so­lu­tion for all start­ing points. When us­ing a scor­ing func­tion like the ones pre­sent­ed above, a unique so­lu­tion can be found for a prob­lem that would oth­er­wise have an in­fi­nite num­ber of pos­si­ble so­lu­tion­s.

My goal is to find a way to com­bine the cost func­tion used in the hill climb­ing al­go­rithm with a scor­ing func­tion that gives cur­va­ture to an oth­er­wise flat plateau. This would al­low the hill climb­ing al­go­rithm to con­verge to a unique so­lu­tion re­gard­less of the ini­tial guess. The plateau es­sen­tial­ly be­comes a ridge. My ini­tial at­tempts at com­bin­ing the cost func­tion with a scor­ing func­tion have re­sult­ed in a method that seems to find its way to the ridge, but then gets stuck when try­ing to as­cend the ridge.

Ul­ti­mate­ly, I want to come up with a tech­nique that finds a unique so­lu­tion to the weight­ed coin toss game when there is a large num­ber of coin toss­es in­stead of just four. And I want to do so in a way that is com­pu­ta­tion­al­ly ef­fi­cien­t. Vari­a­tions of the hill climb­ing al­go­rithm may or may not be the best ap­proach. I plan to post more on this top­ic as I con­tin­ue to ex­plore new ideas.

Ac­com­pa­ny­ing source code is avail­able on GitHub.