Title: Theory / Important / CS / Algo / Artificial intelligence / Introduction{ / 6 Communicating, perceiving, and acting
Tags: récupéré examplesSwitchExample1 fromAlgorithm hasNotNewEffectReturnsMeaning hasSeenConjDef oldAlgoNewName some_instruction MissingMedia effectNew instructionToImplementation keepAlgo
On every note of this deck, unless a note says otherwise:
Chapter: 22

Name: A language
Typ: Some set of strings
Page: 860
Section: 2
Chapter: 22

Name: A grammar
Definition: A set of rules defining a language
Page: 860
Section: 2

Name: A semantic
Definition: A function from elements of the language to some meaning.
Page: 860
Section: 2
Variables: \(L\) a language

Name: Natural language model
Definition: Probability distribution over sentences
Page: 861
Section: 2

Name: Ambiguity in language
Definition: The fact that a single sentence can means two things
Page: 861
Section: 2
Example: He saw her duck

Name: Characters
Definition: Letters, digits, punctuation, spaces, ...
Page: 861
Section: 1.1

Name: An \(n\)-gram
Definition: A sequence of \(n\) written symbols
Page: 861
Section: 1.1
Variables: \(n\in\mathbb N\)

Name: A unigram
Definition: A 1-gram
Page: 861
Section: 1.1

Name: A bigram
Definition: A 2-gram
Page: 861
Section: 1.1

Name: A trigram
Definition: A 3-gram
Page: 861
Section: 1.1

Name: An \(n\)-gram model
Definition: A Markov chain of order \(n-1\)
Page: 861
Section: 1.1

Name: A corpus
Definition: A body of text
Page: 861
Section: 1.1
Name2: corpora (plural)

Name: Language identification
Definition: Determining, given a text, in which natural language it is written in.
Page: 862
Section: 1.1

Name: Genre classification
Definition: Deciding whether a text is news, legal, scientific, novel ...
Page: 862
Section: 1.1

Name: Smoothing
Definition: Adjusting the probability of low-frequency counts.
Page: 863
Section: 1.2

Name: Add-one Smoothing
Definition: If some variable \(X\) is false in \(n\)-observation, its probability is \(\frac 1{n+2}\)
Page: 863
Section: 1.2
Extra: n+2 and not n+1, for some reason

Name: Backoff model
Definition: A language model based on \(n\)-grams. But for \(n\)-gram with low or zero probability, its \(n-1\)-gram probability is used.
Page: 863
Section: 1.2

Name: Linear interpolation smoothing
Definition: A linear combination of trigram, bigram and unigram models.
Page: 863
Section: 1.2
Context: Language model, AI

Question: How to choose linear coefficients for linear interpolation smoothing of a backoff model ?
Answer: Either fixes them - the sum should be one, or they can be trained with expectation-maximization algorithm.
Page: 863
Chapter: 22
Section: 1.2

Question: What to do, for markov model, based on \(n\)-gram, for the \(n-1\) first characters ?
Answer: Either consider negative characters to be space, or use \(i-1\)-gram for the \(i\)-th character.
Page: 863
Chapter: 22
Section: 1.2

Name: Perplexity
Definition: The function sending a string \(c_{1:N}\) to the value \(P(c_{1:N})^{-\frac 1N}=\frac{1}{\sqrt[N]{P(c_{1:N})}}\).
Page: 863, 864
Section: 1.2
Context: Artificial Inteligence
Intuition: Reciprocal of probability, normalized by sequence length weighted average branching factor of a model

Name: Vocabulary
Definition: The set of symbols that make up the corpus and the model
Page: 864
Section: 1.4

Name: Out of vocabulary words
Definition: Words in a model which does not belong to the vocabulary
Page: 864
Section: 1.4

Question: How to deal with unknown words.
Answer: When creating a model from a training corpus, each first encounter of a new word is replaced by <UNK>. (Or <EMAIL>, <NUM>...)
Each unknown words in the non-training corpus are replaced by <UNK>
Page: 864
Chapter: 22
Section: 1.4

Name: Text classification
Definition: Given a text of some kind, decide which of a predefined set of classes it belongs to.
Page: 865
Section: 2
Context: Text
Example: Language identification
Name2: Categorization
Example2: Genre classifiaction
Example3: sentiment analysis
Example4: spam detection

Name: Sentiment analysis
Definition: Classifying a movie or product review as positive or negative
Page: 865
Section: 2

Name: ham
Definition: not-spam
Page: 865
Section: 2
Context: AI

Page: 862
Implementation: Construct a trigram character model of each languages of \(\mathcal L\).
Choose the language \(\ell\) which maximize \(P(\ell)\Pi_{i=1}^NP(c_i\mid c_{i-2:i-1},\ell)\)
\(P(\ell)\) being the probability that an unknown text is in language \(\ell\)
Section: 1.1
Chapter: 22
Effect: Language identification
Variables: \(\mathcal L\) a set of languages,
\(c_1\dots c_N\) a text

Page: 863
Implementation: Spliting a corpus into a training corpus and validation corpus.
Training a model with training corpus, and testing it on validation corpus.
Section: 1.2
Chapter: 22
Name: Cross-validation

Name: Bag of words
Definition: Unigram representation of language modeling
Page: 866
Section: 2

Name: An adversarial task
Definition: A task such that an attacker modify its action according to ours
Page: 866
Section: 2

Name: Feature selection
Definition: Restricting the study to a subset of \(n\)-grams, which are interesting for the current problem.
Page: 866
Section: 2
Context: Natural language processing
Example: Do not consider «of the» in text analysis.

Name: Data compression
Definition: The problem of saving efficiently data.
Page: 866
Section: 2.1

Name: A compression algorithm
Definition: An injective algorithm which sends data of interest to smaller representation of this data.
Page: 866
Section: 2.1

Name: Information retrieval
Definition: A corpus of documents. Each system must decide what it wants to treat as a document: a paragraph, a page, or a multipage text.
Page: 867
Section: 3
Definition2: Queries posed in a query language
Example: Boolean keyword model
Conjdef: A tuple
Definition3: A result set
Abbreviation: IR
Intuition: finding documents that are relevant to a user’s need for information
Definition4: A presentation of the result set

Name: The query foo
Page: 867
Section: 3
Context: Information retrieval
Notation: [foo]

Name: Boolean keyword model
Definition: Each word in the document is treated as a Boolean feature that is true of a document if the word occurs in the document and false if it does not
Page: 867
Section: 3
Definition2: Query language: Boolean expressions over features
Conjdef: The information retrieval
Definition3: Return the documents such that query evaluates to true

Name: The term frequency of \(q\) in \(d\)
Definition: The frequency of the number of times \(q\) appears in \(d\) (according to Artificial inteligence, a modern approach)
Page: 867
Section: 3.1
Variables: \(q\) a word,
\(d\) a document
Notation: \(TF(q,d)\)
Definition2: \[\log\left(1+\frac{\texttt{Number of occurence of q in d}}{\text{number of words in d}}\right)\]
according to database system concept

Definition: The number of document containing \(q_i\)
Page: 867
Section: 3.1
Variables: \(q_i\) a word,
\(d_1,\dots, d_N\) documents
Notation: \(DF(q_i)\)

Page: 868, https://en.wikipedia.org/wiki/Okapi_BM25
Implementation: \(\sum_{i=1}^NIDF(q_i).\frac{TF(q_i,d_j)\cdot (k+1)}{TF(q_i,d_j)+k\cdot \left(1-b+b.\frac{|d_j|}L\right)}\) with \(k,b\) parameters
Section: 3.1
Chapter: 22
Variables: \(q_1,\dots,q_N\) words,
\(d_1,\dots, d_M\) documents
Name: \(BM25(d_j,q_{1:N})\)
Returns: Relevancy of \(d_j\) for the query \(q_{1:N}\)
Extra: BM for Best Matching

Name: Inverse document frequency of word \(q_i\)
Definition: \(\log{\frac{N-DF(q_i)+.5}{DF(q_i)+.5}}\) (according to Artificial inteligence, a modern approach)
Page: 869, https://en.wikipedia.org/wiki/Tf%E2%80%93idf
Section: 3.1
Variables: \(q_1,\dots,q_N\) words,
\(d_1,\dots, d_M\) documents
Definition2: \(\frac 1{n(t)}\) with \(n(t)\) the number of document containing \(t\)
(according to database system concept)
Abbreviation: \(IDF(q_i)\)
Intuition: how much information the word provides, that is, whether the term is common or rare across all documents.

Name: hit list
Definition: An index, associating to each word the set of documents relevant to this document.
Page: 869
Section: 3.1
Variables: \(q_1,\dots,q_N\) words,
\(d_1,\dots, d_M\) documents
Context: Information retrieval

Name: Precision
Definition: The proportion of documents in the result set that are actually relevant.
Page: 869
Section: 3.2
Context: Information retrieval

Name: Recall
Definition: the proportion of all the relevant documents in the collection that are in the result set
Page: 869
Section: 3.2
Context: Information retrieval

Definition: Precision, restricted to the first \(n\) returned documents
Page: 869
Section: 3.2
Variables: \(n\in\mathbb N\)
Context: Information retrieval
Notation: P@n

Definition: Harmonic mean of recall and precision
Page: 869
Section: 3.2
Context: Information retrieval
Notation: \(F_1\)

Name: Harmonic mean of \(x\) and \(y\)
Definition: \(\frac{2xy}{x+y}\)
Page: 869
Section: 3.2
Variables: \(x,y\in\mathbb R\)
Context: Information retrieval

Question: How do we know whether an IR system is performing well?
Answer: We undertake an experiment in which the system is given a set of queries and the result sets are scored with respect to human relevance judgments.
Page: 869
Chapter: 22
Section: 3.22
Context: Information retrieval

Name: Case folding
Definition: Having all text in upper case, to avoid not finding a document because it has another case
Page: 870
Section: 3.23
Context: Information retrieval

Name: Stemming
Definition: Remove suffixes of words, in order to retain the important part.
Page: 870
Section: 3.23
Context: Information retrieval
Example: become Couch
Applied to: Couches

Name: Synonyms
Definition: Words with similar senses
Page: 870
Section: 3.23
Context: Information retrieval
Example: Couch and sofa
Applied to: Tim Couches should not bring result related to sofa

Name: A word related to w
Definition: A word occurring regularly near w in the corpus or in request
Page: 870
Section: 3.23
Variables: w a word
Context: Information retrieval
Example: sofa
Applied to: leather

Name: Metadata
Definition: data outside of the text of the document
Page: 870
Section: 3.23
Variables: w a word
Context: Information retrieval
Example: Link in the web

Name: A link
Definition: A reference to another document in a document
Page: 870
Section: 3.3
Context: Information retrieval

Name: PageRank
Definition: First Google's algorithm
Page: 870, 871
Section: 3.4
Context: Information retrieval
Definition2: A link to a page is similar to a vote for this page.
Definition3: the function associating to page \(p\) \(\frac{1-d}{N}+d\sum_{i}\sum_i\frac{PR(in_i)}{C(in_i)}\) with \(N\) the total number of page, \(in_i\) the pages that link in to \(p\), \(d\) a damping factor
Abbreviation: \(PR\)
Definition4: Probability that a random surfer visit this page at an arbitrary moment

Question: What idea set Google apart from other web search engines
Answer: Page Rank
Page: 870
Chapter: 22
Section: 3.4
Context: Information retrieval
Answer2: When there is a link to page bar and the text of the link is foo, foo is used as a meta data for bar

Name: Random surfer model
Definition: imagine a Web surfer who starts at some random page and begins exploring.
With probability \(d\) (we’ll assume \(d=0.85\)) the surfer clicks on one of the links on the page (choosing uniformly among them), and with probability \(1-d\) she gets bored with the page and restarts on a random page anywhere on the Web.
Page: 871
Section: 3.4
Context: Information retrieval

Page: 872
Section: 3.4
Notation: computing hubs and authorities with respect to a
query.
Chapter: 22
Definition: HITS
Example: RELEVANT-Pages fetches the pages that match the query, and Expand -Pages adds
in every page that links to or is linked from one of the relevant pages. Normalize divides
each page’s score by the sum of the squares of all pages’ scores (separately for both the
authority and hubs scores).
Commutative: Information retrieval
Intuition: Hyperlink-Induced Topic Search
Codomain: Hubs and Authorities

Name: An authority on \(q\)
Definition: A page, to the degree that other pages in the relevant set point to it.
Page: 871
Section: 3.4
Variables: \(q\) a query
Context: Information retrieval, IHTS

Name: An hub on \(q\)
Definition: A page, to the degree that it points to other authoritative pages in the relevant set.
Page: 871
Section: 3.4
Variables: \(q\) a query
Context: Information retrieval, IHTS

Name: Question answering
Definition: An IR problem where the query is a question, and answer should be a short answer.
Page: 871
Section: 36
Context: Information retrieval
Example: MSR

Name: Natural language processing
Page: 871
Section: 36
Context: Information retrieval
Example: the system would have to know that ending a life can be a killing, that “He” refers to Booth
Abbreviation: NLP
Applied to: «John Wilkes Booth altered history with a bullet. He will forever be known as the man who ended Abraham Lincoln’s life.»