Lecture

Lexicons, n-grams and Language Models

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture covers the concepts of lexicons, n-grams, and language models. It starts with an introduction to lexicons and their field implementations, followed by an explanation of n-grams and probabilities. The lecture delves into the n-gram approach, smoothing techniques, and examples of language identification and spelling error correction. It emphasizes the importance of lexica for recognizing and classifying words, the effectiveness of n-grams for various tasks, and the significance of smoothing techniques in estimating n-gram probabilities.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Related concepts (32)

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition.

Nondeterministic finite automaton

In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article.

Finite-state transducer

A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA. An FSA defines a formal language by defining a set of accepted strings, while an FST defines relations between sets of strings.

Deterministic finite automaton

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run.

Quantum finite automaton

In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.

Related lectures (64)

Probability and Statistics

Delves into probability, statistics, paradoxes, and random variables, showcasing their real-world applications and properties.

Probability and Statistics

Introduces probability, statistics, distributions, inference, likelihood, and combinatorics for studying random events and network modeling.

Probability and Statistics: Fundamental Theorems

Explores fundamental theorems in probability and statistics, joint probability laws, and marginal distributions.

State Space Models: Expressivity of Transformers

Covers state space models and the expressivity of transformers in sequence copying tasks.

Probability and Statistics

Covers probability, statistics, independence, covariance, correlation, and random variables.

Related concepts (32)

Finite-state machine

Nondeterministic finite automaton

Finite-state transducer

Deterministic finite automaton

Quantum finite automaton