Module 7: Communicating, Perceiving and Acting - Information Retrieval

First, nomenclature…
• Information retrieval (IR)
• Focus on textual information (= text/document retrieval)
• Other possibilities include image, video, music, …
• What do we search?
• Generically, “collections”
• Less-frequently used, “corpora”
• What do we find?
• Generically, “documents”
• Even though we may be referring to web pages, PDFs, PowerPoint slides,
paragraphs, etc.
Abstract IR Architecture
Query Documents
c qui sition
ent a )
docum b crawling
we
(e.g.,
online offline
Representation Representation
Function Function

Query Representation Document Representation

Comparison
Function Index

Hits
How do we represent text?
• Remember: computers don’t “understand” anything!
• “Bag of words”
• Treat all the words in a document as index terms
• Assign a “weight” to each term based on “importance”
(or, in simplest case, presence/absence of word)
• Disregard order, structure, meaning, etc. of the words
• Simple, yet effective!
• Assumptions
• Term occurrence is independent
• Document relevance is independent
• “Words” are well-defined
Sample Document
McDonald's slims down spuds
Fast-food chain to reduce certain types of fat
“Bag of Words”
in its french fries with new cooking oil.
NEW YORK (CNN/Money) - McDonald's Corp. is 14 × McDonalds
cutting the amount of "bad" fat in its french fries
nearly in half, the fast-food chain said Tuesday as it
moves to make all its fried menu items healthier.
12 × fat
But does that mean the popular shoestring fries won't 11 × fries
taste the same? The company says no. "It's a win-win
for our customers because they are getting the same
great french-fry taste along with an even healthier
8 × new
nutrition profile," said Mike Roberts, president of
McDonald's USA. 7 × french
But others are not so sure. McDonald's will not
specifically discuss the kind of oil it plans to use, but
6 × company, said, nutrition
at least one nutrition expert says playing with the
formula could mean a different taste. 5 × food, oil, percent, reduce,
Shares of Oak Brook, Ill.-based McDonald's (MCD: taste, Tuesday
down $0.54 to $23.22, Research, Estimates) were
lower Tuesday afternoon. It was unclear Tuesday
whether competitors Burger King and Wendy's
…
International (WEN: down $0.80 to $34.91, Research,
Estimates) would follow suit. Neither company could
immediately be reached for comment.
…
Information retrieval models
• An IR model governs how a document and a query are
represented and how the relevance of a document to
a user query is defined.
• Main models:
• Boolean model
• Vector space model
• Statistical language model..
• etc

7
Boolean model
• Each document or query is treated as a “bag” of
words or terms. Word sequence is not considered.
• Given a collection of documents D, let V = {t1, t2, ..., t|
V|} be the set of distinctive words/terms in the
collection. V is called the vocabulary.
• A weight wij > 0 is associated with each term ti of a
document dj ∈ D. For a term that does not appear in
document dj, wij = 0.
dj = (w1j, w2j, ..., w|V|j),

8
Boolean model (contd)
• Query terms are combined logically using the Boolean
operators AND, OR, and NOT.
• E.g., ((data AND mining) AND (NOT text))
• Retrieval
• Given a Boolean query, the system retrieves every
document that makes the query logically true.
• Called exact match.
• The retrieval results are usually quite poor because
term frequency is not considered.

9
 Sec. 1.3

Boolean queries: Exact match

• The Boolean retrieval model is being able to ask a
query that is a Boolean expression:
– Boolean Queries are queries using AND, OR and NOT to join
query terms
• Views each document as a set of words
• Is precise: document matches condition or not.
– Perhaps the simplest model to build an IR system on
• Primary commercial retrieval tool for 3 decades.
• Many search systems you still use are Boolean:
– Email, library catalog, Mac OS X Spotlight

10
Strengths and Weaknesses
• Strengths
• Precise, if you know the right strategies
• Precise, if you have an idea of what you’re looking for
• Implementations are fast and efficient
• Weaknesses
• Users must learn Boolean logic
• Boolean logic insufficient to capture the richness of language
• No control over size of result set: either too many hits or none
• When do you stop reading? All documents in the result set are considered “equally
good”
• What about partial matches? Documents that “don’t quite match” the query may be
useful also
Vector Space Model
t3
d2

d3
d1
θ
φ
t1

d5
t2
d4

Assumption: Documents that are “close together” in

vector space “talk about” the same things

Therefore, retrieve documents based on how close the

document is to the query (i.e., similarity ~ “closeness”)
Similarity Metric
• Use “angle” between the vectors:  
d j d k
cos( )   
d j dk
 

n
d j d k w w
i 1 i , j i , k
sim(d j , d k )    
i 1 i, j i 1 i,k
n n
d j dk w 2
w 2

 
sim(d j , d k ) d j d k i 1 wi , j wi ,k
n

• Or, more generally, inner products:

Vector space model
• Documents are also treated as a “bag” of words or terms.
• Each document is represented as a vector.
• However, the term weights are no longer 0 or 1. Each
term weight is computed based on some variations of TF
or TF-IDF scheme.

14
Term Weighting
• Term weights consist of two components
• Local: how important is the term in this document?
• Global: how important is the term in the collection?
• Here’s the intuition:
• Terms that appear often in a document should get high weights
• Terms that appear in many documents should get low weights
• How do we capture this mathematically?
• Term frequency (local)
• Inverse document frequency (global)
[Link] Term Weighting
N
wi , j tf i , j log
ni
wi , j weight assigned to term i in document j

tf i, j number of occurrence of term i in document j

N number of documents in entire collection

ni number of documents with term i

Vector space model: Example
Vector space model: Example
Some formulas for
Similarity
Dot product Sim ( D, Q )  (ai * bi )
t1
 (a * b ) i i
D
Sim ( D, Q )  i

Cosine  a *b i
2
i
2
Q
i i

2 (ai * bi ) t2
Sim ( D, Q )  i
Dice a i
2
  bi
2

i i

 (a * b ) i i
Sim ( D, Q )  i
Jaccard  a   b   (a * b )
i
2
i
2
i i
i i i

19
Retrieval in vector space model
• Query q is represented in the same way or slightly
differently.
• Relevance of di to q: Compare the similarity of query q
and document di.
• Cosine similarity (the cosine of the angle between the
two vectors)

• Cosine is also commonly used in text clustering

20
An Example
• A document space is defined by three terms:
• hardware, software, users
• the vocabulary
• A set of documents are defined as:
• A1=(1, 0, 0), A2=(0, 1, 0), A3=(0, 0, 1)
• A4=(1, 1, 0), A5=(1, 0, 1), A6=(0, 1, 1)
• A7=(1, 1, 1) A8=(1, 0, 1). A9=(0, 1, 1)
• If the Query is “hardware and software”
• what documents should be retrieved?

21
An Example (cont.)
• In Boolean query matching:
• document A4, A7 will be retrieved (“AND”)
• retrieved: A1, A2, A4, A5, A6, A7, A8, A9 (“OR”)
• In similarity matching (cosine):
• q=(1, 1, 0)
• S(q, A1)=0.71, S(q, A2)=0.71, S(q, A3)=0
• S(q, A4)=1, S(q, A5)=0.5, S(q, A6)=0.5
• S(q, A7)=0.82, S(q, A8)=0.5, S(q, A9)=0.5
• Document retrieved set (with ranking)=
• {A4, A7, A1, A2, A5, A6, A8, A9}

22
Vector Space Model
A Running Example
A Running Example
• Step 1 – Extract text (i.e. no preposition)
This is a data
mining course. This is a data mining course

We are studying
text mining. Text
We are studying text mining
mining is a Text mining is a subfield of
subfield of data
mining.
data mining

Mining text is
interesting, and I
Mining text is interesting and
am interested in I am interested in it
it.
24
P. 24
A Running Example
• Step 2 – Remove stopword
This is a data
mining course. This is a data mining course

We are studying We are studying text mining Text mining is

text mining. Text a subfield of data mining
mining is a
subfield of data
mining.

Mining text is Mining text is interesting and I am

interesting, and I interested in it
am interested in
it.
25
P. 25
A Running Example
• Step 3 – Convert all words to lower case
This is a data
mining course. This is a data mining course

We are studying
text
We are studying text mining Text mining is
text mining. Text a subfield of data mining
mining is a
subfield of data
mining.

Mining text is
mining
Mining text is interesting and I am
interesting, and I interested in it
am interested in
it.
26
P. 26
A Running Example
• Step 4 – Stemming
This is a data mine
This is a data mining course
mining course.

We are studying
study mine textmine
We are studying text mining Text mining is
text mining. Text a subfield of data mining
mining is a
subfield of data
mine
mining.

Mining text is
mine interest
Mining text is interesting and I am
interesting, and I interested in it
am interested in
it.
interest
27
P. 27
A Running Example
• Step 5 – Count the word frequencies
This is a data mine
This is a data mining course
mining course.
coursex1, datax1, minex1

We are studying
study mine textmine
We are studying text mining Text mining is
text mining. Text a subfield of data mining
mining is a
subfield of data
mining. mine
datax1, minex3, studyx1, subfieldx1, textx2

Mining text is
mine interest
Mining text is interesting and I am
interesting, and I interested in it
am interested in
it.
interest
interestx2, minex1, textx1
28
 A Running Example ID word doc freq

• Step 6 – Create an indexing file 1 course 1

This is a data mine 2 data 2
mining course. This is a data mining course
3 interest 1
coursex1, datax1, minex1
4 mine 3
5 study 1
study mine text
We are studying We are studying text mining Text mining is 6 subfield 1
text mining. Text a subfieldmine
of data mining 7 text 2
mining is a
subfield of data
mine
mining.
datax1, minex3, studyx1, subfieldx1, textx2
Mining text is mine interest
Mining text is interesting and I am
interesting, and I interested in it interest
am interested in
it.
interestx2, minex1, textx1
29
A Running Example document
ID word
frequency
• Step 7 – Create the vector space model
1 course 1
This is a data mine
This is a data mining course 2 data 2
mining course.
coursex1, datax1, minex1 3 interest 1
(1, 1, 0, 1, 0, 0, 0) 4 mine 3
5 study 1
We are studying
study mine textmine
We are studying text mining Text mining is 6 subfield 1
text mining. Text a subfield of data mining
7 text 2
mining is a mine
subfield of data
datax1, minex3, studyx1, subfieldx1, textx2
mining.
(0, 1, 0, 3, 1, 1, 2)
Mining text is
mine interest
Mining text is interesting and I am
interesting, and I interested in it
am interested in
it.
interest
interestx2, minex1, textx1
30
(0, 0, 2, 1, 0, 0, 1)
A Running Example
• Step 8 – Compute the inverse document frequency
total documents
IDF ( word ) log
document frequency
This is a data
mining course. document
ID word IDF
(1, 1, 0, 1, 0, 0, 0) frequency
1 course 1 0.477
2 data 2 0.176
We are studying 3 interest 1 0.477
text mining. Text
mining is a 4 mine 3 0
subfield of data
(0, 1, 0, 3, 1, 1, 2)
mining. 5 study 1 0.477
6 subfield 1 0.477
Mining text is 7 text 2 0.176
interesting, and I
am interested in (0, 0, 2, 1, 0, 0, 1)
it.
31
 A Running Example
• Step 9 – Compute the weights of the words
w( word i ) TF ( word i ) IDF ( word i )
This is a data TF ( word i ) number of times word i appears in the document
mining course.
(1, 1, 0, 1, 0, 0, 0) ID word
document
IDF
frequency
(0.477, 0.176, 0, 0, 0, 0, 0)
1 course 1 0.477
2 data 2 0.176
We are studying
text mining. Text 3 interest 1 0.477
mining is a
subfield of data
(0, 1, 0, 2, 1, 1, 2) 4 mine 3 0
mining. (0, 0.176, 0, 0, 0.477, 0.477, 0.352) 5 study 1 0.477
6 subfield 1 0.477
Mining text is
7 text 2 0.176
interesting, and I
am interested in (0, 0, 2, 1, 0, 0, 1)
it.
(0, 0, 0.954, 0, 0, 0, 0.176)
32
P. 32
A Running Example
• Step 10 – Normalize all documents to unit length
w( word i )
w( word i ) 
This is a data w2 ( word1 )  w2 ( word 2 )    w2 ( word n )
mining course.
(1, 1, 0, 1, 0, 0, 0) ID word
document
frequency IDF
(0.938, 0.346, 0, 0, 0, 0, 0)
1 course 1 0.477
2 data 2 0.176
We are studying
text mining. Text 3 interest 1 0.477
mining is a
subfield of data
(0, 1, 0, 3, 1, 1, 2) 4 mine 3 0
mining. 5 study 1 0.477
(0, 0.225 0, 0, 0.611, 0.611, 0.450)
6 subfield 1 0.477
Mining text is
interesting, and I 7 text 2 0.176
am interested in (0, 0, 2, 1, 0, 0, 1)
it.
(0, 0, 0.983, 0, 0, 0, 0.181)
33
A Running Example
• Finally, we obtain the following:
• Everything become structural!
• We can perform classification, clustering, etc!!!!
This is a data document
mining course. ID word IDF
frequency
(0.938, 0.346, 0, 0, 0, 0, 0)
1 course 1 0.477
2 data 2 0.176
We are studying 3 interest 1 0.477
text mining. Text
mining is a (0, 0.225 0, 0, 0.611, 0.611, 0.450) 4 mine 3 0
subfield of data 5 study 1 0.477
mining.
6 subfield 1 0.477
Mining text is
interesting, and I (0, 0, 0.983, 0, 0, 0, 0.181) 7 text 2 0.176
am interested in
it.
34
P. 34
Term frequency —
Inverse document
frequency (TFIDF)
• Term frequency — Inverse document frequency (TFIDF) is based on
the Bag of Words (BoW) model, which contains insights about the less
relevant and more relevant words in a document.

Note
• Bag of words (BoW) converts the text into a feature vector by
counting the occurrence of words in a document. It is not considering
the importance of words.
Term Frequency (TF)
• TF is defined as the ratio of a word’s occurrence in a document to the
total number of words in a document.
• It is a measure of the frequency of a word (w) in a document (d).
 EXAMPLE

• A = “The car is driven on the road”;

• B = “The truck is driven on the highway”

The initial step is to make a vocabulary of unique

words and calculate TF for each document. TF will be
more for words that frequently appear in a document
and less for rare words in a document.
 Inverse Document Frequency
(IDF)
• It is the measure of the importance • IDF measures the rarity of a term
of a word. Term frequency (TF) does across a collection of documents.
not consider the importance of It is calculated as the logarithm of
words. the ratio of the total number of
• Some words such as’ of’, ‘and’, etc. documents to the number of
can be most frequently present but documents containing the term.
are of little significance. • The goal is to penalize words that
• IDF provides weightage to each are common across all documents.
word based on its frequency in the
corpus D.
Term Frequency — Inverse
Document Frequency (TFIDF)
It is the product of TF and IDF.
• TFIDF gives more weightage to the word that is rare in the corpus (all
the documents).
• TFIDF provides more importance to the word that is more frequent in
the document.
What is Natural Language
Processing (NLP)
• The process of computer analysis of input provided in a human
language (natural language), and conversion of this input into
a useful form of representation.
• The field of NLP is primarily concerned with getting computers to
perform useful and interesting tasks with human languages.
• The field of NLP is secondarily concerned with helping us come
to a better understanding of human language.
Forms of Natural Language
• The input/output of a NLP system can be:
• written text
• speech
• We will mostly concerned with written text (not speech).
• To process written text, we need:
• lexical, syntactic, semantic knowledge about the language
• discourse information, real world knowledge
• To process spoken language, we need everything required to process
written text, plus the challenges of speech recognition and speech
synthesis.
Components of NLP
• Natural Language Understanding
• Mapping the given input in the natural language into a useful representation.
• Different level of analysis required:
morphological analysis,
syntactic analysis,
semantic analysis,
discourse analysis, …
• Natural Language Generation
• Producing output in the natural language from some internal representation.
• Different level of synthesis required:
deep planning (what to say),
syntactic generation
• NL Understanding is much harder than NL Generation. But, still both of them are hard.
Why NL Understanding is hard?
• Natural language is extremely rich in form and structure, and very
ambiguous.
• How to represent meaning,
• Which structures map to which meaning structures.
• One input can mean many different things. Ambiguity can be at different levels.
• Lexical (word level) ambiguity -- different meanings of words
• Syntactic ambiguity -- different ways to parse the sentence
• Interpreting partial information -- how to interpret pronouns
• Contextual information -- context of the sentence may affect the meaning of
that sentence.
• Many input can mean the same thing.
• Interaction among components of the input is not clear.
 NLU: Knowledge of Language
• Phonology – concerns how words are related to the sounds that realize them.

• Morphology – concerns how words are constructed from more basic meaning units
called morphemes. A morpheme is the primitive unit of meaning in a language.

• Syntax – concerns how can be put together to form correct sentences and determines
what structural role each word plays in the sentence and what phrases are subparts
of other phrases.

• Semantics – concerns what words mean and how these meaning combine in
sentences to form sentence meaning. The study of context-independent meaning.
Knowledge of Language (cont.)
• Pragmatics – concerns how sentences are used in different situations and how
use affects the interpretation of the sentence.

• Discourse – concerns how the immediately preceding sentences affect the

interpretation of the next sentence. For example, interpreting pronouns and
interpreting the temporal aspects of the information.

• World Knowledge – includes general knowledge about the world. What each
language user must know about the other’s beliefs and goals.
Some NLP Applications
• Machine Translation – Translation between two natural languages.
• See the Babel Fish translations system on Alta Vista.
• Information Retrieval – Web search (uni-lingual or multi-lingual).
• Query Answering/Dialogue – Natural language interface with a database
system, or a dialogue system.
• Report Generation – Generation of reports such as weather reports.
• Some Small Applications –
• Grammar Checking, Spell Checking, Spell Corrector
PAGE RANK ALGORITHM
• Rank Surfer Model

The PageRank for a page p is defined as

• PR(p) is the PageRank of page p

• N is the total number of pages in the corpus,
• PR(ini) are the pages that link in to p
• C(ini) is the count of the total number of out-links on page ini.
• constant d is a damping factor.
PAGE RANK ALGORITHM
PAGE RANK ALGORITHM
 Example 1
Imagine we have a network of 4 web pages (A, B, C, and D), and they are interlinked
as follows

A B

C D
Example

Iteration A B C D
0 0.25 0.25 0.25 0.25
Example
Example
Example
 Example

Iteration A B C D
0 0.25 0.25 0.25 0.25
1 0.25 0.25 0.25 0.25
 Example 2
Imagine we have 3 web pages: A, B, and C. The link structure
between these pages is:

A B

C
 Example

Iteration A B C
0 1 1 1
Example
Example
Example

Iteration A B C
0 1 1 1
1 0.9 0.475 1.325
Example
Example

Iteration A B C
0 1 1 1
1 0.9 0.475 1.325
2 1.177 0.4325 0.83625
Example 3:

Dangling Node
Note: Refer the below link for case
study
• [Link]
echnology-and-building-domain-specific-3a95b42827bb
.
• [Link]
agentic-workflow-patterns-from-scratch-63baa74c54bc
.
• [Link]
models-and-how-do-they-work-41fad9139d07