Answers.Body: <p>I was hoping to see more answers here, but I'll get us started with some examples:</p>
  
  <p><strong><em>Combinatorial Search Problems</em></strong>: If your problem can be phrased as movement through a <a href="https://en.wikipedia.org/wiki/Combinatorics#Graph_theory" rel="noreferrer">combinatorial graph</a>, 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 <a href="https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search" rel="noreferrer">iterative deepening search</a>. 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 href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="noreferrer">A* search</a> instead. Common applications for these techniques include pathfinding in video games (or directions in other applications), AI planning, and Automated Theorem Proving.</p>
  
  <p>I'll add some more topics later, but I suspect others have expertise to share here. Let's see some more ideas!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-27T12:35:04.057Z
Answers.LastActivityDate: 2018-08-27T12:35:04.057Z
Answers.UserDisplayName: John Doucette
Answers.Body: <p>A nice example <a href="https://en.wikipedia.org/wiki/Markov_decision_process" rel="nofollow noreferrer">Markov Decision Processes</a>, which can be solved by classic <a href="https://en.wikipedia.org/wiki/Reinforcement_learning" rel="nofollow noreferrer">reinforcement learning</a> techniques like <a href="https://en.wikipedia.org/wiki/Q-learning" rel="nofollow noreferrer">Q learning</a>.</p>
  <p>A Markov Decision Process consists of</p>
  <ol>
  <li>A set of <em>discrete states</em> (or continuous states that have been discretized)</li>
  <li>A set of possible <em>actions</em> that can be taken in each state.</li>
  <li>A set of <em>transition probabilities</em> that describe how an agent stochastically moves from its current state to the next, based on the agent's actions.</li>
  <li>A <em>reward function</em> quantitatively describing how nice it is to be in each state.</li>
  <li>A <em>discounting factor</em> that describes how much worse it is to receive a reward in the future than today.</li>
  </ol>
  <p>Very small MDPs can be directly, exactly, solved, using techniques like <a href="https://artint.info/html/ArtInt_227.html" rel="nofollow noreferrer">value iteration</a>, but the computational cost for these approaches grows extremely fast.</p>
  <p>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.</p>
  <p>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 &quot;optimal rule of action&quot; for your agent.</p>
  <p>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.</p>
  <p>You can find a nice QL tutorial <a href="http://adventuresinmachinelearning.com/reinforcement-learning-tutorial-python-keras/" rel="nofollow noreferrer">here</a> (normal and deep).</p>
  <p>And a lecture about QL <a href="https://www.youtube.com/watch?v=lvoHnicueoE" rel="nofollow noreferrer">here</a>.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-18T11:45:29.857Z
Answers.Text: RL/MDP is really a bad example of a problem that doesn't require a neural network, given that the main recent successes in RL use neural networks.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-28T08:46:30.983Z
Answers.LastActivityDate: 2021-01-18T11:30:36.640Z
Answers.LastEditDate: 2021-01-18T11:30:36.640Z
Answers.UserDisplayName: 16Aghnar
Answers.Body: <h2>Image Segmentation with Unsupervised Learning</h2>
  <p>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.</p>
  <h3>K-means for image segmentation</h3>
  <p>When you identify the pixels of an RGB image to vectors in <span class="math-container">$\mathbb{R}^3$</span>, you can run the <a href="https://en.wikipedia.org/wiki/K-means_clustering" rel="nofollow noreferrer">classic k-means algorithm</a> 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 <span class="math-container">$\mathbb{R}^5$</span>). You can run again a k-means algorithm to segment your image in superpixels. You can read about that <a href="https://www.researchgate.net/publication/225069465_SLIC_Superpixels_Compared_to_State-of-the-Art_Superpixel_Methods" rel="nofollow noreferrer">SLIC Superpixels Compared to State-of-the-Art Superpixel Methods</a> (2012), Achanta et al.</p>
  <p><strong>Example</strong></p>
  <p>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.</p>
  <p><a href="https://i.sstatic.net/8rVjS.jpg?s=128" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8rVjS.jpg?s=128" alt="enter image description here" /></a>
  <a href="https://i.sstatic.net/v6Iy1.jpg?s=128" rel="nofollow noreferrer"><img src="https://i.sstatic.net/v6Iy1.jpg?s=128" alt="enter image description here" /></a>
  <a href="https://i.sstatic.net/NtsF5.jpg?s=128" rel="nofollow noreferrer"><img src="https://i.sstatic.net/NtsF5.jpg?s=128" alt="enter image description here" /></a></p>
  <h3>Similarity graph and normalized cut</h3>
  <p>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   <span class="math-container">$d(p_1, p_2) = exp(-\sum{(p_{1,i} - p_{2,i})^2}), i \in (r, g, b)$</span>. Then, build the graph over the whole image, and divide it iteratively, using the <a href="https://en.wikipedia.org/wiki/Segmentation-based_object_categorization" rel="nofollow noreferrer">Normalized Cut algorithm</a>.</p>
  <h3>Morphological gradients</h3>
  <p>Here, image segmentation is done by computing the <a href="https://en.wikipedia.org/wiki/Morphological_gradient" rel="nofollow noreferrer">morphological gradient</a> 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.</p>
  <p>An example, still with the seagull. (Morphological gradient computed on a grayscaled input). The seagull appears more clearly.</p>
  <p><a href="https://i.sstatic.net/I9kte.jpg?s=256" rel="nofollow noreferrer"><img src="https://i.sstatic.net/I9kte.jpg?s=256" alt="enter image description here" /></a>
  <a href="https://i.sstatic.net/l5CKx.jpg?s=256" rel="nofollow noreferrer"><img src="https://i.sstatic.net/l5CKx.jpg?s=256" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-28T20:33:11.370Z
Answers.Text: 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.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-02T14:04:41.017Z
Answers.Text: 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
Answers.UserDisplayName: 16Aghnar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-28T20:16:59.007Z
Answers.LastActivityDate: 2021-01-18T11:41:55.693Z
Answers.LastEditDate: 2021-01-18T11:41:55.693Z
Answers.UserDisplayName: 16Aghnar
Body: <p>A lot of questions on this site seem to be asking &quot;can I use X to solve Y?&quot;, 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?</p>
  <p>I have some ideas about this, but am inspired by questions like <a href="https://bicycles.stackexchange.com/q/1195">this one</a> where a fairly wide range of views are expressed, and each answer focuses on just one possible problem domain.</p>
  <p>There are some related questions on this stack already, but they are not the same. <a href="https://ai.stackexchange.com/q/240/2444">This question</a> specifically asks what genetic algorithms are good for, whereas I am more interested in having an inventory of problems mapped to possible techniques. <a href="https://ai.stackexchange.com/q/60/2444">This question</a> asks what possible barriers are to AI with a focus on machine learning approaches, but I am interested in what we <em>can</em> do without using deep neural nets, rather than what is difficult in general.</p>
  <p>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.</p>
  <p>Finally, <a href="https://ai.stackexchange.com/q/2999/2444">this question</a> 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, &quot;solving chess&quot; isn't a problem, but &quot;determining how to optimally play turn-based games without randomness&quot; is.</p>
  
Tags: <neural-networks><machine-learning><deep-neural-networks><symbolic-ai>
Title: What kinds of problems can AI solve without using a deep neural network?
UserDisplayName: John Doucette
ThreadText: # What kinds of problems can AI solve without using a deep neural network?
  
  (Asked by: username_0 on 2018-08-17)
  
  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](https://bicycles.stackexchange.com/q/1195) 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](https://ai.stackexchange.com/q/240/2444) 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](https://ai.stackexchange.com/q/60/2444) 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](https://ai.stackexchange.com/q/2999/2444) 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.
  
  **Tags:** neural-networks, machine-learning, deep-neural-networks, symbolic-ai
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_0 on 2018-08-27. Score: 5
  
  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](https://en.wikipedia.org/wiki/Combinatorics#Graph_theory), 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](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_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](https://en.wikipedia.org/wiki/A*_search_algorithm) 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 by username_1 on 2018-08-28. Score: 4
  
  A nice example [Markov Decision Processes](https://en.wikipedia.org/wiki/Markov_decision_process), which can be solved by classic [reinforcement learning](https://en.wikipedia.org/wiki/Reinforcement_learning) techniques like [Q learning](https://en.wikipedia.org/wiki/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](https://artint.info/html/ArtInt_227.html), 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](http://adventuresinmachinelearning.com/reinforcement-learning-tutorial-python-keras/) (normal and deep).
  
  And a lecture about QL [here](https://www.youtube.com/watch?v=lvoHnicueoE).
  
  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.
  
  > **Comments:**
  > **username_2**: RL/MDP is really a bad example of a problem that doesn't require a neural network, given that the main recent successes in RL use neural networks.  
  
  ---
  
  ### Answer by username_1 on 2018-09-28. Score: 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](https://en.wikipedia.org/wiki/K-means_clustering) 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](https://www.researchgate.net/publication/225069465_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.
  
  [![enter image description here](https://i.sstatic.net/8rVjS.jpg?s=128)](https://i.sstatic.net/8rVjS.jpg?s=128)
  [![enter image description here](https://i.sstatic.net/v6Iy1.jpg?s=128)](https://i.sstatic.net/v6Iy1.jpg?s=128)
  [![enter image description here](https://i.sstatic.net/NtsF5.jpg?s=128)](https://i.sstatic.net/NtsF5.jpg?s=128)
  
  ### 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](https://en.wikipedia.org/wiki/Segmentation-based_object_categorization).
  
  ### Morphological gradients
  
  Here, image segmentation is done by computing the [morphological gradient](https://en.wikipedia.org/wiki/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](https://i.sstatic.net/I9kte.jpg?s=256)](https://i.sstatic.net/I9kte.jpg?s=256)
  [![enter image description here](https://i.sstatic.net/l5CKx.jpg?s=256)](https://i.sstatic.net/l5CKx.jpg?s=256)
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: 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  
  
  ---
  
  