Differential Geometry (Notes from Prof. David Forsyth's lectures at UIUC): PART 2

Reimannian Geometry

Extrinsic vs Intrinsic Geometry

Prior to Riemann, geometry was studied from an extrinsic point of view, i.e, lines, curves and surfaces were considered to be embedded in a Euclidean space which adhered to the usual notions of distances, angles, translation and rotations. But Gauss showed through his Theorema Egregium, that Gaussian curvature is intrinsic, that is it can be computed by measuring angles, distances and their rates on the surface without considering the embedding itself (recall that $\kappa=\det(-I^{-1}II)$). That means that the embedding can often be ignored while studying certain geometric properties which are intrinsic. 

But this means, that properties like Gaussian curvature are invariant to isometry, i.e. deformations that bend the surface without stretching or contraction since local geometric properties are preserved. This in turn implies that a sphere could never be unwrapped onto a plane surface without stretching or contraction of the surface because a plane has a 0 Gaussian curvature whereas a sphere has a Gaussian curvature of 1. This basically says you cannot map all of earth in a single chart without messing up distances between far away cities or areas of continents? So what do we do? We build an atlas consisting of multiple charts where each chart provides a good approximation of local distances and angles in a specific location on the earth. The motivation behind Reimannian geometry and the concept of Manifold is similar.

Now let us define a few terms in a top down fashion - earlier definitions use terms or details that are defined later on.

Riemannian Geometry

Branch of differential geometry that deals with Riemannian Manifolds.

Riemannian Manifold

A smooth manifold $M$ equipped with an inner product $g_p$ (Riemannian metric such as $I$) on tangent space (vector space of tangents at a point) $T_pM$ at each point $p$ that varies smoothly from point to point. Meaning that if $X$ and $Y$ are vector fields on $M$, then $g_p(X(p),Y(p))$ is a smooth function.

Manifold

A topological space that locally resembles a Euclidean space. Meaning that each point of the $n$-dimensional manifold is homeomorphic to a Euclidean space of the same dimension. 

Homeomorphism

A function $\phi$ between topological spaces $U$ and $\Omega$ in $\mathbb{R}^n$ such that

• $\phi$ is one-to-one and onto
• $\phi$ is continuous
• $f^{-1}$ is continuous

$C^p$ Atlas

A $C^p$ atlas on $M$ is given by

• An open cover $\{U_i | i \in I\}$ of $M$
• A family of homeomorphisms $\phi_i : U_i \rightarrow \Omega_i$
• For all $i,j\in I$, $\phi_j \circ \phi_i^{-1}$ is a $C^p$ diffeomorphism  (differentiable homeomorphism) from $\phi_i(U_i \cap U_j)$ to $\phi_j(U_i \cap U_j)$

$(U_i, \phi_i)$ together define a $chart$.

Search Algorithms in AI

Search in AI

Many problems in AI can be formulated as finding a sequence of actions that lead us from the current state to one of the goal states, for instance finding the shortest path through a maze. Such problems can be categorized as follows:

• Based on the nature of search space: Discrete vs Continuous 
• Based on the type of percept or information available: Uninformed vs Informed
• Based on the type of solution desired: Global vs Local 
• Based on ability to find optimal solution: Complete vs Incomplete
• Based on the environment: Deterministic vs Non-deterministic
• Miscellaneous: Adversarial 

Searching as traversing a tree

When the search space is discrete it is possible to enumerate all possible sequence of states that can be reached from a given state. This is often done in the form of a tree where the nodes represent states and branches represent actions that can be taken at a particular state. Leaves of such a tree are reached as a result of taking a finite sequence of actions that either end in a goal state or a dead-end. Goal states might also occur at non-leaf nodes. Any path from the root node to the goal node is a valid solution sequence but often we are looking for shortest sequence that gets us to the goal. If at any state the maximum number of possible actions/branches is $b$ and the maximum length of action sequences is $l$, then searching for the goal can take upto $\mathcal{O}(b^l)$ time. Some brute force search algorithms are:

• Breadth-First Search: Expand the node at the shallowest depth
• Depth-First Search: Expand the node at the deepest depth
• Uniform-Cost Search (Dijkstra): Expand the node with the smallest cost of reaching it from the root
• Iterative Deepening Search: Repeatedly run DFS with increasing depth limits
• Bidirectional Search: Search from both start and goal until the paths meet 

In cases where no additional information is available about the states these are the only options. However, when additional information is available to guide the search other possibilities exist:

• A*: Expand the node $n$, with the lowest $C(n)+h(n)$ where $C(n)$ is the cost of reaching that node and $h(n)$ is an estimate of closeness to goal. This algorithm is complete iff $h(.)$ is admissible, meaning that it never overestimates the distance to goal, for instance straight line distance to the target on a map. 
• Branch & Bound: Perform an inorder traversal of tree while updating the bounds on the optimal solution based on the information available at the node each time it is visited. If the bound at node $n$ does not have an intersection with its parent then prune the subtree.  

Searching as exploring the energy landscape

In discrete or combinatorial optimization problems with some kind of structure and an available energy function to measure the goodness of the solution (more energy meaning a better solution), one can explore the local neighborhood of a current state to incrementally improve the solution. Some algorithms in this domain are:

• Hill Climbing: Move the neighboring state which results in maximum increase in energy until no neighbor can increase the energy
• Simulated Annealing: Randomly choose a neighboring state and if it the change in energy $\nabla E$ is positive then accept the move. Else accept the move with probability $e^{\nabla E/T}$ where T decreases with each iteration
• Local Beam Search: Keep track of $k$ best states rather than just $1$. In each iteration generate all $k$ successors of all $k$ states and select the $k$ best
• Genetic Algorithms: Begin with a population. Assign a fitness score to each member. Choose pairs for cross over with probability proportional to the fitness score. Merge/Cross over the members in each pair. Mutate the result and iterate

Searching in continuous spaces

Two simplest algorithms are:

• Gradient Ascent: $x \leftarrow x + \alpha\nabla f$
• Newton Raphson: Used to find zeros of a function. Maxima occurs when the gradient is $0$ leading to $x = x - H^{-1}(x)\nabla f(x)$

Searching with non-deterministic actions

If actions can lead to stochastic transition behaviour, then contingencies need to be planned for. This usually amounts to constructing an AND-OR search tree and modified version of DFS algorithm to look for goal while handling cycles appropriately. Some of the paths from the root lead to loops while others lead to goal state. One needs to find the path which avoids the loop. 

Searching in presence of adversary

Searching in presence of adversary amounts to playing a two player, zero sum game (utility values at the end of the game are always equal and opposite). Optimal decision can be taken by using the minimax algorithm. First a state space search tree is created. The minimax value (utility of being in a state assuming both players play optimally from there to the end of the game) at each node is then defined as being one of the following:

• Terminal state: Predefined for instance $\{0, 1, 0.5\}$ for outcomes {Checkmate, Win, Draw} in chess
• Our (max's) turn: Choose the action that leads to a state of maximum minimax 
• Adversary's turn: Choose the action that lead to a state of minimum minimax 

However, sometimes the search tree might be exponentially large to enumerate all possible state sequences. Alpha-Beta Pruning can be used to prune out subtrees early on avoiding further search along those paths. It is a form of Branch & Bound algorithm where an inorder-DFS-traversal is performed in the tree and whenever a node is revisited the bound on the minimax value is updated based on the children that have been observed so far. If the bound on a node has a null intersection with its parent then the subtree situated at that node is pruned out.