V-l

V.

Syntax in Text Analysis
S. F. Weiss

Abstract
This paper discusses various methods for the determination ofphrases from text and for their use in information retrieval.

The resultsof a set of experiments using these methods are presented and analyzed.
Future work in this area is also covered.

1.

Introduction
The purpose of this project is to investigate the use of syntax inin text analysis and information retrieval and specifically, to determine
the usefulness of phrases in the retrieval process. In its present state
the SMART system assigns concept vectors to documents partly on the basisof the words in the document.

Two similar yet nonidentical documents canthus be assigned identical vectors, as in the case of the two sentences:the programming of numerical analysis systems;
numerical analysis in programming systems.

If it is desired to differentiate between these two sentences, the obvious
solution is to use syntax.
be accomplished.

What is not obvious is how this process is to

Various possibilities exist; experiments with some ofthese methods are discussed in the following sections.

The experiments

are performed using the ADI collection of 82 documents.

A set of ten

queries, five general and five specific, is chosen as representative of
the various forms and constructions of queries.

A normal SMART run isV-2

performed using the cosine coefficient.

For each of the ten test queries,

the ten most highly correlated documents are identified.

These documents,

along with any others, relevant to the test queries but not in the top ten,are collected to form the test document set.

The total set contains 56 of

the 82 AD1 documents.

In all the experiments, phrases are determined forthis test set only.

It is felt that the results achieved with the limited

set will differ little from those of the full set.

Also because, of thegreat quantity of hand work required, the restricted document set is necessary.

The results of the normal cosine retrieval process are shown in Fig.

1 in the form of the average precision-recall curve for the ten test queries.

2.

Statistical Phrases
The statistical phrase process uses a predetermined list ofphrases.

The cooccurrence of the phrase elements in a document is consideredan occurrence of that phrase regardless of the syntactic relation of thephrase components.

A concept number is associated with each phrase andthe appropriate concepts appended to the document or query vectors.

Thismethod is clearly the simplest way to determine phrases since it requires
no syntactic analysis of the text.
backs.

It however has some rather serious draw-

Most obvious is the fact that it may recognize false phrases; thatis occurrences of the desired phrase elements but not in the proper syntactic relation.

This problem can be minimized in small collections dealing

with a narrow subject area by judicious selection of the statistical phrase
list.

In a corpus dealing with computer systems, for example, the occurrenceof the words "real" and "time" can be viewed with relative certainty to bean occurrence of the phrase "real time".

However as the collection grows

1.0

en

•.

'*.

Precision

.8

CM

^
...,-.V

1

1

1

.4

.6

_ l

.8

L
1.0

RecoilAverage Precision-Recall Curve for Experiment 1
Cno phrases)
Fig. 1

I.Oh

8h

Statistical Phrases(no cooccurrence)
Standard Run(no phrases)

o-6
o

.2
_L

J_

.4

.6

.8

1.0

RecallPrecision-Recall Curve for Experiment 2
Fig. 2

V-4

and the subject area broadens, these decisions become less certain.

Also

the difficulty in creating the phrase list is increased as the corpus isenlarged.

The phrase list can be determined by statistical means, however

weaknesses in this method can further compound the problem•

In the ADI

collection for example, of the 409 statistical phrases in the test documentset, only 153, roughly 37%, are syntactically correct.
A second difficulty in using statistical phrases involves unmatched
concept numbers.

In many cases, especially when the document is long andthe query is short, the document contains many more phrases than the query.
Consequently many of the phrase concepts in the document are not matchedwith query concepts.

These unmatched concepts clearly lower the correla-tion and partially if not completely, offset any gain achieved by thematched phrase concepts.

Thus the inclusion of too many phrases dilutes

the original vector with unusable information and inferior retrieval results are produced.
Fig. 2 shows a comparison of the average precison-recall values for
retrieval with statistical phrases with those made with no phrases.

Thephrases are determined by hand searching the set of test documents andqueries using the SMART list of statistical phrases.

The weight assigned

to a phrase concept is the minimum weight of its component concepts.

3.

Syntactic Phrases
The text of the test documents and queries is searched again andthose statistical phrases which are not syntactically correct are removed.
This leaves 153 of the original 409 document phrases and 6 of the 12 queryphrases.

Results of retrieval using syntactic phrases are shown in Fig,, 3

V-5along with the results of the normal run.

While the elimination of all syn-tactically false phrases solves one problem, another problem, the adverse
effect of an overabundance of unmatched concepts, still remains.

The fol-

lowing section presents a method for solution of this problem.

4.

Cooccurrence
The methods described in sections 2 and 3 have a number of common

problems.

One is the dilution effect causes by unmatched concepts.

Asecond difficulty deals with the value of a phrase as a nonrelevancy indicator.

Individual concepts are about equally good as relevancy and nonrele-

vancy indicators.

That is the cooccurrence of concept A in document D andquery Q is as good a measure of D's relevance to Q as the lack of this cooccurrence is a measure of DVs nonrelevance.

As more and more structure is

imposed on the comparison of documents and queries, high correlations growmore significant but less frequent while low correlations grow more frequent but less significant.

For example if documents are retrieved only

if they match, word for word, the complete query, few if any documents would
ever be retrieved.

However any document retrieved by this scheme would al-most certainly be relevant.

Thus the added structure makes the retrieved

documents more likely to be relevant.

On the other hand, the fact thatsome documents do not match the complete query is not a good indicator of
their nonrelevancy.

The situation is similar for phrases.

The cooccurrenceof a phrase in a document and query is a better indicator of the documentTs
relevance to a query than two other cooccurring concepts that do not form aphrase.

Furthermore an unmatched phrase concept is not as good a nonrele-

vancy measure as is an unmatched word concept.

It is therefore necessary

V-6

I.Oh
Syntactic Phrases(no cooccurrence)

8h

IStandard Run(no phrases)

6

o

H.

0)

*

.4h

-

\

2h

.2

±

I

.4

.6

.8

1.0

RecallAverage Precision-Recall Curve for Experiment 3
Fig. 3

1.0
Statistical Phrases(with cooccurrence)

8

Standard Run(no phrases)
o »6

±

A

.6

.8

l.O

RecallAverage Precision-Recall Curve for Experiment 4
Fig. 4

Y--7

to treat phrase concepts and word concepts differently.
The method proposed to solve these difficulties is to consider
phrases only when they cooccur in both the document and query.
accomplished by the following procedure.

This isLet D and Q be the word concept

vectors for a given document and query, and PD and PQ, their associatedphrase concept vectors.

In the previous experiments the correlation is cal-culated between D + PD and Q + PQ.

For the proposed process, the cooccur-

rence procedure first determines the set C = PDflPQ.

That is C is the setof all phrase concepts which occur in both the query and document.
lation is then calculated using D + C and Q + C only.

Corre-In this way it isguaranteed that phrase concepts cannot lower the correlation; and in theworst case when no phrases cooccur, C = 0 and the correlation is the sameas when no phrases are used.

This process alleviates two of the major

problems associated with phrase use.

First, by ignoring all unmatched con-cepts, the vectors cannot become diluted and thus phrases cannot harm theretrieval.

Secondly, phrases are used only as a relevancy indicator andtheir far weaker role of nonrelevancy indicator is ignored.
The next two experiments involve the use of statistical and syntactic phrases as previously determined, but incorporating the cooccurrence
scheme.

The correlation process for each document query pair involves

forming a master document containing all the word concepts in the original
vector as well as all phrase concepts common to both the document andquery.

A master query is similarly formed.

The cosine coefficient isthen calculated for the master document and master query.
are shown in Fig. 4 and Fig. 5.

The results

V-8

I.Oh

Syntactic Phrase(with cooccurrence).8

Standard Run(no phrases)

S.6
\>

a. -4
•#••••

.2

.4

.6

.8

1.0

RecallAverage Precision-Recall Curve for Experiment 5
Fig. 5

1.0
Cooccurrence Phrases(no phrase list).8

Results from
Experiment I

o -6
o

£ -4

N=^
J_

-L

.4

.6

.8

1.0

RecallAverage Precision-Recall Curve for Experiment 6
Fig. 6

V-9

5.

Elimination of the Phrase List
All methods discussed so far for using phrases in retrieval haverequired a phrase list.

As previously mentioned the creation of theselists, whether by hand or by statistical processes, raises certain inherent
problems.

In general, it is far more desirable

phrases without the need of such a list.

to be able to determine

One possible solution is to per-form a syntactic analysis of the text, and determine all the phrases.
The set of phrases thus generated is then normalized to associate all syntactically different but semantically identical phrases.

This is accom-

plished, for example, by the use of a criterion tree-matching scheme.
Each phrase in the reduced set is then assigned a concept number, and retrieval proceeds as in the previous cases.

However the syntactic analysis

and normalization processes are prohibitively complex and produce a verylarge number of phrases.

For these reasons an alternate method is used.

The scheme used centers on the relation between pairs of concepts,
and allocating cooccurrence phrases.

A cooccurrence phrase is defined as

any pair of concepts which occurs in both the document and the query andwhich has the same or equivalent syntactic relation in both.
firstsyntactically analyzed by hand.

The text is

For each word in the text, the syn-tactic relation between it and every other word in the text is then determined.

For a sentence of length n this can lead to a maximum of n(n-l)

relations.

In practice, however, the number of relations is far smaller

than this because many words are not related.

The types of relations consi-

dered are listed in Table 1.
After the relations are determined, each word is replaced by its
concept number, and the two concepts and their relations are encoded

| Code Number

Type of Relation

01
02
03
04
05
06

Modification
ParallelSubject-Verb
Subject-Predicate nominative
Subject-Direct object
Verb-Object

The following rules are used1.

to determine relations:

Modificationa.

In a string of adjectives followed by a noun, each adjective
modifies all following adjectives as well as the noun.

b.

In the construction;
ADJ NOUN-1 and NOUN-2
the adjective modified both nouns.

However, the case of

NOUN-1 and ADJ NOUN-2c.

the adjective modifies only the second noun.
In the construction
ADJ-1 and ADJ-2 NOUN
both adjectives modify the noun.

d.

For certain prepositional phrases of the form
NOUN-1 PREP NOUN PHRASE
the entire noun phrase is treated as if it occurred in frontof, and modifying NOUN-1.

The most common preposition usedin this way is "of" although others are also used.
A predicate adjective modifies its subject

Parallela.

Two words of similar type and acting in similar roles are
considered parallel.

For example;

Information storage and retrieval
Fast and accurate method
Neither programmers, analysts, nor researchers
All the other relations are fairly straightforward.

Relations Between Concepts
Table 1V-ll

XXXYYYZZ, where XXX is the first concept, YYY, the second, and ZZ, the relation between them.

The order of the two concepts is significant for all

relations except parallel; and for this case the smaller concept always
appears first.

The encoded concepts and relations are then treated asconcept numbers and the retrieval process is carried out using the cooccurrence scheme.

The results are seen in Fig. 6.

A system that uses a phrase list can recognize equivalent phrases
whose constituent concepts are not equivalent.

For example the phrases"memory holding" and "data processing" are both assigned the same phrase
concept number by the SMART phrase list, while each of the four words falls
into a different concept class.

The recognition of such equivalent phrases

is impossible for systems which do not employ such a list.

It is therefore

expected that the results of this experiment should be somewhat inferior tothose achieved in the previous experiments.

However, retrieval without therequirement of a phrase list seems to be a more reasonable approach to the
problem especially in the case of large document collections.

6.

Analysis of Results
The results of the six retrieval experiments are summarized inFig. 7.

The plus or minus to the right of each figure indicates whether

it is above ( + ) or below (-) the value achieved for that recall level whenno phrases are used (experiment l ) . The results clearly show that there
is no great gain achieved by the use of phrases and in some cases theiruse appears to be actually detrimental.

However, upon more careful analysisof these results, a number of unusual factors are found which make theseresults less discouraging than they initially appear.

1

2

3

4

5

6

.1

.61242.62538+.64999+.58761-.56242-.54575-.2.55242.62538+.59999+.52761-.50242-.48575-.3.48618.49573+.47975-.46385-.48261-.48618+-.4.42868.40780-.44225+.42228-.42437-.42794-'5.43344.40587-.44701+.40955-.43270-.43270-.6.32924.33295+.33162+.32076-.33376+.33411+.7.25489.28381+.25514+.26077+.26165+.25515+.8.2536828781+.24309-.25543+.25711+.25061-.9.2413327709+.23509-.24329+.24914+.24313+1.0.2413327709+.23509-.24329+.24914+.24313+

Recall1

Experiments:
1.
2.
3.
4.
5.
6.

No phrases
Statistical phrases, no cooccurrence
Syntactic phrases, no cooccurrence
Statistical phrases with cooccurrence
Syntactic phrases with cooccurrence
Cooccurrence phrases, no phrase lists

Precision Values at each Recall Level
for Each ExperimentFig. 7

V-13

Consider first the results obtained with the statistical and syntactic phrases.

It is argued in section 4 that the use of cooccurrence im-proves the retrieval quality.
opposite is true.

The results seem to indicate that exactly theUpon analysis of the retrieval output it is discoveredthat the reason for this apparent turnabout is the dilution of nonrelevant
concept vectors due to unmatched concepts.

For many of the queries analyzed,

there are one or more documents, highly correlated to that query, but nonrelevant, and which have a relatively large number of phrases which are notmatched by the query.

Because of the dilution effect which occurs when co-occurrence is not used, the correlations for these documents are lowered
often below that of one of the relevant documents.

The rank of the relevant

document is thus raised by default although its correlation is often notaltered.

Consider for example the correlation of document 11 with query A4.

With no phrases used, this nonrelevant document ranks sixth with a correlation of 0.24818.

The document has 13 phrases which do not match the query.

When retrieval is performed using these phrases without cooccurrence, thecoefficient is reduced to 0.15599 and the rank lowered to ninth place.

This

allows one of the relevant documents to move ahead producing an apparent
improvement in retrieval quality.

When cooccurrence is used there are nophrase matches, the coefficient remains 0.24818, and the relevant document
is not allowed to move up.

Considering the entire set of 33 documents rele-vant to the test queries, theranks of 16 are improved by the use of sta-tistical phrases with no cooccurrence.
move up in correlation coefficient.

However of these 16, only 7 actually

The remaining 9 lose in correlation but

gain in rank due to the dilution and consequent lowering of nonrelevant documents.

Ten of the 33 documents lose in both rank and coefficient, mostlyV-14

by dilution, while 7 remained fixed in rank.

Of these 7, 5 are reduced incoefficient but by an amount insufficient to drop the ran]..

It is also dis-covered that most of the documents with a large number of phrases are not
relevant to any test query.

Thus the apparent improvement achieved when co-occurrence is not used is almost entirely due to the lowering in coefficientof certain nonrelevant documents.

The fact that most of the documents witha large number of phrases are not relevant is not true in general; and theapparent improvement of experiment 2 over experiment 4 is clearly exceptional.
Attention is next focused on the fact that precision values obtained
for statistical and syntactic phrase experiments with cooccurrence (experiments 4 and 5) fall below those achieved with no phrases at all.
be understood by considering the experiment l\ results.

This canOf the 33 relevant

documents, this phrase process improves both the rank and correlation for 9;
5 are reduced in rank; while the remaining 19 are unchanged.

Overall thisseems to be an improvement, but this is not born out by the tabulated res alts
in Fig. 7.

The reason for this lies almost entirely with query B5.

It hasonly one relevant document and the phrase process loweres its rank from second to fifth thus lowering its precision for all recall levels, from 0.5
to 0.2.

This is a considerable decrease in precision, and since the values

are averaged over only ten queries, the effect on the average is substantial.
If precision values are taken for the nine other queries only, the values forthe phrase processes exceed those for the no-phrase experiment for all reeall
levels.

Thus with the exception of one rather unusual query, the results ob-

tained by using the phrase process with cooccurrence (experiment 4 and, withsimilar reasoning, experiment 5) are slightly better than those obtained without phrases.

V-15

The tabulations in Fig. 7 indicate that results achieved by using
the no-phrase-list method (experiment 6) are inferior to both the phrase
list and no-phrase results.

This is in part due to the methodTs inability

to associate phrases with different constituent concepts.

The inferior

results can also be blamed on the very small number of cooccurrences.

Of

the more than 800 relations entered, only 28 cooccurrences between document
and query are found.
on the queries.

This very low number can be blamed, at least in part,

They are all quite short and contain very few phrases.

The queries also tend to be quite general.

Since retrieval is performed byconcept matching and not by hierarchical expansion, general queries do notalways produce the desired results.

Of the 28 cooccurrences, only 5 occur

between a query and one of its relevant documents.

In the ten test queries,

three have no cooccurrences at all, and their results are clearly not altered from the no-phrase case.

Four queries have cooccurrences in nonrele-vant documents only and these results are obviously lowered.

The three re-maining queries have cooccurrences in relevant documents; however, an improvement is realized in only one.

Of the other two, one shows an improvement incorrelation coefficient, but insufficient for a rank change, and the otherhas cooccurrences in nonrelevant documents which overshadowed any improvement.

These results cast some doubt on the value of this method.

Howeverthe present evidence is really inconclusive.
To summarize, it appears that contrary to the tabulated results, thephrase processes really do provide some improvement in retrieval performance.
These improvements, however, are small and may not be worth the extra effort
needed to achieve them.

Before final judgment is passed on these tests, it

must be determined whether the tests are fair.

In the opening section ofV-16

this paper, the basic motivation for the use of phrases is stated to be theseparation of highly correlated documents.

A document collection thus has

to provide such documents in order for a fair test to be conducted.
ment-document correlation is performed on the ADI collection.

A docu-The results

are omitted here, but it is sufficient to say that with an average correlation of only 0.1, and a maximum of under 0.8, this collection is far too
sparse to provide a conclusive test.

The refinement added to the documents

and queries by the use of syntax is not needed in such a sparse corpus andtherefore substantial performance gains cannot be expected.

7.

Conclusion
One general problem encountered in using phrases for retrieval con-cerns high frequency words.

These words occur too frequently to be of any

use in retrieval and they are therefore not included in the concept vectors.
Certain of these words, however, can enter into significant phrases.
word "system" for example is one such high frequency word.

The

By itself it

carries little meaning, but in phrases such as "system programming" and"systems analysis", it is significant.

But because "system" is a high fre-quency word, these phrases cannot be located.

This problem will probably

solve itself for larger and more general collections where the list of highfrequency words is much more limited.

While solving one problem, the lar-ger collection creates another; that of the metalanguage; that is, words
and phrases which convey no significant meaning as is seen in the underlined
portion of the following sentence:
methods of syntactic analysis.

In this paper the author discusses the

In the ADI collection metalanguage words arealmost all included in the high frequency word list and thus eliminated.

V-17

This is impossible for larger collections and thus some means of automatically determining and eliminating metalanguage segments will have to bedevised.
The results presented in this study seem rather discouraging.

Theydo, however, point out a number of other areas that must be investigated inorder to determine conclusively the value of phrases in retrieval.

First,

the experiments presented here must be retried using more dense collections.
The amount of syntactic and semantic structure required in the concept vectors to achieve desired results seems to be related to the density of thecollection.

This relation should be investigated.

ther study is that of relevancy judgments.

A second area for fur-

It is possible that significant

improvement in retrieval quality cannot be achieved until some investigation is made into what makes a user deem a certain document relevant to agiven query.

And third, in order to implement syntactic or cooccurrencephrases into a usable system, an automated syntactic analyzer must be used.
A number of such schemes exist including those by Hillman [1], Sager[2],

and Baxendale [3]. None of these produce perfect results and further study
must be made to improve this facility.

V-18

References[1]

Hillman, K., The Leader System, Proc. 1969 AFIPS Spring
Joint Computer Conference, Thompson Book Co,, Washington,
May 1969.

[2]

Sager, N., "Report on String Analysis", NSF Report, University of Pennsylvania, March 1966,[3]

Baxendale, P., "Documentation for an Economical Program for the
Limited Parsing of English: Lexicon, Grammar, and Flowcharts"
IBM Corporation Report RJ 386, August 1966,