ISR-9
August, 1965

H-l
II.

A GENERAL DISCUSSION
T0 E v s l i n

1.

Introduction
The following is a general description of the logical propertiesof the SMART system,, For operating instructions and specific descriptionsof the system operation, see Sec. IV of this reports

For a. descriptionof specific subroutines and algorithms, see the sections devoted to theappropriate chain link.
SM.ART is an experimental document indexing, correlating and retrieval system.

English language documents are punched on cards andconverted by the lookup programs to an internal form, called document
vectors, which become part of the permanent document collection^

Requestvectors are formed in the same way and correlated with the documents.
Document vectors which correlate with a request above a user-specified
cutoff are taken to be answers to this request«

The flexibility and im-

portance of SMART lie in the different ways document and/or request vectors
may be mechanically specified, weighted, or changed to provide the kind of
retrieval which the user wishes to use or evaluatee

2,

The LOOKUP and Phrase Detection
Documents and requests are introduced into the system in natural

language form on punched cardso

The only special SMART conventions are11-2
those for document identification and for the simulation of punctuation notavailable on the IBM 026 keypunch.

During the lookup,, English texts become

document vectors,, The simplest form of a vector is one in which eachEnglish word is represented by a unique internal concept number.

Such asimple system uses very little of the information actually contained in adocumentQ
The first step in the sophistication of the lookup is to assign
concept numbers to word stems, rather than to whole words*

Obviously adocument containing the word "mathematics" should correlate to some degreewith a. document containing the word "mathematical"
both words is the same0

The semantic value of

Therefore^ the first step in the SMART lookup isto split words into stems and suffixes0

A list of suffixes is provided

internally and rules for handling doubled consonants and terminal y ? s havebeen included.
The word stems are looked up in a stem dictionary called the thesaurus, and the suffixes are looked up in a suffix list0

From the stem

dictionary, each word stem is replaced by one or more concept numbers
representing semantic values*

The suffix lookup produces syntactic codes

for each word0
Two types of stem dictionaries are available in the SMART system „One is handmade; the other produced mechanically0

A handmade dictionary

offers the advantage of allowing synonyms to be properly identified andassigned to the same concept number,,

It also allows the assignment ofmultiple concept numbers to word stems with several possible meanings0

II-3

However, a mechanically produced, or "null" dictionary, frees the systemfrom the need for an expert lexicographer to produce a thesaurus for eachcollection in a new field.

It permits the rapid preparation of a dictionaryof significant concepts in any discipline as soon as the documents areavailable. A significant concept, for these purposes, is one which occurs
in the collection either with a frequency above a user-specified cutoff,
or which appears in a top group of most frequent concepts whose size isalso determined by the user. Eliminated from the list of significant concepts
are those concepts which are so common that their appearance in a document
carries no semantic information,. Words like "the," "if," and "or" obviously
have no semantic value, although they are necessary for analysis„

A list ofthese "common" words is supplied with the system and may be modified by theusers.

This list is generally conceded to be standard through all disciplines

and subjects • (For a discussion of the production of hand dictionaries see
Information Storage and Retrieval, Report Noe ISR-7* Sec0 IIL)
A further sophistication of the lookup process to produce even more
complete vectors is possible.

If the co-occurrence of single words in docu-

ments is significant in the correlation process, then certainly the cooccurrence of entire phrases would be expected to be of even greater importance.
For this reason, SMART includes two methods of phrase detection. Phrases,
like single word stems, are detected in the text; and the concept number
identified with each phrase is added to the vector representing the corresponding document•
Statistical phrases are defined as the co-occurrence of concepts ina sentence regardless of relative position or other relationship between

II-U
phrase components. Therefore, the statistical phrase finder would findthat the sentences "Information retrieval is a new science" and "Information can be gained by the retrieval of the capsule" both contain thephrase "information retrieval."

Preliminary experimental evidence showsthat statistical phrase searching significantly improves the performanceof the SMART system. There is theoretical speculation that the statistical definition of a phrase may be more valuable than a syntactic definition(in which components are syntactically related) for indexing purposes,
since the co-occurrence of concepts in a sentence is likely to be significant whether or not the components are syntactically related.
Two kinds of statistical phrase dictionaries are available, which
are somewhat analagous to the hand and mechanically produced concept
dictionaries. The hand produced dictionary has the advantage that a phrase
may be assigned to the same concept number as a synonymous phrase, or wordstem.

The mechanically produced phrase dictionary, called the cluster

dictionary, has the same advantage as the null word stem thesaurus:

it canbe quickly and effortlessly produced for any collection without the needfor a human expert in the topic field, This cluster dictionary is formedby correlating each sentence in the collection with each other sentence,and forming clusters out of those concepts which co-occur with significant
frequency in the same sentence. Each cluster is then assigned an arbitrarycluster number. When a cluster, or a hand-defined phrase, is detected in adocument or request, its concept number is added to the vector being formed
for that request.

II-S
The user of the SMART system may request that syntactic phrases be
detected.

In order for a. syntactic phrase to exist, its constituent con-cepts must occur in a. defined grammatical relationship within the sentence*
For example, the sentences "Information retrieval is a new science" and"Information may be obtained by the retieval of the capsule" both containthe statistical phrase "information retrieval," but only the first sentence
contains "information retrieval" as a syntactic phrase•

The sentence "Because

the capsule contains top secret information retrieval is vital" does notcontain the phrase "information retrieval" in a syntactic sense even though
the components occur in adjacent positions.

On. the other hand, the sentence"Retrieval of information is the business of SMART" does contain the syntacticphrase,The program for detecting syntactic phrases accurately is a highly
complex algorithm and, compared to statistical phrase searching, is quite
expensive to run. Basically, it takes those sentences which the statisticalphrase finder has identified as containing all the constituents of somestatistical phrase and feeds them through the Kuno Syntactic Analyzer (seeMathematical Linguistics and Automatic Translationg NSF-9).

The syntactic

codes associated with each word and previously detected from the word suffixes (see above) are introduced to the analyzer along with the actual
sentence.

Its output is a tree of graph of the sentence. Each node contains

semantic and syntactic values; each branch a structural relationship0
match routines (described morn fully in

Sec.

The

XII of this report) search

the sentence trees for the occurrence of any one of the subtrees which areII-6
in the phrase dictionary.

If a subtree, such as the noun "retrieval"modified by the noun "information/1 is found to be wholly included in a
sentence tree, the concept number associated with the subtree is added tothe document vector.

The dictionary of subtrees, or syntactic phrases,

is prepared by hand.
The concept numbers which make up the document vectors may now
represent four different kinds of information: word stems, statisticalphrases, clusters, and syntactic phrases. Associated with each concept
number is a weight representing originally the number of times the concept
was detected in the document.

The user, however, may specify that concept

numbers from different sources be weighted differently.

For example, he

may weight statistical phrases U.7 times higher than word stems, andclusters twice as high.

He may decide that concepts which occur in a docu-

ment title should be weighted several times higher than those in the body.
One of the aims of the SMART system is to discover the effect of suchweighting on the type and quality of the retrieved documents.

In general,weighting phrases highly will result in a smaller number of retrieved
documents, and a higher percentage of relevant ones for a given request.
Weighting titles heavily tends to approximate a KWTC indexing system andretrieves a relatively higher percentage of irrelevant texts.

3.

Further Modifications to the Document Vectors
A.

Concept-concept Correlation
A human researcher who consults a library to find documents relevant

to a given request would notice correlations beyond simple identity of words

II-7
and phraseso

Given the request:"I would like information about solar

systems/' the researcher would, if he had any acquaintance with the field,
select articles not only about the solar system, but also texts using thewords "planetary" and "stellar."Concept-concept expansion is a method of

adding related, although not necessarily synonymous, concepts to a document
vector.
In order to perform concept-concept expansion, it is necessary tocorrelate each concept number against each other one and identify thosewhich are related above a user-specified cutoff.

The first step in thisprocess is to invert the document concept matrix.

In its original form

(see above) it consists of rows called document vectors*

Each vector con-sists of a list of the concept numbers associated with a given document andtheir weight in that document.

In the inverted form each row is a concept

vector containing for each concept the list of documents in which it occurs9
and its weights in each document.
The concept vectors are correlated against each other according to
one of two formulas specified by the user (see following for discussion ofcorrelation methods).

Concepts appearing in a similar set of documents withsimilar frequencies will correlate most high] .

pts which correlate

above a user-specified cutoff are assumed to be related.

It is possible toiterate the concept-concept correlation as many times as desired, a process
which, theoretically, should lead to a complete synonym list*
The user may indicate whether he wishes to have requests, texts, orboth expanded by concept-concept association.

In either case, the document

n-8
vectors to be expanded are read-in, and additions are made from the listof significantly related concepts*

For example, if the vector of a certain

text contains concept number seven, and concept seven has been found to berelated to concept twenty, concept twenty will then be added to the vector•
If concept twenty is already present in the vector, its weight will be increased.

A user of the SMART system may specify a constant to be used

multiplicatively to increase or decrease the weight assigned to concepts
which are added by concept-concept expansion (to make them more or lessimportant in determining final request-document correlation).

B.

The Hierarchy
Another way of modifying the request and/or text vectors in orderto change the nature of the answers received, is to use hierarchical expansion. A hierarchy of concept numbers is included in the SMART system.
A segment of a sample hierarchy appears below.
Fruit

f Cider

Pear/

Bartlett//

Mcintosh^ Baldwin"" —yTo modify a document containing the word "apple," the user may specify
movement in any one of four possible directions. He can expand upwards
adding the concept number for "fruit" (the parent of "apple,") to thevector.

He can expand laterally, adding "pear" and "peach," which are

I

II-9
the brothers of "apple,"

Downward expansion to sons adds "Baldwin" and"Mcintosh." "Cider" i s a cross-reference to "apple," a r e l a t e d concept whoser e l a t i o n s h i p does not lend i t s e l f to h i e r a r c h i c a l expression.

Any combi-

nation of the four d i r e c t i o n s : up, down, sideways, and across^ i s available*
The concept numbers added through these methods may be weighted as the user
desires.

The user may also choose to have the concepts determined by h i e r -archical expansion, replace the o r i g i n a l vector instead of being appended
to i t .

h*Correlation
After documents and requests have been looked up in the thesaurus,

and have been found, and. after the vectors have been expanded and weighted
according to the u s e r ' s object-time s p e c i f i c a t i o n s , the vectors must be
c o r r e l a t e d , and documents which are s i g n i f i c a n t l y related to the requests
must be i d e n t i f i e d .

The word " s i g n i f i c a n t , " here as elsewhere in t h i s t e x t ,means with a correlation higher than a user-specified

cutoff«Each vector can be thought of as a set of ordered numbers, defining
a point on the surface of an N-dimensional sphere, where N i s the number ofconcepts included in the thesaurus.

Correlation between two vectors i s thena measure of the arc on the surface of the N-sphere which separates them.
Two algorithms are available to the user for measuring t h i s a r c !
overlap:cosine and11-10
N

Ya.b.
i=l
N

COSINE .
ab

i-1

i-1

^Min(a i ,b i )OVERLAPab.
Mn£v Ibi

Consider for example the two vectors
a - 6,0,5,0,0,1.2,
andb - 2,1,0,2,0,1,1,1*.
This representation of the vectors implies that for document a, concept
number one has a weight of six, two does not appear, three has a weightof five, and so on. Similarly for document b, where concept one has aweight of two, concept two a weight of one, and three does not appear.
Their correlations by the two given methods are completed as follows:rn^TMTT - (6-2+Q-l+5-Q+Q-2+Q-Q±l-l+Q-l+2-li)
C0SINE ab " j( 3 6 + 0 + 2^+0+0+1+O+U)(li+l+O+U+0+1+1+16)

OVERLAPab. -Min(ll,ll|)l:°T,°T^2=m n 5<n- 0.16.

These correlation methods have the advantage that all correlation values
fall between one and zero. This restricted range is helpful to the user°' °>

11-11"who must pick a cutoff above which all correlations will be declared relevant.
The same two equations used for request-document correlation are available for the other two correlations performed by SMART:

concept-concept

correlation (see above) and document-document correlation (see below),
At this point a list of requests is available, and correlations ofeach document in the collection with each of these requests has been produced*
These lists may now be thought of as a matrix, where each row is a request
and each column is a document. At the intersection of each row and column
is the correlation of a given document with a priven request. The user may
now -print out the documents whose correlation with each request lies above
the specific cutoff, or he may perform further operations on the requestdocument matrix.

$•

Document-Document Correlation to Expand the Answer List

If a research, worker were performing a. document search, he mightsearch his library card catalogue for all the sources listed under his
primary topic.

He might then go a. step further, and search under topics

suggested by his primary reading, or listed in the bibliographies of his
original sources.

Using SMART it is possible first to find a list of docu-

ments significantly related to a given request, then to go further and add
to this list documents related to the original documents. This process iscalled document-document correlation.
document correlation.

It takes place following request-

11-12Each document in the collection i s correlated with each other document according to the algorithms explained above,A l i s t of documents whosec o r r e l a t i o n i s larger than a user-specified cutoff with each other documenti s then prepared.

Using t h i s l i s t , a document i s added to the answer vector

for a given request, if i t i s s i g n i f i c a n t l y r e l a t e d to some other document
which i s already an answer to that r e q u e s t .
6.

Evaluation
Since SMART i s an experimental information r e t r i e v a l system, i tlends i t s e l f to an evaluation procedure which t e s t s the completeness andrelevance of the answers produced by each of the analysis procedures•In

order to do t h i s i t i s necessary to compare the l i s t of request-documentc o r r e l a t i o n received as answers to a search request with a l i s t of a n t i c i pated document ranks prepared by hand.

Several algorithms are available

and a user can e a s i l y add his own.
The two basic evaluation measures for an information r e t r i e v a lsystem are "precision" and "recall 1 1 r e s p e c t i v e l y .

Recall i s defined as

the number of relevant documents r e t r i e v e d over the t o t a l number of r e l e vant documents in the c o l l e c t i o n .

Precision i s defined as the number of

relevant documents retrieved over the t o t a l number of documents r e t r i e v e d .
These two measures tend t o vary inversely for a given information r e t r i e v a lmethod.

For example, if the request-document cutoff i s lowered, r e c a l l w i l ld e t e r i o r a t e as more i r r e l e v a n t documents are returned.

Basically, a com-bined r e c a l l and precision measure must be used to evaluate the r e l a t i v eeffectiveness of different methods of information r e t r i e v a l .

The evaluation

11-13system i s described fully in Sec* XVII of t h i s r e p o r t .

7.

Graphical System Summary
The flowchart which follows i s in no sense a system flowchart*.

It

does, however, explain the basic l o g i c , as well as some of the l o g i c a l l yimportant input and output process*A formal flowchart appears in the nextpart.
action always performed by system

Legend:I]

optional function of systemcard input via. magnetic tape at object^

time, or card output

preprocess function

prepared by handI

prepared by machinetape input at object

printed output

n-iU
START

English t e x t

User-specified option

Set up parameters
for this run>

English text

i Lookup new |The sauna s• Print words not!
ifound in lookup|

English text

orm cluster
ictionarv.

Detect statistical phraseS|
and add to vectors
^r
^J

r

&
Statistical phrase
dictionary^—4

Detect clusters and ,add to vectors|

cluster dictionary&
Detect syntactic phrases \^and add to dictionary _j
Syntactic phrase
dictionaryi
Smart Logical Functions
Flowchart 1

n-15
A

v.
previously looked- T " nConceptconceptr
up t e x t s.
',^' e x p r e s s i o n performed[ r e s u l t s added t o v e c t o r s

r e v i o u s l y look ed-up
texts

I

I Hierarchy performed and! r e s u l t s added t o v e c t o r sJ&..

Vectors merged andweighted ass p e c i f i e d by u s e r~\ looked-up t e x t snmerged v e c t o r s
V\/V

jv_

Requests c o r r e l a t e d w i t hdocuments and l i s t ofanswers prepared f o r each reOURsi

Document-document expansion
performed and r e s u l t s used t o 'I ^expand t^he^ a n s w e r ^ l i s t s\kl
pin swer p r i n t e d for"1I
each r e q u e s t

i / W

r

answers|evaluation performed—?

pre d i e t e d an swers/
R( su] ts o f run
Future evaluation
flowchart 1 (continued)

for