Re70-NOTES.pdf

(The below text version of the notes is for search purposes and convenience. See the PDF version for proper formatting such as bold, italics, etc., and graphics where applicable. Copyright: 2023 Retraice, Inc.)

Re70: Gradients and Partial Derivatives Part 1
(AIMA4e pp. 119-122)

retraice.com

The math of `Local Search in Continuous Spaces'.

Air date: Sunday, 4th Dec. 2022, 11:00 PM Eastern/US.

We're focusing on the math and code difficulties of AIMA4e^1 right now, December 2022. This is in service of our plan to deep-dive the book from Jan.-Jun., 2023.

DISCLAIMER: The below notes cannot really be trusted, as they're a student's attempt, not an instructor's.

Placing three airports in Romania

The problem given^2 is to minimize the sum of the squares of the distances (see below comment*) between each major city in Romania^3 and one of its three to-be-constructed airports. This defines our `objective function' f of n-dimensional state vector x:

f(x)= f(x1,y1,x2,y2,x3,y3)

The x[i] and y[i] values are the Cartesian coordinates of the candidate locations of the three airports, from which we can calculate the squares of the distances from each city to its nearest airport and sum them to find the value of our objective function for a given set of airport locations.

*Why the squares of the distances? Perhaps because, as in the case of two cities and one airport, zero-sum arithmetic obtains if we only measure the distances themselves. Taking the squares reflects that some changes in the location of the airport are better than others.
________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC
Sums of squares reflect `better' airport locations; sums of distances don't necessarily do so.
________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Gradient descent

The solution to the airport problem, we're told, might be found by means of a gradient vector and gradient descent, i.e. cost minimization. This falls under the math subfield of `vector calculus'. The gradient is a vector, composed of partial derivatives of the objective function with respect to each of the six independent variables (x1,y1,x2,y2,x3,y3) , "that gives the magnitude and direction of the steepest slope" in our state space, i.e. the direction of change at any point in the six-dimensional space of solutions that would locally improve the value of our sum-of-squares objective funtion.^4

( \partialf \partialf \partialf \partialf \partialf \partialf) Nablaf = \partialx-,\partialy-,\partialx,\partialy-,\partialx-,\partialy- 1 1 2 2 3 3

Ultimately, gradient descent is about calculating the optimal direction to go in a state space to obtain better states as valued by an objective function, which itself is analogous to `elevation' in the state space. Gradient `descent' and `ascent' are inverses of each other: to minimize the cost, `descend' toward lower elevation; to maximize the benefit, invert the same objective function and `descend' toward higher numbers. Alternatively, `ascend' toward higher cost savings (`bigger' negative numbers) or `ascend' toward higher benefits (bigger positive numbers). This works locally, but not necessarily globally, i.e. local maxima and minima are a problem.

Struggling

We haven't yet made key decisions about how to tackle difficult topics such as these on Retraice. Depth first? Breadth first? How thorough and explanatory should we be? Our ECMP (English, code, math, progress) method might be a guide, but it's not the whole answer.^5

_

References

Retraice (2022/12/03). Re69: TABLE-DRIVEN-AGENT Part 5 (ECMP and AIMA4e p. 48). retraice.com.
https://www.retraice.com/segments/re69 Retrieved 4th Dec. 2022.

Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach. Pearson, 4th ed. ISBN: 978-0134610993. Searches:
https://www.amazon.com/s?k=978-0134610993
https://www.google.com/search?q=isbn+978-0134610993
https://lccn.loc.gov/2019047498

Footnotes

^1 Russell & Norvig (2020).

^2 Russell & Norvig (2020) p. 120.

^3 See the map on p. 64, figure 3.1, or p. 89, figure 3.20 (with `contours') or at http://aima.cs.berkeley.edu/figures.pdf.

^4 Russell & Norvig (2020) p. 120.

^5 Retraice (2022/12/03).