4
$\begingroup$

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.

I realize this is pretty broad. If you think it's too broad for the stack, please vote to close it. I suspect it might be useful to have as a kind of wiki to refer new users to as the stack grows however.

$\endgroup$
3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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 get 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 a ANN.

You can find a nice QL tutorial here (normal and deep): http://adventuresinmachinelearning.com/reinforcement-learning-tutorial-python-keras/

And a lecture about QL : https://www.youtube.com/watch?v=lvoHnicueoE

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

Hope that helps !

$\endgroup$
  • 1
    $\begingroup$ Welcome to AI.SE @16Aghnar! Q-learning is a great technique. I think you could add some more detail about the class of problems it is designed for though, which are called Markov Decision Processes. If you like, I can edit your answer to add some thoughts. $\endgroup$ – John Doucette Aug 28 '18 at 10:56
  • 1
    $\begingroup$ feel free to edit :) $\endgroup$ – 16Aghnar Aug 28 '18 at 10:59
1
$\begingroup$

Image Segmentation with Unsupervised Learning.

Deep Learning is now widely used for image classification and segmentation. However, for segmentation, some algorithm are still really effective. They could be a great solution for the development of self-driving cars for examples.

  1. K-means for image segmentation.

When you identify the pixels of an RGB image to vectors in $\mathbb{R}^3$, you can run a classic k-means algo to distinguish objects. Further more, 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 algo to segmentate your image in superpixels. You can read about that "SLIC superpixels compared to state of the art", Achanta et al (2011).

An example : segmentation of picture of seagull on a roof. left : original image. middle : 3 clusters. right 12 clusters. If it easily distinguishes the roof from the sky, the seagull is still unclear with 12 centroids.

enter image description here enter image description here enter image description here

  1. 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 algo.

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

enter image description here enter image description here

$\endgroup$
  • $\begingroup$ I'll add content to my answer in the following days. $\endgroup$ – 16Aghnar Sep 28 '18 at 20:18
  • $\begingroup$ Nice. Something to think about adding might be DBScan along with k-means, but this is exactly the sort of answer I was hoping to see here. $\endgroup$ – John Doucette Sep 28 '18 at 20:33
  • $\begingroup$ Ok, I added some illustrations. I'm not enough familiar with DBScan to write about it, but feel free to do it If you want $\endgroup$ – 16Aghnar Oct 2 '18 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.