<commit_before>---
layout: post
title: Artificial Intelligence 

images:
    - url: https://www.deepcoredata.com/wp-content/uploads/2016/06/small_1420.png
      alt: Artificial Intelligence
      title: ida*
---

## Determining Intelligence

#### Turing Test
The Turing Test is a test devised by <NAME>. The test calls for a computer and a human to be put in two seprate rooms, and another human to converse with both the human and the computer. If the human observer thinks he/she is talking to another human, the computer is said to have passed the Turing test. 

#### Winograd Schema
Winograd Schema are another series of problems that are used to test for understanding.
The idea is to have a sentence, with two possible meanings and to let the computer pick two choices that make sense. 

E.g. The city councilmen refused the demonstrators a permit because they [feared/advocated] violence. Who [feared/advocated] violence?


## Search
Many problems, such as 8-puzzles, n-queens, or solving a rubic's cube can be formulated as search problems.

### Formulating Search Problems
All search problems should have these parts:
+ **initial state** - This is the initial state that is given to the search problem
+ **goal state** - There may be more than one goal state. It is the state at which the search problem is solved.
+ **transition model/successor function** - Describes how to move from one state to another given an action. 
+ **action** - Each action changes the current state. Each action may also have an associated cost with it. 

The goal is to find a sequence of actions to move from the initial state to the goal state and minimize the cost of your actions

### Solving Search Problems
The idea behind solving all search problems is the same.
```
frontier = {I}
loop:
    if frontier is empty:
        return FALSE
    node = some node in the frontier
    if goal == node:
        return current state
    generate the node's children
    add the node's children to the frontier and "explored set"
```
A search strategy is said to be **complete** if it finds a solution if one exsists.

A search strategy is said to be **optimal** if the solution it finds is the one with the least cost.

The **seperation property** states that if the frontier seperates all explored states from all non-explored states that the search strategy is **optimal**

The **branching factor** describes how many actions you can take in a given state. If this number is not constant, the average branching factor or the max branching factor is usually used.

#### Breath First Search
The idea of BFS is to search the closest nodes first. To implement it, we use a queue (FIFO) to represent the frontier. 
However the problem with BFS is that it is exponential in time and space. Exponential time is not as large of a problem as exponential space, as we quickly run out of memory.
We can see that in order to expand all the nodes down to our solution depth, $$d$$, we would have to expand $$b^d$$ nodes, where $$b$$ is the branching factor. 

Let $$N(b, d)$$ be the number of nodes generated for a problem with branching factor $$b$$ and solution at depth $$d$$.

$$N(b, d) = b^d + b^{d-1} + \ldots + 1$$

$$b \times  N(b, d) = b^{d+1} + b^{d-1} + \ldots + b$$

$$b \times  N(b, d)  - N(b,d)= b^{d+1} - 1$$

$$N(b, d) = \frac{b^{d+1} + 1}{b-1} \approx \frac{b^{d+1}}{b-1} \approx b^d \times \frac{b}{b-1}$$

#### DFS
In DFS, we try to go as deep as possible first. To implement this, we use a stack (FILO) to represent the frontier.
We can see that our "explored set" needs only to be $$bd$$ rather than $$b^d$$. However, DFS is not optimal - our solution may not be the best one.

For both BFS and DFS, the number of nodes generated is 

$$N(b, d) \approx b^d \times \frac{b}{b-1}$$

#### Iterative Deepening Search
The idea of Iterative Deepening Search is to do Depth Limited Serach (DFS with a depth limit), gradually increasing the depth each time. This maintains the ideal properties of $$bd$$ space. While it may seem wasteful to regenerate each node, it actually only requires twice the work, maintaining an $$b^d$$ runtime as well as optimality.


Let $$N(b, d)$$ be the number of nodes generated by DFS for a problem with branching factor $$b$$ and solution at depth $$d$$.
We know from above that

$$N(b, d) \approx b^d(\frac{b}{b-1})$$

Let $$N'(b, d)$$ be the number of nodes generated by Iterative Deepening for a problem with branching factor $$b$$ and solution at depth $$d$$. 
Since iterative deepening runs for each depth from $$1$$ until $$d$$, we can express the number of nodes generated as a sum.

$$N'(b, d) = \sum_{i = 1}^{d}{b^i(\frac{b}{b-1})}$$

$$N'(b, d) = (\frac{b}{b-1})\sum_{i = 1}^{d}{b^i}$$

Now we can see that $$\sum_{i = 1}^{d}{b^i}$$ is the exact same equation we had for DFS before, so we et

$$N'(b, d) = (\frac{b}{b-1})^2b^d$$

$$\frac{b}{b-1}$$ is the difference between running DFS and ID.
Since $$b > 1$$, at most it is a 2x more work. We can see that even for relatively small $$b$$ ($$b=10$$) that it is just 1.1x more work.

#### Comparison

|        |BFS       |DFS       |ID        |
|--------|----------|----------|----------|
|Time    |$$O(b^d)$$|$$O(b^d)$$|$$O(b^d)$$|
|Space   |$$O(b^d)$$|$$O(bd)$$|$$O(bd)$$|
|Optimal | Y        |  N       |   Y      |
|Complete | Y        |  Y       |   Y      |

### Solving Search Problems with Cost

#### Uniform Cost Search
Nodes are expanded in increasing order of cost. Therefore, whatever we expand will have a larger cost.

#### Best First Search
An estimate of the cost at the current state is needed $$h(x)$$, or a heurestic function.
We can then use a greedy search - try to take the biggest bite at the current distance.
However, while this search strategy is complete it is not optimal.

#### Determining a Heurestic
Our heurestic is **consistent** if $$h(n) \leq c(n, a, n') + h(n')$$ where $$h(n)$$ is the cost for a node $$n$$, $$c(n, a, n')$$ is the cost to the goal state $$a$$ through $$n'$$. This means that the estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the cost of reaching that neighbor.

Our heurestic is **admissable** if it never overpredicts the distance to the goal state. This means that $$h(n) \leq h^*(n)$$, where $$h^*(n)$$ is the actual cost to reach the goal state.

One easy way to generate heurestics is to relax the constraints of a problem. 

#### A\* Search
We can improve upon best first search by taking into account the cost used to get to a node as well as the predicted cost. We can model this with the function

$$f(n) = g(n) + h(n)$$

$$g(n)$$ = the cost to get to the current node

$$h(n)$$ = the predicted, heurestic cost to get to the final solution

Note that if $$h(n) = 0$$, then A\* is just Uniform Cost Search

A\* Search is optimal if our heurestic is both **consistent** and **admissable**.
For

### Local Search Strategies
+ Gradient Descent  
+ [Simulated Annealing](https://jcaip.github.io/Simulated-Annealing/)
+ [Genetic Algorithms](https://jcaip.github.io/Genetic-Algorithm/)

## Constraint Satisfaction
Constraint Graph

#### Types of Constraints
+ Unary Constraint - Constraints involving just one variable ($$A > 0$$).
+ Binary Constraint - Constraints involving two variables ( $$A \neq B$$).
+ Global Constraint - Constraints involving two or more variables ( $$A \neq B \neq C$$)

### Solving Contraint Satisfaction Problems
One property we seek to exploit when 
<commit_msg>Added artificial intelligence post<commit_after>---
layout: post
title: Artificial Intelligence 

images:
    - url: https://www.deepcoredata.com/wp-content/uploads/2016/06/small_1420.png
      alt: Artificial Intelligence
      title: ida*
---

## Determining Intelligence

#### Turing Test
The Turing Test is a test devised by <NAME>. The test calls for a computer and a human to be put in two seprate rooms, and another human to converse with both the human and the computer. If the human observer thinks he/she is talking to another human, the computer is said to have passed the Turing test. 

#### Winograd Schema
Winograd Schema are another series of problems that are used to test for understanding.
The idea is to have a sentence, with two possible meanings and to let the computer pick two choices that make sense. 

E.g. The city councilmen refused the demonstrators a permit because they [feared/advocated] violence. Who [feared/advocated] violence?


## Search
Many problems, such as 8-puzzles, n-queens, or solving a rubic's cube can be formulated as search problems.

### Formulating Search Problems
All search problems should have these parts:
+ **initial state** - This is the initial state that is given to the search problem
+ **goal state** - There may be more than one goal state. It is the state at which the search problem is solved.
+ **transition model/successor function** - Describes how to move from one state to another given an action. 
+ **action** - Each action changes the current state. Each action may also have an associated cost with it. 

The goal is to find a sequence of actions to move from the initial state to the goal state and minimize the cost of your actions

### Solving Search Problems
The idea behind solving all search problems is the same.
```
frontier = {I}
loop:
    if frontier is empty:
        return FALSE
    node = some node in the frontier
    if goal == node:
        return current state
    generate the node's children
    add the node's children to the frontier and "explored set"
```
A search strategy is said to be **complete** if it finds a solution if one exsists.

A search strategy is said to be **optimal** if the solution it finds is the one with the least cost.

The **seperation property** states that if the frontier seperates all explored states from all non-explored states that the search strategy is **optimal**

The **branching factor** describes how many actions you can take in a given state. If this number is not constant, the average branching factor or the max branching factor is usually used.

#### Breath First Search
The idea of BFS is to search the closest nodes first. To implement it, we use a queue (FIFO) to represent the frontier. 
However the problem with BFS is that it is exponential in time and space. Exponential time is not as large of a problem as exponential space, as we quickly run out of memory.
We can see that in order to expand all the nodes down to our solution depth, $$d$$, we would have to expand $$b^d$$ nodes, where $$b$$ is the branching factor. 

Let $$N(b, d)$$ be the number of nodes generated for a problem with branching factor $$b$$ and solution at depth $$d$$.

$$N(b, d) = b^d + b^{d-1} + \ldots + 1$$

$$b \times  N(b, d) = b^{d+1} + b^{d-1} + \ldots + b$$

$$b \times  N(b, d)  - N(b,d)= b^{d+1} - 1$$

$$N(b, d) = \frac{b^{d+1} + 1}{b-1} \approx \frac{b^{d+1}}{b-1} \approx b^d \times \frac{b}{b-1}$$

#### DFS
In DFS, we try to go as deep as possible first. To implement this, we use a stack (FILO) to represent the frontier.
We can see that our "explored set" needs only to be $$bd$$ rather than $$b^d$$. However, DFS is not optimal - our solution may not be the best one.

For both BFS and DFS, the number of nodes generated is 

$$N(b, d) \approx b^d \times \frac{b}{b-1}$$

#### Iterative Deepening Search
The idea of Iterative Deepening Search is to do Depth Limited Serach (DFS with a depth limit), gradually increasing the depth each time. This maintains the ideal properties of $$bd$$ space. While it may seem wasteful to regenerate each node, it actually only requires twice the work, maintaining an $$b^d$$ runtime as well as optimality.


Let $$N(b, d)$$ be the number of nodes generated by DFS for a problem with branching factor $$b$$ and solution at depth $$d$$.
We know from above that

$$N(b, d) \approx b^d(\frac{b}{b-1})$$

Let $$N'(b, d)$$ be the number of nodes generated by Iterative Deepening for a problem with branching factor $$b$$ and solution at depth $$d$$. 
Since iterative deepening runs for each depth from $$1$$ until $$d$$, we can express the number of nodes generated as a sum.

$$N'(b, d) = \sum_{i = 1}^{d}{b^i(\frac{b}{b-1})}$$

$$N'(b, d) = (\frac{b}{b-1})\sum_{i = 1}^{d}{b^i}$$

Now we can see that $$\sum_{i = 1}^{d}{b^i}$$ is the exact same equation we had for DFS before, so we et

$$N'(b, d) = (\frac{b}{b-1})^2b^d$$

$$\frac{b}{b-1}$$ is the difference between running DFS and ID.
Since $$b > 1$$, at most it is a 2x more work. We can see that even for relatively small $$b$$ ($$b=10$$) that it is just 1.1x more work.

#### Comparison

|        |BFS       |DFS       |ID        |
|--------|----------|----------|----------|
|Time    |$$O(b^d)$$|$$O(b^d)$$|$$O(b^d)$$|
|Space   |$$O(b^d)$$|$$O(bd)$$|$$O(bd)$$|
|Optimal | Y        |  N       |   Y      |
|Complete | Y        |  Y       |   Y      |

### Solving Search Problems with Cost

#### Uniform Cost Search
Nodes are expanded in increasing order of cost. Therefore, whatever we expand will have a larger cost.

#### Best First Search
An estimate of the cost at the current state is needed $$h(x)$$, or a heurestic function.
We can then use a greedy search - try to take the biggest bite at the current distance.
However, while this search strategy is complete it is not optimal.

#### Determining a Heurestic
Our heurestic is **consistent** if $$h(n) \leq c(n, a, n') + h(n')$$ where $$h(n)$$ is the cost for a node $$n$$, $$c(n, a, n')$$ is the cost to the goal state $$a$$ through $$n'$$. This means that the estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the cost of reaching that neighbor.

Our heurestic is **admissable** if it never overpredicts the distance to the goal state. This means that $$h(n) \leq h^*(n)$$, where $$h^*(n)$$ is the actual cost to reach the goal state.

One easy way to generate heurestics is to relax the constraints of a problem. 

#### A\* Search
We can improve upon best first search by taking into account the cost used to get to a node as well as the predicted cost. We can model this with the function

$$f(n) = g(n) + h(n)$$

$$g(n)$$ = the cost to get to the current node

$$h(n)$$ = the predicted, heurestic cost to get to the final solution

Note that if $$h(n) = 0$$, then A\* is just Uniform Cost Search

A\* Search is optimal if our heurestic is both **consistent** and **admissable**.

For any node $$n$$, along the path from the initial state $$I$$ to a goal state $$G$$ with actual cost $$c^*$$, we know that $$f(n) = g(n) + h(n) \leq c*$$, since our heurestic is both consistent and admissable.

Suppose there is some other goal state, $$G'$$, that has less cost than $$c*$$.
$$f(G') = g(G') + h(G') = g(G') \leq c*$$. However, in this case, we would expand $$G'$$ before $$n$$, so we would reach the optimal solution.

### Local Search Strategies
+ Gradient Descent  
+ [Simulated Annealing](https://jcaip.github.io/Simulated-Annealing/)
+ [Genetic Algorithms](https://jcaip.github.io/Genetic-Algorithm/)

## Constraint Satisfaction
Constraint Graph

#### Types of Constraints
+ Unary Constraint - Constraints involving just one variable ($$A > 0$$).
+ Binary Constraint - Constraints involving two variables ( $$A \neq B$$).
+ Global Constraint - Constraints involving two or more variables ( $$A \neq B \neq C$$)

### Solving Contraint Satisfaction Problems
One property we seek to exploit when 

{'fraction_non_alphanumeric': 0.11934689646235584, 'fraction_numerical': 0.005442529480368019, 'mean_word_length': 3.6972002434570905, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 9, 'https://': 6, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1778884', 'n_tokens_mistral': 4712, 'n_tokens_neox': 4471, 'n_words': 2358}