What kinds of problems can AI solve without using a deep neural network?

Question

A lot of questions on this site seem to be asking "can I use X to solve Y?", where X is usually a deep neural network, and Y is often something already addressed by other areas of AI that are less well known?

I have some ideas about this, but am inspired by questions like this one where a fairly wide range of views are expressed, and each answer focuses on just one possible problem domain.

There are some related questions on this stack already, but they are not the same. This question specifically asks what genetic algorithms are good for, whereas I am more interested in having an inventory of problems mapped to possible techniques. This question asks what possible barriers are to AI with a focus on machine learning approaches, but I am interested in what we can do without using deep neural nets, rather than what is difficult in general.

A good answer will be supported with citations to the academic literature, and a brief description of both the problem and the main approaches that are used.

Finally, this question asks what AI can do to solve problems related to climate change. I'm not interested in the ability to address specific application domains. Instead, I want to see a catalog of abstract problems (e.g. having an agent learn to navigate in a new environment; reasoning strategically about how others might act; interpreting emotions), mapped to useful techniques for those problems. That is, "solving chess" isn't a problem, but "determining how to optimally play turn-based games without randomness" is.

Answer 1

I was hoping to see more answers here, but I'll get us started with some examples:

Combinatorial Search Problems: If your problem can be phrased as movement through a combinatorial graph, you don't need a neural network. In particular, your problem should have discrete states, a clear set of actions that are possible in each state, a clear definition of where we start, and a clear definition of what the goal state looks like. The most effective general purpose technique is iterative deepening search. If you have an idea about which moves might be more effective, or better, a function that estimates how far each state is from the goal, you may be able to build a heuristic function and use A* search instead. Common applications for these techniques include pathfinding in video games (or directions in other applications), AI planning, and Automated Theorem Proving.

I'll add some more topics later, but I suspect others have expertise to share here. Let's see some more ideas!

Answer 2

A nice example Markov Decision Processes, which can be solved by classic reinforcement learning techniques like Q learning.

A Markov Decision Process consists of

1. A set of discrete states (or continuous states that have been discretized)
2. A set of possible actions that can be taken in each state.
3. A set of transition probabilities that describe how an agent stochastically moves from its current state to the next, based on the agent's actions.
4. A reward function quantitatively describing how nice it is to be in each state.
5. A discounting factor that describes how much worse it is to receive a reward in the future than today.

Very small MDPs can be directly, exactly, solved, using techniques like value iteration, but the computational cost for these approaches grows extremely fast.

Reinforcement Learning (RL) was developed as a machine learning approach for MDPs. There is a loop: the agent gets the state of the environment, chooses an action, executes this action on the environment, and he gets back a reward, and the new state of the environment, and so on... You want the agent to maximize the cumulative reward over time.

The basic concept of Q Learning doesn't use ANNs. In Q learning, you build a state-action matrix, called the Q matrix. Thus, you must discretize the states of your environment, and the actions available to your agent. Then, the coefficient Qij is the expected reward when you perform the action j on the state i. In basic Q Learning, you explore and build this matrix, and it should converge and give an "optimal rule of action" for your agent.

However, the situation is often too complex, and you often want a non-discretized space of states or actions. Here Deep QL arrives, where the Q matrix becomes an ANN.

You can find a nice QL tutorial here (normal and deep).

And a lecture about QL here.

Keep in mind that only ANNs perform well in complex situations, so you'll always see examples with ANNs, even if the basic theory doesn't require ANNs.

Answer 3

Image Segmentation with Unsupervised Learning

Deep Learning is now widely used for image classification and segmentation. However, for segmentation, some algorithms are still really effective. For example, they could also be used for the development of self-driving cars.

K-means for image segmentation

When you identify the pixels of an RGB image to vectors in $\mathbb{R}^3$, you can run the classic k-means algorithm to distinguish objects. Furthermore, you can do superpixel segmentation, by adding to all pixel vectors two components corresponding to their coordinates in the image (so it will be vectors in $\mathbb{R}^5$). You can run again a k-means algorithm to segment your image in superpixels. You can read about that SLIC Superpixels Compared to State-of-the-Art Superpixel Methods (2012), Achanta et al.

Example

Below is an example of the segmentation of picture of a seagull on a roof. On the left, we have the original image. In the middle, 3 clusters. On the right, 12 clusters. If it easily distinguishes the roof from the sky, the seagull is still unclear with 12 centroids.

Similarity graph and normalized cut

The main idea is to build a graph of similarities between pixels and then to cut the graph into subgraphs. First, you need to define a distance between pixels. For example, the colour dissimilarity, that could be $d(p_1, p_2) = exp(-\sum{(p_{1,i} - p_{2,i})^2}), i \in (r, g, b)$. Then, build the graph over the whole image, and divide it iteratively, using the Normalized Cut algorithm.

Morphological gradients

Here, image segmentation is done by computing the morphological gradient of the image. It is the difference between the dilatation and the erosion of the input image. Erosion and dilatation are equivalent to passing min() and max() filters over all subwindows of a given size.

An example, still with the seagull. (Morphological gradient computed on a grayscaled input). The seagull appears more clearly.