Posts Tagged ‘Information Retrieval’

My Labors Are Not Ended

Wednesday, June 26th, 2013

lenora at rest in the library

But I am going to take a rest for a bit.

Above you see a shot of my cat Lenora resting in front of the “To Read Science Fiction” section of my Library, the enormous book collection I’ve been accumulating over the last quarter century. I have books older than that, of course, but they’re stored in my mother’s house in my hometown. It’s only over the last 25 years or so have I been accumulating my own personal library.

But why am I, if not resting, at least thinking about it? I finished organizing the books in my Library.

lenora at rest in the library 2

I have an enormous amount of papers, bills, bric a brac and other memorabilia still to organize, file, trash or donate, but the Library itself is organized, at last. It’s even possible to use it.

How organized? Well…

Religion, politics, economics, the environment, women’s studies, Ayn Rand, read books, Lovecraft, centaur books, read urban fantasy, read science fiction, Atlanta, read comics, to-read comics, to-read science fiction magazines, comic reference books, drawing reference books, steampunk, urban fantasy, miscellaneous writing projects, Dakota Frost, books to donate, science fiction to-reads: Asimov, Clarke, Banks, Cherryh, miscellaneous, other fiction to-reads, non-fiction to-reads, general art books, genre art books, BDSM and fetish magazines and art books, fetish and sexuality theory and culture, military, war, law, space travel, astronomy, popular science, physics of time travel, Einstein, quantum mechanics, Feynman, more physics, mathematics, philosophy, martial arts, health, nutrition, home care, ancient computer manuals, more recent computer manuals, popular computer books, the practice of computer programming, programming language theory, ancient computer languages, Web languages, Perl, Java, C and C++, Lisp, APL, the Art of Computer Programming, popular cognitive science, Schankian cognitive science, animal cognition, animal biology, consciousness, dreaming, sleep, emotion, personality, cognitive science theory, brain theory, brain philosophy, evolution, human evolution, cognitive evolution, brain cognition, memory, “Readings in …” various AI and cogsci disciplines, oversized AI and science books, conference proceedings, technical reports, game AI, game development, robotics, imagery, vision, information retrieval, natural language processing, linguistics, popular AI, theory of AI, programming AI, AI textbooks, AI notes from recent projects, notes from college from undergraduate through my thesis, more Dakota Frost, GURPS, other roleplaying games, Magic the Gathering, Dungeons and Dragons, more Dakota Frost, recent projects, literary theory of Asimov and Clarke, literary theory of science fiction, science fiction shows and TV, writing science fiction, mythology, travel, writing science, writing reference, writers on writing, writing markets, poetry, improv, voice acting, film, writing film, history of literature, representative examples, oversized reference, history, anthropology, dictionaries, thesauri, topical dictionaries, language dictionaries, language learning, Japanese, culture of Japan, recent project papers, comic archives, older project papers, tubs containing things to file … and the single volume version of the Oxford English Dictionary, complete with magnifying glass.

lenora at rest in the library 2

I deliberately left out the details of many categories and outright omitted a few others not stored in the library proper, like my cookbooks, my display shelves of Arkham House editions, Harry Potter and other hardbacks, my “favorite” nonfiction books, some spot reading materials, a stash of transhumanist science fiction, all the technical books I keep in the shelf next to me at work … and, of course, my wife and I’s enormous collection of audiobooks.

What’s really interesting about all that to me is there are far more categories out there in the world not in my Library than there are in my Library. Try it sometime – go into a bookstore or library, or peruse the list of categories in the Library of Congress or Dewey Decimal System Classifications. There’s far more things to think about than even I, a borderline hoarder with a generous income and enormous knowledge of bookstores, have been able to accumulate in a quarter century.

Makes you think, doesn’t it?

-the Centaur

Context-Directed Spreading Activation

Monday, March 18th, 2013


Let me completely up front about my motivation for writing this post: recently, I came across a paper which was similar to the work in my PhD thesis, but applied to a different area. The paper didn’t cite my work – in fact, its survey of related work in the area seemed to indicate that no prior work along the lines of mine existed – and when I alerted the authors to the omission, they informed me they’d cited all relevant work, and claimed “my obscure dissertation probably wasn’t relevant.” Clearly, I haven’t done a good enough job articulating or promoting my work, so I thought I should take a moment to explain what I did for my doctoral dissertation.

My research improved computer memory by modeling it after human memory. People remember different things in different contexts based on how different pieces of information are connected to one another. Even a word as simple as ‘ford’ can call different things to mind depending on whether you’ve bought a popular brand of car, watched the credits of an Indiana Jones movie, or tried to cross the shallow part of a river. Based on that human phenomenon, I built a memory retrieval engine that used context to remember relevant things more quickly.

My approach was based on a technique I called context directed spreading activation, which I argued was an advance over so-called “traditional” spreading activation. Spreading activation is a technique for finding information in a kind of computer memory called semantic networks, which model relationships in the human mind. A semantic network represents knowledge as a graph, with concepts as nodes and relationships between concepts as links, and traditional spreading activation finds information in that network by starting with a set of “query” nodes and propagating “activation” out on the links, like current in an electric circuit. The current that hits each node in the network determines how highly ranked the node is for a query. (If you understand circuits and spreading activation, and this description caused you to catch on fire, my apologies. I’ll be more precise in future blogposts. Roll with it).

The problem is, as semantic networks grow large, there’s a heck of a lot of activation to propagate. My approach, context directed spreading activation (CDSA), cuts this cost dramatically by making activation propagate over fewer types of links. In CDSA, each link has a type, each type has a node, and activation propagates only over links whose nodes are active (to a very rough first approximation, although in my evaluations I tested about every variant of this under the sun). Propagating over active links isn’t just cheaper than spreading activation over every link; it’s smarter: the same “query” nodes can activate different parts of the network, depending on which “context” nodes are active. So, if you design your network right, Harrison Ford is never going to occur to you if you’ve been thinking about cars.

I was a typical graduate student, and I thought my approach was so good, it was good for everything—so I built an entire cognitive architecture around the idea. (Cognitive architectures are general reasoning systems, normally built by teams of researchers, and building even a small one is part of the reason my PhD thesis took ten years, but I digress.) My cognitive architecture was called context sensitive asynchronous memory (CSAM), and it automatically collected context while the system was thinking, fed it into the context-directed spreading activation system, and incorporated dynamically remembered information into its ongoing thought processes using patch programs called integration mechanisms.

CSAM wasn’t just an idea: I built it out into a computer program called Nicole, and even published a workshop paper on it in 1997 called “Can Your Architecture Do This? A Proposal for Impasse-Driven Asynchronous Memory Retrieval and Integration.” But to get a PhD in artificial intelligence, you need more than a clever idea you’ve written up in a paper or implemented in a computer program. You need to use the program you’ve written to answer a scientific question. You need to show that your system works in the domains you claim it works in, that it can solve the problems that you claim it can solve, and that it’s better than other approaches, if other approaches exist.

So I tested Nicole on computer planning systems and showed that integration mechanisms worked. Then I and a colleague tested Nicole on a natural language understanding program and showed that memory retrieval worked. But the most important part was showing that CDSA, the heart of the theory, didn’t just work, but was better than the alternatives. I did a detailed analysis of the theory of CDSA and showed it was better than traditional spreading activation in several ways—but that rightly wasn’t enough for my committee. They wanted an example. There were alternatives to my approach, and they wanted to see that my approach was better than the alternatives for real problems.

So I turned Nicole into an information retrieval system called IRIA—the Information Retrieval Intelligent Assistant. By this time, the dot-com boom was in full swing, and my thesis advisor invited me and another graduate student to join him starting a company called Enkia. We tried many different concepts to start with, but the further we went, the more IRIA seemed to have legs. We showed she could recommend useful information to people while browsing the Internet. We showed several people could use her at the same time and get useful feedback. And critically, we showed that by using context-directed spreading activation, IRIA could retrieve better information faster than traditional spreading activation approaches.

The first publication on IRIA came out in 2000, shortly before I got my PhD thesis, and at the company things were going gangbusters. We found customers for the idea, my more experienced colleagues and I turned the IRIA program from a typical graduate student mess into a more disciplined and efficient system called the Enkion, a process we documented in a paper in early 2001. We even launched a search site called Search Orbit—and then the whole dot-com disaster happened, and the company essentially imploded. Actually, that’s not fair: the company continued for many years after I left—but I essentially imploded, and if you want to know more about that, read “Approaching 33, as Seen from 44.”

Regardless, the upshot is that I didn’t follow up on my thesis work after I finished my PhD. That happens to a lot of PhD students, but for me in particular I felt that it would have been betraying the trust of my colleagues to go publish a sequence of papers on the innards of a program they were trying to use to run their business. Eventually, they moved on to new software, but by that time, so had I.

Fast forward to 2012, and while researching an unrelated problem for The Search Engine That Starts With A G, I came across the 2006 paper “Recommending in context: A spreading activation model that is independent of the type of recommender system and its contents” by Alexander Kovács and Haruki Ueno. At Enkia, we’d thought of doing recommender systems on top of the Enkion, and had even started to build a prototype for Emory University, but the idea never took off and we never generated any publications, so at first, I was pleased to see someone doing spreading activation work in recommender systems.

Then I was unnerved to see that this approach also involved spreading activation, over a typed network, with nodes representing the types of links, and activation in the type nodes changing the way activation propagated over the links. Then I was unsettled to see that my work, which is based on a similar idea and predates their publication by almost a decade, was not cited in the paper. Then I was actually disturbed when I read: “The details of spreading activation networks in the literature differ considerably. However, they’re all equal with respect to how they handle context … context nodes do not modulate links at all…” If you were to take that at face value, the work that I did over ten years of my life—work which produced four papers, a PhD thesis, and at one point helped employ thirty people—did not exist.

Now, I was also surprised by some spooky similarities between their systems and mine—their system is built on a context-directed spreading activation model, mine is a context-directed spreading activation model, theirs is called CASAN, mine is embedded in a system called CSAM—but as far as I can see there’s NO evidence that their work was derivative of mine. As Chris Atkinson said to a friend of mine (paraphrased): “The great beam of intelligence is more like a shotgun: good ideas land on lots of people all over the world—not just on you.”

In fact, I’d argue that their work is a real advance to the field. Their model is similar, not identical, and their mathematical formalism uses more contemporary matrix algebra, making the relationship to related approaches like Page Rank more clear (see Google Page Rank and Beyond). Plus, they apparently got their approach to work on recommender systems, which we did not; IRIA did more straight up recommendation of information in traditional information retrieval, which is a similar but not identical problem.

So Kovács and Ueno’s “Recommending in Context” paper is a great paper and you should read it if you’re into this kind of stuff. But, to set the record straight, and maybe to be a little bit petty, there are a number of spreading activation systems that do use context to modulate links in the network … most notably mine.

-the Centaur

Pictured: a tiny chunk of the WordNet online dictionary, which I’m using as a proxy of a semantic network. Data processing by me in Python, graph representation by the GraphViz suite’s dot program, and postprocessing by me in Adobe Photoshop.

Conventions … not the fan kind

Saturday, July 24th, 2010

I’ve picked up a fair number of conventions over the years … notations, ways of writing things to make the type of thing that I’m writing clear. Most of these I’ve picked up from others, some are my own. Here are a few of them:

  • Novel titles are written in ALL CAPS
    You write novels this way to make it clear that it’s a BOOK you’re talking about, dag nab it. Examples: FROST MOON, ATLAS SHRUGGED, ULYSSES. I picked up this convention from my publisher, Bell Bridge Books.
  • Search queries are written in [square brackets]
    You write search queries this way, rather than with quotes, because quotes can appear in search queries. Examples: [frost moon], ["frost moon"] – note the results are not the same. I picked up this convention from The Search Engine That Starts With a G.
  • Command line text is indented in a special format where the prompt is bold, the command is bold italic, and the command response is plain text.

This last one takes more explanation (and breaking out of the unordered list to overcome WordPress CSS theme issues). When including command line responses in email, you indent the entire excerpt to set it apart from your message, then put the command prompt in bold, the command in bold italic, and its response in plain text, like so:

centaur@mobile (Sat Jul 24, 00:44:54) [501] ~:
$ imagelink comicon-2010-01.jpg san diego comicon 2010

<a href=”” alt=”san diego comicon 2010″><img src=”” alt=”san diego comicon 2010″ border=”0″ width=”600″ /></a>

Some WordPress or theme weirdness is making this formatting a little harder than it is in Gmail. I think this is fixed to the point that you should be able to see that the “informational” part of the prompt (when the command was executed) appears on its own line, with a colon and line break to separate it from the command proper. The command proper is prefixed by a dollar sign, a UNIX standard that distinguishes it from the response text that follows. This communicates and distinguishes when you did it, what you did, and what you got.

This one is mine. I’ve been developing this convention over the years as a way of communicating results from the command line in email. I have to admit, this is driven in part by a bit of egoism: I want people to know that the results I’m sending them can be done in one line of Bash, Sed and (g)AWK. And the remaining part is, I want people to learn that yes, they too can in a minute do immense amounts of computation with Bash, Sed and AWK.

That’s all for now. Next time: why the Einstein summation notation is cool.
-the Centaur