What you will need: A piece of paper, a writing utensil, and a timer.
There is an interesting category of tasks used in psychology research called fluency tasks. Within a fixed time limit, you have to come up with as many items of a certain type as you can.
To kick off this chapter, we are going to do three different fluency tasks.
If you know more than one language, you can try these tasks in whatever language you feel most comfortable! Or even try doing them in different languages, and see how each one feels—the same or different? Here are some random generators you can use for your target letters, categories, and objects.
Task 1. Letter fluency. You will have one (1) minute to write down as many words as you can that start with a given letter. For example, if the target letter were “s,” then you might write, “swim start stop stick” etc. Multiple words that share the same stem do not count (like “swim” and “swam” and “swimming”), and no proper nouns (like “Siberia” or “Spiderman”).
Set your timer for one minute, and click below to reveal the target letter as soon as you start your timer.
Task 1. Click icon on the right to reveal target letter
Target letter: F
How many words did you come up with? As you look back at your list now, do you see any patterns? Any words you were particularly proud of? Can you remember particular strings of reasoning that led you to produce particular strings of words?
Just take a minute to reflect on what you did, and especially how you did it, and we’ll come back to this task in a bit.
Okay, next task!
Task 2. Category fluency. You will have one (1) minute to write down as many items as you can that fit into a given category. For example, if the category were “winter Olympic sports,” then you might write, “ice dancing, luge, speed skating” etc.
Set your timer for one minute, and click below to reveal the target category as soon as you start your timer.
Task 2. Click icon on the right to reveal target category
Target category: Sea animals
As with Task 1, look at your list. How many items? Any particularly good ones? We’ll come back to this task as well.
Okay, next task!
Task 3. Alternative uses test. This one is a bit different from the first two. Now, you will have three (3) minutes to write down as many uses as you can for a given object. For example, if the target object were a newspaper, you might write, “read it; roll up as flyswatter; hold over head as umbrella; use as tinder to start fire;” etc. As in this example, your uses can include both conventional uses of the object as well as creative uses.
Set your timer for three (3) minutes, and click below to reveal the target object as soon as you start your timer.
Click icon on the right to reveal target object
Target object: A single brick
How many uses were you able to come up with? Any patterns to your answers? Any interesting outliers?
5.2 Fluency tasks as a form of search, plus 5 key observations
All three of these tasks can be thought of as a form of search:
\(\Leftarrow\) What is search?
Definition 5.1 Search is the process of sifting through a large collection of possibilities to select a smaller number of things that meet some target criteria or goal.
The “large collection of possibilities” in this definition is called a search space.
\(\Leftarrow\) What is a search space?
Definition 5.2 A search space is a collection of possibilities that can be sifted through by some search process.
A central idea we shall consider throughout this book is that virtually all of the activities that we call “intelligent” can be viewed as forms of search.
In other words, “intelligence” is what you use when there are a large number of possible things that you could choose, and you want to choose just the right one or ones. This is true of the biological intelligence that we observe in humans and animals, and it is also true of the AI techniques that we develop for building artificial agents.
Next, we will analyze our three fluency tasks in more detail. This analysis will raise five observations that are all very relevant, and very central, to thinking about intelligence as search.
<Under construction. five observations>
AI is the study of how to take complex problems and:
Describe each problem in terms of one or more search spaces and associated goals.
Develop and evaluate algorithms for effectively searching through these spaces.
5.3 Examples of intelligent activities as search
<Under construction… chess, medical diagnosis, writing a poem, hiking>
We’ve talked a bit about how a search space consists of “a collection of possibilities,” and also about how this collection will have some sort of structure to it—i.e., some sort of rhyme or reason as to how the possibilities are organized within it.
A very common way of modeling the structure of a search space is to describe the space as a graph.
\(\Leftarrow\) What is a graph?
Definition 5.2 A graph is a collection of things together with the relationships among them. Each “thing” in a graph is called a node (or a vertex), and the existence of a relationship between two things is called an edge.
Before we jump into graphs and their role in search, let’s first consider graphs more generally, along with some of their variations and properties.
Graphs in their own right are the subject of entire disciplines in mathematics (e.g. graph theory) and computer science (e.g. graph algorithms). The reason they are so fantastically useful is that many, many aspects of the world can be described as “a collection of things and the relationships among them.”
For example, a love triangle can be described as a small graph. There are three nodes, representing the three people involved. Without loss of generality, and picking names totally at random, let us call them Bella, Edward, and Jacob. The simplest description of the love triangle would be to have these three nodes, and then add edges between Bella and Edward, and also between Bella and Jacob. Classic love triangle conundrum.
Or, we could add a little bit more information by labeling these edges as “love” edges. And then, we could add an “antagonism and jealousy” edge that goes between Edward and Jacob.
“But wait!” the attentive reader exclaims. “The love edge between Bella and Edward is not at all the same as the one between Bella and Jacob!”
Good point! But that can be easily fixed by adding yet more information to our graph. First, we can make the edges uni-directional instead of bi-directional, i.e., arrows instead of just lines. Then, we can have regular “loves” arrows going from Bella to Edward, from Edward to Bella, and from Jacob to Bella. And then we can add a different kind of arrow from Bella to Jacob, something like, “loves but in a different way.”
We could also assign numerical scores to the edges, to reflect the strength of the relationship. For example, let us add a fourth node—again, picking a name totally at random, let’s call it Mike. Mike also loves Bella, but with an edge strength of about 0.05, while Edward loves Bella with an edge strength of 1,000.
<Under construction. Add diagram.>
This is a silly little example to be sure, but it illustrates several important properties of graphs:
Nodes in a graph can have information associated with them, and so they are often designated to represent some conceptual entities in the world. Nodes can be assigned to stand for people, places, things, ideas, etc.
In graph theory, hypergraphs are a variation on graphs in which edges can connect more than two nodes, but we won’t get into those here.
Each edge connects exactly two nodes. And, for any two nodes in a graph, they are either connected or not connected.
Multigraphs are a variation on graphs in which two nodes can be connected by more than one (undirected) or two (directed) edges, but we won’t get into those here either.
Edges can be bidirectional (e.g., a line segment connecting two nodes) or uni-directional (e.g., an arrow pointing from one node to another.) Graphs with bidirectional edges are called undirected graphs, while graphs with uni-directional edges are called directed graphs. Undirected graphs can have at most one edge between any two nodes, while directed graphs can have up to two edges between two nodes, i.e., one going in each direction.
Edges can either be plain (e.g., just an unspecified connection between two nodes) or they can be labeled in some way. Labels can be categorical (e.g., “love” versus “antagonism”), and/or they can have real-valued numerical labels, which are often called weights or costs.
<to add: trees are directed acyclic graphs.>
Coming back to search, it turns out that graphs (including all of the variations listed above) are very handy tools for modeling search spaces, because: the “collection of possibilities” in a search space can be modeled as the set of nodes in a graph, and the ways in which an intelligent agent can “sift through” the space, moving from one possibility to the next, can be modeled as the set of edges in the graph.
5.5 Examples of search spaces as graphs
Searching for something across different spatial locations is one of the most straightforward examples of modeling a search space as a graph. For example, consider the task of driving around. We can model various locations as nodes, and roads as edges. Then, finding a path from your house to the airport can be done by finding a series of connected nodes in the graph that lead from your house node to the airport node.
<Add discussion of directed versus undirected, and weighted versus unweighted.>
<Under construction. Add diagram.>
Or, consider the task of finding your keys in your house. Different locations in your house can be the nodes, and all of the patches of floor that you walk on to get around can be the edges.
<Under construction. Add diagram.>
While these two examples are similar in some ways, they are also different in one important way. In the first example, the goal of the search involves finding a path through the search graph, i.e., a connected sequence of nodes. In the second example, the goal of the search is not really about the path as much as it is about just finding the single node (coffee table, backpack, couch cushions, refrigerator, …) that happens to contain your keys at that moment. Throughout this book, we will see many examples of both of these types of search goals.
Searching for a sequence across time is also a very common example of modeling a search space as a graph. For example, suppose you are very grumpy right now, and you are trying to figure out how to improve your mood. Let your current mood be a node in a graph, and let the edges coming out from this node represent the different choices that are available to you: take a nap, go for a walk, keep reading this book, eat some ice cream, etc. Each edge will take you to some other mood-node, and you might search through these possibilities to figure out which temporal “path” to take through your day in order to be in a good mood at the end.
<Under construction. Add diagram.>
Many games are also easily modeled as sequences through time: each node in the graph represents a possible state of the game at a given moment, and edges in the graph represent how the game can transition from one state into another. This applies to board games, card games, video games, etc.
<Under construction. Add diagram.>
Finally, some search spaces are modeled as graphs primarily to capture the limitations or idiosyncrasies of the intelligent agent that is doing the searching, even if there are no obvious physical or temporal restrictions on the possibilities being searched. For example, consider the very first task we started with in this chapter, letter fluency. Let all of the words you know be modeled as nodes in a graph. Then, edges in this graph can represent the leaps between words that your mind might make as you are performing the task. Now, there is no a priori reason that you can’t jump from a particular word to any other word. However, the word jumps you would end up making likely reflect many obscure aspects of how your mind organizes and accesses information in a given moment. So, this particular graph is not as well-defined as, say, a graph of locations and roads in a city. But we can still use such a graph to model your search process on this task.
wordnet
For example, if the target letter were “s,” then if you thought of the word “start,” it is likely that there is an edge going from “start” to “stop,” and your next word might come out to be “stop.” <Add something about word associations.>
<Add example of starting with a word and perturbing letters.>
<Add example of picking words at random from a dictionary.>
<In some cases, it might seem like the search graph is a function of the environment, but it is also a function of the agent. Affordances! picking up crumbs example.>
<Exercises: web surfing. 6 degrees of kevin bacon. erdos-bacon-sabbath number.>
5.6 Estimating the complexity of a search space
5.7 A very simple search algorithm
Suppose we have some given search graph \(\large S\), consisting of nodes \(\large N\) connected by edges \(\large E\). We represent our search goal as a function that returns true or false for any given node: \(\large goalTest: N \rightarrow \{0, 1\}\).
\(\Leftarrow\) What is a successor function?
Finally, we define one additional helper function that, given a particular node, returns a list of all of the adjacent nodes that we can get to from there: \(\large getSuccessors: N \rightarrow N\). These “can-get-to” nodes are often called successors or children of the parent node.
TO ADD: This is a “knowledge representation.” or some other name for this? schema?
– add analogy to head massager thingy
Then, we can write a very simple search algorithm:
function SimpleSearchLoop(function goalTest, function getSuccessors,
node currentNode) -> node
if (goalTest(currentNode))
return currentNode;
list options = getSuccessors(currentNode);
if (options.isEmpty())
return null;
node nextNode = chooseOne(options);
return SimpleSearchLoop(goalTest, getSuccessors, nextNode);
end
Given any search graph, we can now run a search just by calling this function on any starting node from that graph. Let us consider some properties of this search algorithm.
First, the function chooseOne is used to select which successor to move to next. If chooseOne is set to be random, then this search algorithm is essentially a random walk over the search graph. That could be a good thing, in that our search will potentially (albeit slowly) travel around to interesting places in the graph.
Imagine you are stuck in a hedge maze, and you try to get out by rolling a dice at each intersection and choosing your next move completely at random. You are going to be stuck in there ALL day! Unless you just happen to get very lucky, that is.
On the other hand, it’s also a bit dumb, for a couple of reasons. First, because the search halts as soon as you get to a “dead-end” node, we might halt prematurely even though there are other places in the graph that we could have explored. In other words, if there is some way to keep track of our choice points, then if we do hit a dead end, we could go back and explore some different choices.
In our hedge maze, it would be nice if we had little bits of ribbon or something that we could tie off every time we are at an intersection and go down a particular direction. That way, the next time we return to that same intersection, we can see where we’ve already been, and make sure to go in a different direction.
Second, we might spend time exploring nodes that we’ve already seen before. If we could keep track of where we had previously been, then that would clearly save us a lot of wasted effort.
A bit later, we’ll look at search algorithms that include these enhancements. However, for now, we’ll stick with the simple version to illustrate one more important concept in search: namely, search trees.
5.8 Turning graphs into trees
Consider our simple search algorithm from above. An agent running this algorithm would bounce around the search graph, moving from node to node. Each time it hits a node, if that node isn’t the goal, then it looks at its options from that node, and then continues.
If you think of the graph from the perspective of this search agent, then the graph might look something like this:
<diagram of partial tree.>
Notice that, while we know there is a whole graph sitting there, and the agent is running around in it…from the perspective of the agent itself, it looks like a skinny little tree. The starting node is the root of the tree, and each time the agent calls the function getSuccessors(currentNode), it generates the set of available branches coming out from currentNode.
Now, we’ll add one more perspective-change onto this idea. The tree above depends on the agent’s choices during its search; it only shows the parts of the search space that the agent actually travels through. Imagine instead that we could see a version of the tree that encompassed ALL of the agents possible choices, and not just the ones that it ended up choosing. Then, we would have something like this:
<diagram of full tree with partial tree highlighted.>
For a given search graph, this is what we call the corresponding search tree.
\(\Leftarrow\) What is a search tree?
Definition 5.3 A search tree is ….
5.9 Search tree size: Branching factor and depth
\(\Leftarrow\) What is branching factor of a search tree?
The branching factor of a search tree refers to how many branches (on average) come out from each node. If a search graph, if every node has exactly the same number of children, then the branching factor of our tree will be a constant. If, on the other hand, different nodes have different numbers of children, then the branching factor will vary across our tree, but we can still usually compute some kind of approximate branching factor (e.g., average branching factor, or upper and lower bounds, etc.).
\(\Leftarrow\) What is depth of a search tree?
The depth of a search tree refers to how many layers deep the tree is.
<Example of finite graph, finite depth tree.>
<Example of finite graph, infinite depth tree.>
<Because the tree is from the perspective of the search agent, the branching factor and depth depend just as much on the properties of the agent as they do on the properties of the graph. E.g. visit repeated states or not.>
5.10 Example: Finding the minimum via local search vs. analytical solution
5.11 Putting it all together: Chess
5.12 To add…
Guilford, J. P., Wilson, R. C., Chrlstensen, P. R., & Lewis, D. J. (1951). A factor-analytic study of creative thinking: Part i. Hypothesis and description of tests. Psychology Laboratory Report.
More on AUT here.
Alan Newell and Herbert Simon, two pioneers of AI, …
More on search here.
reflex agents (knee jerk, and blinking? recognition is not reflex)
feed-forward agents
dimensionality - interesting, but also extremely limiting if you think of dimensions as … unidimensional! and quantitative.
Page built:
2022-12-06
using
R version 4.1.1 (2021-08-10)
Please cite as: Kunda, M. (2022). Triangle AI Book. https://www.triangleaibook.org View source Website analytics provided by Plausible.io, a deliberate choice made to preserve your privacy. (See here for more on the rationale behind this choice, and the role of AI in modern surveillance.)
This work is licensed under the Creative Commons BY-NC-ND 4.0 License. This means you are welcome to redistribute material from this book but only: (1) WITH attribution, (2) for NON-commercial purposes, and (3) WITHOUT modifications, in order to preserve the intellectual integrity of this work.
View source
This work is licensed under the Creative Commons BY-NC-ND 4.0 License. This means you are welcome to redistribute material from this book but only: (1) WITH attribution, (2) for NON-commercial purposes, and (3) WITHOUT modifications, in order to preserve the intellectual integrity of this work.