Associative Search and the Semantic Web: The Next Step Beyond Natural Language Search
May 13th, 2008Our present day search engines are a poor match for the way that our brains actually think and search for answers. Our brains search associatively along networks of relationships. We search for things that are related to things we know, and things that are related to those things. Our brains not only search along these networks, they sense when networks intersect, and that is how we find things. I call this associative search, because we search along networks of associations between things.
Human memory — in other words, human search — is associative. It works by “homing in” on what we are looking for, rather than finding exact matches. Compare this to the the keyword search that is so popular on the Web today and there are obvious differences. Keyword searching provides a very weak form of “homing in” — by choosing our keywords carefully we can limit the set of things which match. But the problem is we can only find things which contain those literal keywords.
There is no actual use of associations in keyword search, it is just literal matching to keywords. Our brains on the other hand use a much more sophisticated form of “homing in” on answers. Instead of literal matches, our brains look for things things which are associatively connected to things we remember, in order to find what we are ultimately looking for.
For example, consider the case where you cannot remember someone’s name. How do you remember it? Usually we start by trying to remember various facts about that person. By doing this our brains then start networking from those facts to other facts and finally to other memories that they intersect. Ultimately through this process of “free association” or “associative memory” we home in on things which eventually trigger a memory of the person’s name.
Both forms of search make use of the intersections of sets, but the associative search model is exponentially more powerful because for every additional search term in your query, an entire network of concepts, and relationships between them, is implied. One additional term can result in an entire network of related queries, and when you begin to intersect the different networks that result from multiple
terms in the query, you quickly home in on only those results that make sense. In keyword search on the other hand, each additional search term only provides a linear benefit — there is no exponential amplification using networks.
Keyword search is a very weak approximation of associative search because there really is no concept of a relationship at all. By entering keywords into a search engine like Google we are simulating an associative search, but without the real power of actual relationships between things to help us. Google does not know how various concepts are related and it doesn’t take that into account when helping us find things. Instead, Google just looks for documents that contain exact matches to the terms we are looking for and weights them statistically. It makes some use of relationships between Web pages to rank the results, but it does not actually search along relationships to find new results.
Basically the problem today is that Google does not work the way our brains think. This difference creates an inefficiency for searchers: We have to do the work of translating our associative way of thinking into “keywordese” that is likely to return results we want. Often this requires a bit of trial and error and reiteration of our searches before we get result sets that match our needs.
A recently proposed solution to the problem of “keywordese” is natural language search (or NLP search), such as what is being proposed by companies like Powerset and Hakia. Natural language search engines are slightly closer to the way we actually think because they at least attempt to understand ordinary language instead of requiring keywords. You can ask a question and get answers to that question that make sense.
Natural language search engines are able to understand the language of a query and the language in the result documents in order to make a better match between the question and potential answers. But this is still not true associative search. Although these systems bear a closer resemblance to the way we think, they still do not actually leverage the power of networks — they are still not as powerful as associative search.
A natural language search can understand the meaning of a query like “books about Harry Potter” and it knows this is not the same as “Books by Harry Potter.” But ultimately what is happening is that a linguistic expression is being converted into a more sophisticated keyword search. The language in the query is being mapped to documents that contain text that answers a question, or to data objects that match the thing being asked for. This is certainly better than keyword search but it is still ultimately just a smarter form of literal matching. It is not really making use of associative search along networks of semantic relationships in the data (other than linguistic relationships between words in the query) or any sort of sophisticated reasoning.
By comparison, associative search doesn’t merely understand the meaning of the query, it understands and can reason about relationships in the data. This is an important distinction.
An associative search returns documents that represent things that are related, via various forms of associations (semantic links), to the things in the query. An associative search looks through a network of associations for the things that are most connected to the items in the query. By specifying more specific starting points, the set of things which are connected to all those starting points is narrowed. Thus an associative search is an intersection of multiple networks. The items that are most strongly intersected are the results that are most likely
to matter.
Associative search is a very different approach to search from keyword search (which merely looks for things with the keywords in them) and natural language search (which merely looks for things that contain content that matches the meaning of the question). It also happens to be more similar to how our brains actually think.
On its own, associative search represents an important advance in the way we search. But by adding some simple reasoning to an associative search it becomes even more powerful. Reasoning adds the ability to generalize or get more specific, and to weight various paths through the network of relationships in more sophisticated ways, such as based on logical relationships or inferences through the network.
A simple example of reasoning is transitivity — for example, if A is a part of B and B is a part of C, then A is a part of C. If we know that the “part of” relationship is transitive, then whenever we see chains of “part of” links between things we can make transitive inferences. In an associative search these inferences are quite useful. For example, we can search for all the parts of a 747 jet. Using transitive reasoning along networks of relationships we can find all the parts, even those things that are “parts of parts.” Similarly we could find “all products of Sony” including products of subsidiaries and business units of Sony. Transitive inferences across transitive links is just one type of reasoning; there are many other variations
that are possible, which when combined together become even more useful.
Our current search tools — whether they are keyword based or natural language based do not support true associative search, let alone reasoning. But we do see associative search starting to appear in a very different breed of application: social networks. A search in LinkedIn for example, is an associative search. Will social networks do an end-run around traditional search engines to provide the next-generation of search? It’s quite possible. Facebook and LinkedIn are far better positioned than Google today for associative search. In fact, I would venture that this is how Facebook could give Google some serious competition. But they have to hurry if they are going to do this — Google has clearly realized the power of “social search” and is rapidly moving to leverage it in their own search results.
Ultimately associative search is more than just social search however. To be really effective, associative search engines need to understand and leverage the full spectrum of relationships between things, not just social relationships. They need to see and understand more types of relationships between more types of things. In order to accomplish this, associative search engines need the Semantic Web.
The Semantic Web provides exactly what is needed to enableassociative search, with reasoning, on the Web-at-large. Using RDF and OWL, content can be marked up with metadata that specifies not only its intended meaning and structure, but also the various kinds of semantic relationships it has to other content and to other concepts. In other words, these standards provide a way to add a new network of
semantically defined associations to the data on the Web. For example a document about Microsoft can be linked to the concepts “Software Company,” “Software Manufacturer,” and “Redmond.” It can also be linked to a data record that represents “Microsoft” and the properties that define it as a company. The “Microsoft” object can then link to companies that are “suppliers” and “customers” and “competitors” as well as to things which are connected as “products” or “services.”
This rich network of relationships between things goes far beyond documents. It contains relationships to people, places, other organizations, products, events, services, etc. It’s similar to a social network, but instead of just containing people and social relationships, it contains more types of things and relationships between them. This is really what the Semantic Web enables. One can imagine that as this new semantic data becomes visible on the Web (which is rapidly happening in fact), the power of search will be dramatically improved. Associative search is coming soon to a Web near you!
With that in mind, here is an example of how Semantic Web enabled associative search will work in the future.
PROBLEM: I am trying to remember name of the organizer of a conference I once attended.
WHAT I ALREADY KNOW:
- I know this person and have corresponded with them in the past.
- The conference was related to government and the Internet.
- It took place in a town near Big Sur, but I can’t remember the name of the town.
- The organizer of the conference once introduced me to a male celebrity, but I can’t remember the celebrity’s name.
- I gave a talk at the Conference about Web 3.0.
- My friend, Sue Smith, also spoke at the conference.
- The conference I attended took place in the Spring, but I am not sure if it was last year or two years ago.
In the above example, I cannot remember the specific keywords that will help me generate a query to find the answer. Instead, I remember a number of relationships and generalizations about the answer. Present day search engines cannot see these relationships, and they have no ability to understand a generalization and look at things it contains.
The ability to intersect the sets formed by relationships and generalizations is a fundamental feature of human memory and search. But our present day tools don’t have these capabilities. Thus we have to spend time translating our questions into keywordese, rather than just asking our questions in the actual language of human thought.
There are two ways to approach solving this.
- The first way is to create artificial intelligence which, given a question in natural language English, can understand it and reason about the question as well as understand and reason about the information in the set of documents being searched, in order to intelligently arrive at candidate answers. This is computationally intensive, and very hard to program. This is why AI hasn’t quite happened yet on this scale.
- A perhaps easier approach is to use the Semantic Web. In the Semantic Web approach, metadata is embedded into content that describes the meaning of the content, it’s various important properties, and its relationships to other concepts. On the basis of this metadata, the problem becomes much simpler to solve. Instead of doing high-level AI it becomes essentially a statistical search.
Now let’s look at how using the Semantic Web could help us solve the above problem via an associative search:
Items are connected to more general or specific concepts by virtue of semantic linkages between concepts. For example, the conference I am looking for is related to the concepts “Government” and “Technology.” If I can at least remember that then I can find conferences related to government and technology. Furthermore, since the concept “Policy” is a subset of government it may be related to that topic
as well.
Likewise, things are connected to things that are “near” them via geographic links. Because the conference was near Big Sur it is in Northern California, along the coast. It is probably in a town that is geographically close, ror example Carmel-by-the-Sea is a town that is near the Big Sur area.
The organizer of the conference introduced me to a male celebrity. There are several celebrities in my social network. If the fact that I met certain people via introductions from other people was stored using semantic links, then this too would be searchable. For example, “find all celebrities I was introduced to by my connections” would be a solvable query. Similarly, “find people who introduced me to celebrities” would also be solvable.
The fact that I gave a talk at the conference could also be semantically represented on a data record describing the conference, as well as on my own profile. Thus there could exist a link such as “speaker at” which links me to various conferences I have spoken at. I could then get a list of all the conference I have spoken at. I could also look for all the conferences where both myself and Sue Smith were speakers.
Or, better yet, there could be a link called “Gave talk about” which links me to an instance describing each talk I have given. From such an instance there could then be “Gave talk at” links to all the events where I have given that talk. So I could look up my “Web 3.0″ talk and then see all the conferences where I gave that talk.
Temporal relations can also be generalized and semantically represented. For example, the conference I am looking for took place in the spring. Therefore only look for conferences that took place in or near months that are considered to be in the spring season.
By intersecting the results of the above searches we narrow down very precisely to a set of people I might be looking for, or just to a single qualifying person.
For example the answer I was seeking for was that the organizer was named Robert Jones, and the conference was about Government and Technology Policy in Carmel-by-the-Sea last spring. This result should be easily findable via associative search starting from the above set of things I remember.
But if for some reason the answer is still not there, there is another capability which the brain uses that we need to add to our search engines: Perturbation, or what could be called “prospecting.”
The query I entered is comprised of a question and a set of facts related to the answer I am seeking. But there is a possibility that I asked the question incorrectly, or some of the facts I added were incorrect, or insufficient. Perturbation can correct for this by introducing variations into the question and the facts in order to explore the space of answers that are “near” them as well.
There are many ways to go about adding perturbation to the system — for example, we can search more than one hop out from every link, or we can search for other types of relationships that are highly correlated with relationships we are asking for
explicitly, or we can include results for things which are strongly connected to things that are found.
From a user-interface standpoint perturbation can be controlled with a simple “sliding lever” in the user interface for “Precision.” If the user sets very high Precision as a requirement then there is no perturbation — the results are exact matches to the query and facts. If there is low Precision as a requirement then there can be more perturbation, thus the results are fuzzy and may include things that are near what I asked for but not exactly what I specified, enabling me to discover
things via relevant relationships that I could not even remember to mention as facts.
Finally, using a reasoner, the results found by the above search can be analyzed such that those results which are most likely to be what I am looking for, given the facts I have included as constraints, are presented first. Reasoning becomes the ranking algorithm in the system, rather than something like Pagerank. The answers that actually make the most sense in the context of my question are delivered first.
The above illustration describes how searches that are powered by the Semantic Web will work, once this technology is widely adopted. This is how the brain works, and how our search engines should work as well.
This is not a pipedream — in fact it is already happening in research settings and in the government. Within 15 years, if not a lot sooner, we will see these capabilities emerge in consumer-grade search interfaces.