Optimization: The Intuitive Process at the Core of AI
Artificial Intelligence (AI) has gotten a reputation as being the big technological advancement of our time, but at the same time a force which stands to upend society. AI seems almost alien in all of its mystery, complexity, and implications. I want to prove that while the implications are enormous, the fundamental mathematical process driving it is understandable, and maybe even intuitive. Lets start with an analogy.
Consider how a lone blind explorer attempting to find the location the highest peak in his country. All that the person can do is walk North/South, walk East/West, or do a combination of those two. So, in this case, there are only two inputs the person has control over: the distance traveled North/South (lets call this Y) and the distance traveled East/West (lets call this X). The result of having traveled those two distances is his current location on the map and corresponding elevation. See the terrain below. At Y=0.5 miles North, X=0.5 miles South, for example, the current elevation would be Z=0.52 miles in elevation.
The location at top of the highest peak, then, is just the best possible combination of the two inputs. So how would the blind man approach the problem?
One approach would be to simply walk in the direction that feels the steepest, then after a while reevaluate and choose a new steepest direction, then continue walking. The process is repeated, taking “steps” until there is no longer any good direction to go. This should be at the top of a peak. In the animation below, the explorer, represented by a colored dot, finds the peak after 25 steps.
A slight modification is for the explorers to run. While moving quickly might mean that they are not able to perfectly evaluate which way is the steepest and shortest way to the top, taking faster less thoughtful steps will still reach the summit more quickly.
However, for a different starting location, the explorer might only find a smaller peak and think that he is at the top, even if a bigger peak exists close by.
Fortunately, the computer is not limited to only one explorer, but can select several random starting locations for several explorers. Likely, at least one of them will have found the highest peak. In the case below, both the pink and red explorers find it while the others end on smaller peaks.
Now, the computer is able to quickly solve the optimization problem by sending out multiple explorer and having them run in the direction that is approximately the steepest path. With only a small amount of computational power, the X and Y location of the tallest peak is located.
Admittedly, in the two input case, the problem could instead be solved by simply checking every possible position on the map. However, most real-world optimization problems have many more than two inputs, up to several hundred. As the number of inputs grows, it becomes increasingly important to have a fast system, like the one the explorers used, to search for the optimal result instead of attempting to check every possible point. An exhaustive search of all points could likely take an impossible amount of computer time for a problem with many inputs. For instance, if the problem had 50 inputs and each input had 10 possible settings, to try every combination would be about as many trials as there are atoms on the Earth.
In this case, a two-input problem is used as an example because three dimensions (two inputs making one output) is the most that a person is able to easily visualize. While higher dimensional systems may be impractical to visualize, the intuition behind how the problem is solved remains exactly the same.
Multi-dimensional optimization problems are at the core of many computer programs set to revolutionize several industries. One important use for this type of problem is with neural networks, a prominent type of AI. In this case, the current elevation of the explorer is how well the AI performs a task, and each input is how active a given neuron or neuron connection path is in the neural network. The structure of the network is complex, but the principle is still to find the best possible combination of inputs. The activations of each neuron and connection changes slightly every time the program runs, and the network performs its task better and better. This is just like how the explorer got progressively closer to the summit, but the summit here is a well performing neural network. AIs trained in this way will do tasks all the way from recognizing handwritten text to being the brains of self-driving cars.
Another important use is in generative design AI. Generative design software takes in several requirements from an engineer such as how strong a part needs to be and what material it will be made out of. For example, the part above is a bracket to hold an airplane seat to the floor, and will be made out of titanium. The computer is then tasked with designing the part to meet the requirements, but be as lightweight as possible. Again, from a starting geometry, the part becomes progressively lighter with each small change. Once no small change could possibly make the part better, then it is considered optimized. The parts made with this method take on strange alien-like shapes like the seat bracket, but are often 30% lighter, or more, than conventional parts which is a big deal in a lot of applications. This will mean lighter, faster cars, bridges that need less material to build, airplanes that can carry more weight, and mostly likely enable some new inventions that were not possible without it.
In addition to the two types discussed above, AI has many other forms, almost all of which rely on optimization. Even with all of the impact that AI is poised to have on our lives, it is almost comforting to know that, fundamentally, it is just a computer solving the problem of the blind explorer.
CODE: For those curious, the MatLab code used to generate the images is below. Feel free to copy it into a new file and see how it works.
clear; close all;
%% Options
Animation_File=’Animation4';
Number_Of_Steps=25+1;
Step_Scale_Factor=0.2;
Frame_Rate=3; %in frames/sec
Step_Rand=1; %turns random noise on the steps on or off
randAngle=30; %angle +/-
currentLocation=[0.75,2.2;2.7,1.75;0.9,0.15;1.75,1.4;2.55,2.3];
%currentLocation=[0.75,2.2];
%currentLocation=[2.7,1.75];
%currentLocation=[0.5,0.5];
colorOptions=[‘r’,’g’,’b’,’m’,’y’,’w’,’c’];
%% Generate terrain
[Y,X] = ndgrid(-1.5:0.05:1.5,-1.5:0.05:1.5);
East=X+1.5;
North=Y+1.5;
%make surface
Z = getZ(North,East);
%background color
figure(‘Color’,’white’)
%scale
set(gcf, ‘OuterPosition’, [0 0 1000 800]);
%plot surface
surf(East,North,Z)
axis equal
hold on
colormap(pink)
xlabel(‘East’)
ylabel(‘North’)
zlabel(‘Elevation’)
xticks(0:0.5:3)
yticks(0:0.5:3)
zticks(0:0.25:2)
%% Make Interpolent For Gradient (in nd grid form so coordinates are (Y,X) or (North,East))
[fx,fy] = gradient(Z,0.05);
Fx=griddedInterpolant(North,East,fx);
Fy=griddedInterpolant(North,East,fy);
%% Explorer Initialization
%currentLocation=[0.75,2.2;2.7,1.75;0.9,0.15;1.75,1.4;2.55,2.3];
%currentLocation=[0.75,2.2];
locationHistory=zeros(size(currentLocation,1),2,Number_Of_Steps+1);
locationHistory(:,:,1)=currentLocation;
ne=size(currentLocation,1);
summit=zeros(ne,1);
%colorOptions=[‘r’,’g’,’b’,’m’,’y’,’w’,’c’];
%% Take Steps
stepScale=Step_Scale_Factor;
theta=0;
for stepNum=1:Number_Of_Steps
for i=1:ne
if ~summit(i) %if that explore has not summitted already
pNow=currentLocation(i,:);
moveTest=[Fy(pNow(1),pNow(2)),Fx(pNow(1),pNow(2))].*stepScale;
%pTest=pNow+moveTest+moveTest.*(randi([-pRand,pRand],1,2)./100).*Step_Rand;%add rand if it is turned on
if Step_Rand
theta=randi([-randAngle,randAngle],1,1)*pi/180;
end
pTest=pNow+moveTest*[cos(theta),sin(theta);-sin(theta),cos(theta)];
if getZ(pNow(1),pNow(2))<getZ(pTest(1),pTest(2)) %if the new point is higher
currentLocation(i,:)=pTest; %move
locationHistory(i,:,stepNum+1)=pTest; %update history
else
summit(i)=1; %otherwise they have summitted
end
end
end
end
%% Animation Frames
%frame parameters
b=[0,50,50,100];
pos = get(gcf, ‘Position’); %// gives x left, y bottom, width, height
width = pos(3);
height = pos(4);
fr=[b(1),b(2),width-b(3),height-b(4)];
zOffset=0.02;
title(‘Start’)
for stepNum=1:Number_Of_Steps
for i=1:ne
pNow=locationHistory(i,:,stepNum);
if sum(pNow)~=0
scatter3(pNow(2),pNow(1),getZ(pNow(1),pNow(2))+zOffset,75,’Filled’,colorOptions(i))
if stepNum~=1
pOld=locationHistory(i,:,stepNum-1);
scatter3(pOld(2),pOld(1),getZ(pOld(1),pOld(2))+zOffset,60,’Filled’,’k’)
title([‘Step Number’ ‘ ‘ num2str(stepNum-1)])
end
end
end
% Get frame now
M(stepNum)= getframe(1,fr);
end
%% Save Animation
movie_obj = VideoWriter(Animation_File);
movie_obj.FrameRate=Frame_Rate;
open(movie_obj);
startImageLen=4;
for K= 1:startImageLen
this_image = M(1);
writeVideo(movie_obj, this_image);
end
for K = 1:length(M)
this_image = M(K);
writeVideo(movie_obj, this_image);
end
close(movie_obj);
function Z=getZ(North,East)
X=East-1.5;
Y=North-1.5;
Z = sin(X.*pi).*cos(Y.*pi).*exp(-sqrt(X.*X+Y.*Y))./2+0.5;
end
