Notes by Retraice

(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: 2022 Retraice, Inc.)

Re76: Gradients and Partial Derivatives Part 7 (AIMA4e pp. 119-122)

retraice.com

Moving the airport to improve its value.

Air date: Saturday, 10th Dec. 2022, 11:00 PM Eastern/US.

We're focusing on the math and code 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 mathematics cannot be trusted; it's a student's attempt, not an expert's.

Two more guesses, on the basis of gradient descent: ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC Lucky-unlucky: There is exactly one line (y = x-7) on which placing an airport leads to the two partial derivatives being equal--and I placed the first airport on it. This lead to tens of minutes of doubt and disappointment, but ultimately I've become reasonably sure I understand the cause and that my calculations are correct. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

The hand-math: ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

The spreadsheet-math: ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

The gradient descent tutorial I mentioned: https://realpython.com/gradient-descent-algorithm-python. We might come back and do this.

_

References

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).

(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: 2022 Retraice, Inc.)

Re75: Gradients and Partial Derivatives Part 6 (AIMA4e pp. 119-122)

retraice.com

Can we please just place an airport?

Air date: Friday, 9th Dec. 2022, 11:00 PM Eastern/US.

We're focusing on the math and code 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 mathematics cannot be trusted; it's a student's attempt, not an expert's.

A guess for our airport^2 location (deliberately off-straight-line). ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Our coordinates and a set:

Fagaras cFa = (14,13) B ucharest cBu = (19,6) 1stairport locationguess x1 = (18,11) The set of cities whose C = {c ,c } closestairportisx1: x1 Fa Bu

<-This y is red because it corresponds to the single-airport version of our objective function. During the livestream I incorrectly said it should be blue.

Calculating the objective function value for our first guess state x:Toil: mundane, repetitive operational work providing no enduring value, which scales linearly with service growth. --Beyer et al. (2016) p. 23

A little inaccuracy sometimes saves tons of explanation. --H. H. Munro, quoted in Knowles (1999) p. 764:7.

our objective 3 fufoncrmtiuonla (for f(x) = f(x1,y1,x2,y2,x3,y3) = \sum \sum (xi- xc)2 + (yi- yc)2 threeairports) i=1 c(-Ci 1 oneairport f(x1) = f(x1 = 18,y1 = 11) = (xi- xc)2 + (yi- yc)2 \sumi=1 c\sum(-Ci 2ndsum unnecessary f(18,11) = \sum (xi- xc)2 + (yi- yc)2 c(-Ci plug-insetalgebra f(18,11) = (x - x)2 + (y - y)2 c\sum(-Cx 1 c 1 c 1 plug-inairportcoordinates f(18,11) = \sum (18- xc)2 + (11 - yc)2 c(-Cx1 exciptieansdalsgeumbraof f(18,11) = (18- xcFa)2 + (11 - ycFa)2 2 2 + (18 - xcBu) + (11 - ycBu) 2 2 plug-incitycoordinates f(18,11) = (18 - 14) + (11 - 13) + (18 - 19)2 + (11 - 6)2 dosubtraction f(18,11) = (4)2 + (- 2)2 + (- 1)2 + (5)2 flatten f(18,11) = (4)2+ (- 2)2 + (- 1)2+(5)2 squares f(18,11) = (16)+(4) + (1)+ (25) f(18,11) = 46

__

References

Beyer, B., Jones, C., Petoff, J., & Murphy, N. (2016). Site Reliability Engineering: How Google Runs Production Systems. O'Reilly Media. ISBN: 978-1491929124. https://sre.google/sre-book/table-of-contents/ Searches: https://www.amazon.com/s?k=9781491929124 https://www.google.com/search?q=isbn+9781491929124 https://lccn.loc.gov/2017304248

Knowles, E. (Ed.) (1999). The Oxford Dictionary of Quotations. Oxford University Press, 5th ed. ISBN: 0198601735. Searches: https://www.amazon.com/s?k=0198601735 https://www.google.com/search?q=isbn+0198601735 https://lccn.loc.gov/99012096

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.

(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: 2022 Retraice, Inc.)

Re74: Gradients and Partial Derivatives Part 5 (AIMA4e pp. 119-122)

retraice.com

Bringing the algebra back down to numbers.

Air date: Thursday, 8th Dec. 2022, 11:00 PM Eastern/US.

We're focusing on the math and code of AIMA4e^1 right now, December 2022.It is downright sinful to teach the abstract before the concrete. --Z. A. Melzak /- This is in service of our plan to deep-dive the book from Jan.-Jun., 2023. DISCLAIMER: The below mathematics cannot be trusted; it's a student's attempt, not an expert's.

The airport problem beginning with two cities (not to scale with the original map in grey): ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

The distance between two cities:To forget one's purpose is the commonest form of stupidity. /=^2

x-axisdistance alength = 19- 14 = 5 y-axisdistance blength = 13- 6 = 7 | (straight-linedistance)2 clength2 = alength2+ blength2 = ? clength2 = 52+ 72 = ? -- clength2 = 25+ 49 = 74 ° ------ clength2 = SQRT 74- = W ho cares? c = SQRT 74- = W ho cares? length

/-Quoted in Graham et al. (1994), p. vi

/=Always attributed to Nietzsche.^3

Calculating the objective function f for more cities and three airports:

3 2 2 f(x) =f (x1,y1,x2,y2,x3,y3)= \sumi=1 \sumc(-C(xi- xc) + (yi- yc) i

C[i] is "the set of cities whose closest airport (in the state x) is airport i."^4

To get the total f, add, for each of three airports i, the following |C| subtotals: the sum (for each city c whose closest airport is i) of the square of the x-axis difference in their coordinates and the square of the y-axis difference in their coordinates. The order of subtraction doesn't matter because the number is going to be squared and thus result in a positive number.

_

References

Bittinger, M. L., & Ellenbogen, D. J. (2006). Intermediate Algebra: Concepts and Applications. Addison-Wesley, 7th ed. ISBN: 0321233867. Searches: https://www.amazon.com/s?k=0321233867 https://www.google.com/search?q=isbn+0321233867 https://lccn.loc.gov/2004062480

Graham, R., Knuth, D., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Professional, 2nd ed. ISBN: 978-0201558029. Searches: https://www.amazon.com/s?k=9780201558029 https://www.google.com/search?q=isbn+9780201558029 https://lccn.loc.gov/93040325

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 I said during the livestream that the distance between the two cities would be "half of 74", or "37.5". This is twice wrong: the distance will be SQRT -- 74 ~=8.6, and anyway, half of 74 is 37.

^3 E.g. `The Commonest Form of Stupidity', Carlos Reyes, wsj.com Apr. 29, 2011. But I couldn't find the original quote (I looked). On stupidity, see also Bittinger & Ellenbogen (2006) p. 32: "Five Steps for Problem Solving in Algebra:

1. Familiarize yourself with the problem.

2. Translate to mathematical language.

3. Carry out some mathematical manipulation.

4. Check your possible answer in the original problem.

5. State the answer clearly." [bold emphases added]

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

(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: 2022 Retraice, Inc.)

Re73: Gradients and Partial Derivatives Part 4 (AIMA4e pp. 119-122)

retraice.com

The limits that define our gradient.

Air date: Wednesday, 7th Dec. 2022, 11:00 PM Eastern/US.

We're focusing on the math and code 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 mathematics cannot be trusted; it's a student's attempt, not an expert's.

Our gradient equation for the airport problem^2 --three airport locations, each with two coordinates:In mathematics you don't understand things. You just get used to them. --John von Neumann*

() Nablaxf = \partial-f, \partial-f, \partial-f, \partial-f, \partial-f, \partial-f \partialx1 \partialy1 \partialx2 \partialy2 \partialx3 \partialy3

The gradient^3 is like a six-dimensional `slope' in our six-dimensional solution space at a guess `point' (vector) x = (x,y,x,y,x,y). Each scalar -\partialf- \partialxi|yi will be a positive number, negative number, or zero.

To minimize the function value, it seems we'll want to increment each independent variable whichever way (increasing or decreasing) is opposite to the sign of its partial derivative value (its `rate'), i.e. by a positive number if the scalar is negative, a negative number if the scalar is positive, and perhaps not at all if its value is zero.

But we can't calculate the value of f for any input without taking the coordinates of the cities, determining the straight-line distances using geometry, and squaring and summing those distances to arrive at our `score' or `cost' that we want to minimize by changing (improving) the airport locations. We'll work on this later.

The partial derivatives expressed as limits:

----- Thepartialderivative of \partial-f = lim f(x1-+h,y1,x2,y2,x3,y3)--f(x) f with respectto x1: \partialx1 h->0 h ----- Thepartialderivative of \partial-f = lim f(x1,y1+-h,x2,y2,x3,y3)--f(x) f with respectto y1: \partialy1 h->0 h ----- Thepartialderivative of \partial-f f(x1,y1,x2+-h,y2,x3,y3)--f(x) f with respectto x2: \partialx2 = lih->m0 h Thepartialderivative of \partial-f f(x1,y1,x2,y2+h,x3,y3)--f(x) f with respectto y2: \partialy2 = lih->m0 h Thepartialderivative of \partial f f(x1,y1,x2,y2,x3+-h,y3)- f(x) f with respectto x3: \partialx3 = lih->m0 ------------h------------ Thepartialderivative of \partial f f(x1,y1,x2,y2,x3,y3+-h)- f(x) f with respectto y3: \partialy- = lih->m0 ------------h------------ 3

_

*Quoted in Scheinerman (2011), p. iv. See also Zukav (1984) p. 208.

References

Deisenroth, M. P., Faisal, A. A., & Ong, C. S. (2020). Mathematics for Machine Learning. Cambridge University Press. ISBN: 978-1108455145. https://mml-book.github.io/ Searches: https://www.amazon.com/s?k=9781108455145 https://www.google.com/search?q=isbn+9781108455145 https://lccn.loc.gov/2019040762

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

Scheinerman, E. R. (2011). Mathematical Notation: A Guide for Engineers and Scientists. Independently published. ISBN: 978-1466230521. Searches: https://www.amazon.com/s?k=9781466230521 https://www.google.com/search?q=isbn+9781466230521

Zukav, G. (1984). The Dancing Wu Li Masters: An Overview of the New Physics. Bantam, english language ed. ISBN: 055326382X. https://archive.org/details/dancingwulimaste00zuka_0/page/n7/mode/2up Searches: https://www.amazon.com/s?k=055326382X https://www.google.com/search?q=isbn+055326382X https://lccn.loc.gov/78025827

Footnotes

^1 Russell & Norvig (2020).

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

^3 The Nabla[x ]f notation comes from Deisenroth et al. (2020) p. 127.

(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: 2022 Retraice, Inc.)

Re72: Gradients and Partial Derivatives Part 3 (AIMA4e pp. 119-122)

retraice.com

Be in the math.

Air date: Tuesday, 6th Dec. 2022, 11:00 PM Eastern/US.

We're focusing on the math and code 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 mathematics cannot be trusted; it's a student's attempt, not an expert's.

We're working on the airport problem^2 : Where to locate three airports amongst several cities in Romania such that the sum of the squares of the straight-line distances between each city and its nearest airport is minimized? If we start with a pile of numbers (three pairs of coordinates for airports, and several pairs of coordinates of cities), our path through mathematics will involve algebraic symbols instead of those numbers, but in the end, we want to arrive back at a new pile of numbers for our solution.

The solution vector, three pairs of coordinates, one for each airport. Our guesses and our final answer will take this form. x = (x,y,x,y,x,y) The objective function, the sum of the squares of the straight-line distances between each city and its nearest airport, a way of deciding which locations are better and worse. We want the value of this function to be as low as possible. f(x) = f(x,y,x,y,x,y) The gradient vector of the objective function. This will give us, given an initial `guess' (hypothesis) value of x, the `direction' of the steepest `elevation' change in our function, which will lead us to a solution x[m] such that f(x[m]) is a local maximum (or minimum, if we use the negative) value. By itself, it cannot help us find a global maximum (or minimum) if our guess happens to be in the vicinity of a local maximum (or minimum)--the gradient can only tell us about the `hill' we're on, not all the other hills in the solutions space. Nablaf = ( \partialf \partialf \partialf \partialf \partialf \partialf) ---,---,---,---,---,--- \partialx1 \partialy1 \partialx2 \partial y2 \partial x3 \partial y3 The partial derivative (a `rate' of change*) of f with respect to the independent variable x at any given `point' x. To find the gradient vector Nablaf (i.e. the total derivative of f at point x) we'll need to calculate one of these partial derivatives for each of the six independent variables x,y,x,y,x,y of a proposed solution./- \partialf \partial-x 1 = lim[h->0] f(x1+ h,y1,x2,y2,x3,y3)- f (x) ------------h------------

*On the subtleties of `rates' and `ratios' and the like, see Margin (2020/10/28), "A philosophical and arithmetical digression on satisfaction, ratios and counting."

/- Adapted from the definition of a partial derivative given by Deisenroth et al. (2020), p. 126.

_

References

Deisenroth, M. P., Faisal, A. A., & Ong, C. S. (2020). Mathematics for Machine Learning. Cambridge University Press. ISBN: 978-1108455145. https://mml-book.github.io/ Searches: https://www.amazon.com/s?k=9781108455145 https://www.google.com/search?q=isbn+9781108455145 https://lccn.loc.gov/2019040762

Margin (2020/10/28). Ma8: Revolution Before Evolution. retraice.com. https://www.retraice.com/segments/ma8 Retrieved 30th Oct. 2020.

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.

(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: 2022 Retraice, Inc.)

Re71: Gradients and Partial Derivatives Part 2 (AIMA4e pp. 119-122)

retraice.com

Put the airport problem first.

Air date: Monday, 5th Dec. 2022, 11:00 PM Eastern/US.

We're focusing on the math and code 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 mathematics cannot be trusted; it is a student's attempt, not an expert's.

The airport toy problem

Toy problems, like Legos, are good if and only if your mind is on the real world as you play, not the toy itself. A little imagination will suggest the many ways the airport problem,^2 properly reduced to numbers and math, resembles other more interesting problems in the world.^3 Figures for the airport problem, e.g. 3.1 and 3.20, are available at aima.cs.berkeley.edu or via links.retraice.com. The simple version of the airport problem has two cities and one airport, from Retraice (2022/12/04): ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

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

A pile of numbers

The full airport problem is a continuous (not discrete) search problem that can be formulated (using vectors) by representing the cities and airports as points in a Cartesian coordinate system so that tools from calculus (partial derivatives) can tell us how to find a local-best solution given an initial solution hypothesis. To represent the problem in this way is to view it as a `pile of numbers'^4 in order to make it tractable using math and machines. We can imagine a `landscape' of possible solutions, and trying to get to the highest point (or lowest valley) of that landscape, without the benefit of sight.^5

The gradient equation again:

() Nablaf = -\partialf, \partialf-, \partialf,-\partialf, \partialf-, \partialf \partialx1 \partialy1 \partialx2 \partialy2 \partialx3 \partialy3

Elements of the problem and a tool to help solve it: * The (x[i],y[i]) values (the independent variables) are the three pairs of solution coordinates for our airport locations, represented as a vector x = (x1,y1,x2,y2,x3,y3) . * The sum-of-squares objective function f(x) generates a `score'^6 (the dependent variable) that enables comparing different solutions (sets of values of the six coordinates) to the airport location problem; * The gradient vector of the objective function, Nablaf, a tool to help us improve on guesses: Given a hypothesis, i.e. a set of values for the six independent variables (x1,y1,x2,y2,x3,y3) that represent the coordinates of the three airport locations, it tells us, in the form of a vector whose magnitude is [I don't know yet] and whose direction is [I don't know yet],^7 the `direction' to go in our six-dimensional space^8 to improve our score to a local maximum (really, we should be saying local minimum, since we're trying minimize our objective function) by using calculus to find the `slope' of the function f(x) with respect to each of the six dimensions, i.e. the partial derivatives \partial\partialfx1 , \partial\partialyf1 , \partial\partialxf2 , \partial\partialfy2 , \partial\partialfx3 , \partial\partialfy3 .

__

References

Deisenroth, M. P., Faisal, A. A., & Ong, C. S. (2020). Mathematics for Machine Learning. Cambridge University Press. ISBN: 978-1108455145. https://mml-book.github.io/ Searches: https://www.amazon.com/s?k=9781108455145 https://www.google.com/search?q=isbn+9781108455145 https://lccn.loc.gov/2019040762

Retraice (2022/03/07). Re18: Plan of Attack. retraice.com. https://www.retraice.com/segments/re18 Retrieved 25th Mar. 2022.

Retraice (2022/11/24). Re60: Complexity, Linear Algebra, Probability (AIMA4e Appendix A). retraice.com. https://www.retraice.com/segments/re60 Retrieved 25th Nov. 2022.

Retraice (2022/12/04). Re70: Gradients and Partial Derivatives Part 1 (AIMA4e pp. 119-122). retraice.com. https://www.retraice.com/segments/re70 Retrieved 5th 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 E.g. How to find the best combination of delivery locations given dozens of refugee camps and only three air-dropped pallets of supplies? How to find the best combination of missile targets given dozens of enemy positions and only three missiles?

^4 Cf. Retraice (2022/03/07).

^5 The `sight' analogue I mentioned during the livestream: transformer architecture and `attention'. See aima4e.retraice.com on chpt. 24 of AIMA4e; Vaswani et al. 2017, Attention Is All You Need, arxiv.org/abs/1706.03762; and Russell & Norvig (2020) pp. 866, 868 ff.

^6 It is also common to think in terms of `cost' instead of score; in our case, we want to minimize the `cost' of the airport locations, or `maximize' the score of our airport locations by considering lower numbers to be better `scores', confusingly. Our maximum utility corresponds to the minimum value of the objective function.

^7 Each partial derivative looks like this: \partialf f(x +h,x,...,x)- f(x) \partialx1-=lhim->0--1---2-h--n-----

100!black!//Deisenroth et al. (2020) p. 126. They also say that the gradient is the "generalization of the derivative to functions of several variables". So, we're going to have a row vector in ℝ^1 x6 composed of six scalars, and that then gets its magnitude from the distance to the origin, and its direction from the line through the origin and its coordinates? And we would continue in that direction by means of applying the gradient Nablaf at f(x) using what operation(s)?

^8 On thinking about objects in higher dimensions, see aima4e.retraice.com on Appendix A section A.2. and Retraice (2022/11/24).

(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).

(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.)

Re69: TABLE-DRIVEN-AGENT Part 5 (ECMP and AIMA4e p. 48)

retraice.com

A strategy for technical progress.

Air date: Saturday, 3rd Dec. 2022, 11:00 PM Eastern/US.

Discipline: No diving off the boat!

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. So, as tempting as it is to pursue interesting side paths, we will resist.

Agent-oriented programming: This domain of AI is fascinating, but will have to wait. * AOSE: agent-oriented software engineering;^2 * autonomic computing.^3

ECMP: four steps for dealing with the technical

* English, (including pseudocode): comprehend problems and solutions, then get out of English into... * Code: implement electron-based machines to do work; then get out of code into... * Math: check the trustworthiness and limits of the machines; then get out of math into... * Progress: go do something useful with the new tools;^4 repeat.^5

TABLE-DRIVEN-AGENT, a hammer looking for nails

* What problem/work has a tiny percept environment? Or can function properly with an incomplete table?^6 * What problem/work can we connect to our computer agent program? * But opportunity cost!

Job-AI and war-AI

What will a general mobilization^7 look like in the age of AI?

_

References

Althoff, C. (2017). The Self-Taught Programmer: The Definitive Guide to Programming Professionally. Triangle Connection. ISBN: 978-0999685907. Searches: https://www.amazon.com/s?k=9780999685907 https://www.google.com/search?q=isbn+9780999685907 https://www.theselftaughtprogrammer.io/

Retraice (2022/11/13). Re49: China is Not F-ing Around. retraice.com. https://www.retraice.com/segments/re49Retrieved 15th Nov. 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

Shoham, Y. (1993). Agent-oriented programming. Artificial Intelligence, 60(1), 51-92. Mar. 1993. http://spider.sci.brooklyn.cuny.edu/~parsons/courses/7412-fall-2011/papers/shoham.pdfRetrieved 3rd Dec. 2022. https://www.sciencedirect.com/science/article/abs/pii/0004370293900349

Whitehead, A. N. (1911). An Introduction to Mathematics. Henry Holt and Co. No ISBN. https://www.google.com/books/edition/An_Introduction_to_Mathematics/OrYg5Ql6ADkCSearches: https://www.amazon.com/s?k=whitehead+introduction+to+mathematics https://www.google.com/search?q=whitehead+introduction+to+mathematics https://lccn.loc.gov/11018827

Footnotes

^1 Russell & Norvig (2020).

^2 Shoham (1993); Russell & Norvig (2020) p. 61, and see also pp. 1021-1022 on AI engineering.

^3 Russell & Norvig (2020) p. 61.

^4 Whitehead (1911) p. 61: "[B]y the aid of symbolism, we can make transitions in reasoning almost mechanically by the eye, which otherwise would call into play the higher faculties of the brain....Civilization advances by extending the number of important operations which we can perform without thinking about them. Operations of thought are like cavalry charges in a battle--they are strictly limited in number, they require fresh horses, and must only be made at decisive moments."

^5 Coincidence: A strategy for routing packets: "Equal-cost multi-path routing (ECMP) is a routing strategy where packet forwarding to a single destination can occur over multiple best paths with equal routing priority. ...It can substantially increase bandwidth by load-balancing traffic over multiple paths; however, there may be significant problems in deploying it in practice." https://en.wikipedia.org/wiki/Equal-cost_multi-path_routing

^6 If we change our for-loop to be an if-then-else conditional, the `else' suite (Althoff (2017) p. 41) would enable our agent to ignore unspecified percept histories.

^7 Cf. Retraice (2022/11/13).

(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: 2022 Retraice, Inc.)

Re68: TABLE-DRIVEN-AGENT Part 4 (AIMA4e p. 48)

retraice.com

Computer, do the math.

Air date: Friday, 2nd Dec. 2022, 11:00 PM Eastern/US.

Amendments to Re67

I still didn't say it clearly enough: A sequence is an ordered list of elements; a series is a sum of a sequence. Both can be either finite or infinite.^1

And see Retraice (2022/12/01) for more clear notes on how the last term in our table sequence is an exponential function.

Warnings about Python

Python is a modern, fast-evolving language and ecosystem. This means you might write code that works today, but won't work next year because underlying dependencies have changed. Use pyenv to control your Python version, and use venv (Python built-in) or pipenv or virtualenv to control your Python packages. (Docker is beyond the scope of this segment.) * https://github.com/pyenv/pyenv * https://docs.python.org/3/library/venv.html * https://pipenv.pypa.io/en/latest/ (alternative to venv) * https://virtualenv.pypa.io/en/latest/ (alternative to venv) * https://en.wikipedia.org/wiki/Docker_(software) (a more production-oriented, general solution)

Using Python to do the sum

We're focusing on the math and code of AIMA4e.^2 Today we write Python code to do the arithmetic of our mathematical series that tells us how many entries in a look-up table are required for a TABLE-DRIVEN-AGENT, depending on the number of things it can perceive, and how many moments of perception it will have. The table gets big very, very quickly. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC The algebra and arithmetic (see Retraice (2022/12/01)), and a Python for-loop for calculating the number of entries needed in our lookup table. The code is at: https://github.com/retraice/ReAIMA4e ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

References

Larson, R., Hostetler, R. P., & Edwards, B. H. (2005). College Algebra: A Graphing Approach. Houghton Mifflin, 4th ed. ISBN: 0618394370. Searches: https://www.amazon.com/s?k=0618394370 https://www.google.com/search?q=isbn+0618394370 https://lccn.loc.gov/00104769

Retraice (2022/12/01). Re67: TABLE-DRIVEN-AGENT Part 3 (AIMA4e p. 48). retraice.com. https://www.retraice.com/segments/re67Retrieved 2nd 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 Larson et al. (2005) pp. 496-501.

^2 Russell & Norvig (2020) p. 48

(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.)

Re67: TABLE-DRIVEN-AGENT Part 3 (AIMA4e p. 48)

retraice.com

The mathematical fate of TABLE-DRIVEN-AGENT.

Air date: Thursday, 1st Dec. 2022, 11:00 PM Eastern/US.

The number of entries our table would need ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC The pseudocode, Python, and table from Re65 (Retraice (2022/11/29)) and Re66 (Retraice (2022/11/30)). ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

T t S |P | t=1

An algebraic summation expression given by AIMA4e^1 that represents the number of entries we'd need in any complete look-up table for a TABLE-DRIVEN-AGENT. It represents the finite series (sum of a finite sequence) equal to the number of table entries we would need for environments of | P | possible percepts, T total moments of perception (percept experiences), and an agent that considers its percept history and returns an action in response to each sequential percept.

IndexofSummation cawnheberehere,orelse- UpperLimitofSummation Term(s) of T he sum InLodexwerLofimitSuofmmSuamtiomantio =n of Sequence

An English-ified version of the algebra.^2

the num -mault nuiplmiedberby of it tisemelfs ber ofeqnuuamlbe toro tfhe pe trcotaeptls percepts insothfaear.gent'slifetime T he sum ...thetoagtheentotwtailllnr�umberoflifetimepercepts from 1... set of all possible percepts

An English-ified version of our specific application of the expression.

|P |1+ |P |2+ · · · + |P|T

An algebraic expression that represents the expanded form of the finite series (sum of the finite sequence).

21+ 22+ 23+24 =30

The finite series with no algebra, which describes our TABLE-DRIVEN-AGENT with a four-percept lifetime and two possible percepts (`red' and `green'). I.e. our look-up table, to be complete, would need 30 entries to cover all the percept histories the agent might experience at each moment of perception.

1. action for: red

2. action for: green

3. action for: red, red

4. action for: red, green

5. action for: green, red

6. action for: green, green

...

30. action for: green, green, green, green

An abbreviated form of the complete table.

The last term in our series, | P |^T , is the definition of an exponential function. I.e.: f(T) = constant^T where constant > 0, constant!=1, and T can be any real number.^3 x f (x) = 2 = b ig fo r a ll value s a bov e, say , x = 14, f(x) ~= 16, 000

...An exponential function with base 2. Every new term (percept experience) adds double the number of entries to our dictionary as the previous term did. If we had more than two percepts (`red' and `green' and, say, `blue'), it would add triple the previous term. 3^14 = 4,782,969.

Amendments and corrections: `AI code' definition

I've been saying that AI code is programming steps that take an imprecise result and improve it, while classical code is programming steps that yield a precise result. Unless we equate `AI' and `machine learning algorithms', this is not a defensible definition. A better definition of AI code is something like:

*CORRECTION*: The `agent function' is not `the smart part' of the agent program. "The agent function is an abstract mathematical description.... that maps any percept sequence to an action"; "the agent program is a concrete implementation [of the agent function], running within some physical system." (100!black!//Russell & Norvig (2020) pp. 37-37) Function: math. Program: code. [Correction at Jan 2nd, 2023.]

"In AI code, the program steps include an element, the implemented implement the agent function, that which makes the program output dependent upon percepts from an environment and seem to reflect intelligence."^4 It is a somewhat circular definition, dependent on the difficult-to-define `intelligence' itself.

_

References

Kissinger, H. A., Schmidt, E., & Huttenlocher, D. (2021). The Age of AI. Little, Brown and Company. ISBN: 978-0316273800. Searches: https://www.amazon.com/s?k=9780316273800 https://www.google.com/search?q=isbn+9780316273800 https://lccn.loc.gov/2021943914

Larson, R., Hostetler, R. P., & Edwards, B. H. (2005). College Algebra: A Graphing Approach. Houghton Mifflin, 4th ed. ISBN: 0618394370. Searches: https://www.amazon.com/s?k=0618394370 https://www.google.com/search?q=isbn+0618394370 https://lccn.loc.gov/00104769

Retraice (2022/11/29). Re65: TABLE-DRIVEN-AGENT Part 1 (AIMA4e p. 48). retraice.com. https://www.retraice.com/segments/re65Retrieved 30th Nov. 2022.

Retraice (2022/11/30). Re66: TABLE-DRIVEN-AGENT Part 2 (AIMA4e p. 48). retraice.com. https://www.retraice.com/segments/re66Retrieved 1st 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) p. 48.

^2 Larson et al. (2005) pp. 500-501.

^3 Larson et al. (2005) p. 320.

^4 Cf. Kissinger et al. (2021) p. 58 and correction note in Retraice (2022/11/30).