text:
# Orthogonality

Orthogonality
The line segments AB and CD are orthogonal to each other.

Orthogonality occurs when two things can vary independently, they are uncorrelated, or they are perpendicular.

## Mathematics

In mathematics, two vectors are orthogonal if they are perpendicular, i.e., they form a right angle. The word comes from the Greek ὀρθός (orthos), meaning "straight", and γωνία (gonia), meaning "angle".

### Definitions

• Two vectors, x and y, in an inner product space, V, are orthogonal if their inner product $\langle x, y \rangle$ is zero. This relationship is denoted $x \perp y$.
• Two vector subspaces, A and B, of an inner product space, V, are called orthogonal subspaces if each vector in A is orthogonal to each vector in B. The largest subspace of V that is orthogonal to a given subspace is its orthogonal complement.
• A linear transformation, $T : V \rightarrow V$, is called an orthogonal linear transformation if it preserves the inner product. That is, for all pairs of vectors, x and y, in the inner product space V,
$\langle Tx, Ty \rangle = \langle x, y \rangle.$

This means that T preserves the angle between x and y, and that the lengths of Tx and x are equal.

A term rewriting system is said to be orthogonal if it is left-linear and is non-ambiguous. Orthogonal term rewriting systems are confluent.

A set of vectors is called pairwise orthogonal if each pairing of them is orthogonal; such a set is called an orthogonal set. Non-zero pairwise orthogonal vectors are always linearly independent.

• Curves or functions in the plane are orthogonal if their tangent lines are perpendicular at their point of intersection.

The word normal is sometimes[citation needed] used in place of orthogonal. However, normal may also refer to unit vectors. In particular, an orthogonal set is called orthonormal if all its vectors are unit vectors. So, using the term normal to mean "orthogonal" is often avoided. Sometimes normal is used to describe a straight line that intersects a curve at a right angle. For example, the y-axis is normal to the curve y = x2 at the origin.

### Euclidean vector spaces

In 2- or higher-dimensional Euclidean space, two vectors are orthogonal if their dot product is zero, i.e. they make an angle of 90° or π/2 radians.[1] Hence orthogonality of vectors is an extension of the concept of perpendicular vectors into higher-dimensional spaces.[citation needed] In terms of Euclidean subspaces, the orthogonal complement of a line is the plane perpendicular to it, and vice versa.[citation needed] Note however that there is no correspondence with regards to perpendicular planes, because vectors in subspaces start from the origin.[citation needed]

In 4-dimensional Euclidean space, the orthogonal complement of a line is a hyperplane and vice versa, and that of a plane is a plane.[citation needed]

### Orthogonal functions

It is common to use the following inner product for two functions f and g:

$\langle f, g\rangle_w = \int_a^b f(x)g(x)w(x)\,dx.$

Here we introduce a nonnegative weight function w(x) in the definition of this inner product.

We say that those functions are orthogonal if that inner product is zero:

$\int_a^b f(x)g(x)w(x)\,dx = 0.$

We write the norms with respect to this inner product and the weight function as

$\|f\|_w = \sqrt{\langle f, f\rangle_w}$

The members of a sequence { fi : i = 1, 2, 3, ... } are:

• orthogonal on the interval [a,b] if
$\langle f_i, f_j \rangle=\int_a^b f_i(x) f_j(x) w(x)\,dx=\|f_i\|^2\delta_{i,j}=\|f_j\|^2\delta_{i,j}$
• orthonormal on the interval [a,b] if
$\langle f_i, f_j \rangle=\int_a^b f_i(x) f_j(x) w(x)\,dx=\delta_{i,j}$

where

$\delta_{i,j}=\left\{\begin{matrix}1 & \mathrm{if}\ i=j \\ 0 & \mathrm{if}\ i\neq j\end{matrix}\right.$

is the Kronecker delta. In other words, any two of them are orthogonal, and the norm of each is 1 in the case of the orthonormal sequence. See in particular orthogonal polynomials.

### Examples

• The vectors (1, 3, 2), (3, −1, 0), (1/3, 1, −5/3) are orthogonal to each other, since (1)(3) + (3)(−1) + (2)(0) = 0, (3)(1/3) + (−1)(1) + (0)(−5/3) = 0, and (1)(1/3) + (3)(1) + (2)(−5/3) = 0.
• The vectors (1, 0, 1, 0, ...)T and (0, 1, 0, 1, ...)T are orthogonal to each other. The dot product of these vectors is 0. We can then make the generalization to consider the vectors in Z2n:
$\mathbf{v}_k = \sum_{i=0\atop ai+k < n}^{n/a} \mathbf{e}_i$
for some positive integer a, and for 1 ≤ ka − 1, these vectors are orthogonal, for example (1, 0, 0, 1, 0, 0, 1, 0)T, (0, 1, 0, 0, 1, 0, 0, 1)T, (0, 0, 1, 0, 0, 1, 0, 0)T are orthogonal.
• Take two quadratic functions 2t + 3 and 5t2 + t − 17/9. These functions are orthogonal with respect to a unit weight function on the interval from −1 to 1. The product of these two functions is 10t3 + 17t2 − 7/9 t − 17/3, and now,
\begin{align} & {} \qquad \int_{-1}^1 \left(10t^3+17t^2-{7\over 9}t-{17\over 3}\right)\,dt \\[6pt] & = \left[{5\over 2}t^4 + {17\over 3}t^3-{7\over 18}t^2-{17\over 3} t \right]_{-1}^1 \\[6pt] & = \left({5\over 2}(1)^4+{17\over 3}(1)^3-{7\over 18}(1)^2-{17\over 3}(1)\right)-\left({5\over 2}(-1)^4+{17\over 3}(-1)^3-{7\over 18}(-1)^2-{17\over 3}(-1)\right) \\[6pt] & = {19\over 9} - {19\over 9} = 0. \end{align}
• The functions 1, sin(nx), cos(nx) : n = 1, 2, 3, ... are orthogonal with respect to Lebesgue measure on the interval from 0 to 2π. This fact is central to the theory of Fourier series.

#### Orthogonal states in quantum mechanics

• In quantum mechanics, two eigenstates of a Hermitian operator, ψm and ψn, are orthogonal if they correspond to different eigenvalues. This means, in Dirac notation, that $\langle \psi_m | \psi_n \rangle = 0$ unless ψm and ψn correspond to the same eigenvalue. This follows from the fact that Schrödinger's equation is a Sturm–Liouville equation (in Schrödinger's formulation) or that observables are given by hermitian operators (in Heisenberg's formulation).

## Art and architecture

In art the perspective imagined lines pointing to the vanishing point are referred to as 'orthogonal lines'.

The term "orthogonal line" often has a quite different meaning in the literature of modern art criticism. Many works by painters such as Piet Mondrian and Burgoyne Diller are noted for their exclusive use of "orthogonal lines" — not, however, with reference to perspective, but rather referring to lines which are straight and exclusively horizontal or vertical, forming right angles where they intersect. For example, an essay at the website of the Thyssen-Bornemisza Museum states that "Mondrian ....dedicated his entire oeuvre to the investigation of the balance between orthogonal lines and primary colours." [1]

## Computer science

Orthogonality is a system design property facilitating feasibility and compactness of complex designs. Orthogonality guarantees that modifying the technical effect produced by a component of a system neither creates nor propagates side effects to other components of the system. The emergent behavior of a system consisting of components should be controlled strictly by formal definitions of its logic and not by side effects resulting from poor integration, i.e. non-orthogonal design of modules and interfaces. Orthogonality reduces testing and development time because it is easier to verify designs that neither cause side effects nor depend on them.

For example, a car has orthogonal components and controls (e.g. accelerating the vehicle does not influence anything else but the components involved exclusively with the acceleration function). On the other hand, a non-orthogonal design might have its steering influence its braking (e.g. electronic stability control), or its speed tweak its suspension.[2] Consequently, this usage is seen to be derived from the use of orthogonal in mathematics: One may project a vector onto a subspace by projecting it onto each member of a set of basis vectors separately and adding the projections if and only if the basis vectors are mutually orthogonal.

An instruction set is said to be orthogonal if it lacks redundancy (i.e. there is only a single instruction that can be used to accomplish a given task)[3] and is designed such that instructions can use any register in any addressing mode. This terminology results from considering an instruction as a vector whose components are the instruction fields. One field identifies the registers to be operated upon, and another specifies the addressing mode. An orthogonal instruction set uniquely encodes all combinations of registers and addressing modes.[citation needed]

## Communications

In communications, multiple-access schemes are orthogonal when an ideal receiver can completely reject arbitrarily strong unwanted signals using different basis functions than the desired signal. One such scheme is TDMA, where the orthogonal basis functions are non-overlapping rectangular pulses ("time slots").

Another scheme is orthogonal frequency-division multiplexing (OFDM), which refers to the use, by a single transmitter, of a set of frequency multiplexed signals with the exact minimum frequency spacing needed to make them orthogonal so that they do not interfere with each other. Well known examples include (a, g, and n) versions of 802.11 Wi-Fi; WiMAX; ITU-T G.hn, DVB-T, the terrestrial digital TV broadcast system used in most of the world outside North America; and DMT, the standard form of ADSL.

In OFDM, the sub-carrier frequencies are chosen so that the sub-carriers are orthogonal to each other, meaning that cross-talk between the sub-channels is eliminated and inter-carrier guard bands are not required. This greatly simplifies the design of both the transmitter and the receiver; unlike conventional FDM, a separate filter for each sub-channel is not required.

## Statistics, econometrics, and economics

When performing statistical analysis, independent variables that affect a particular dependent variable are said to be orthogonal if they are uncorrelated[4], since the covariance forms an inner product. In this case the same results are obtained for the effect of any of the independent variables upon the dependent variable, regardless of whether one models the variables' effects individually with simple regression or simultaneously with multiple regression. If correlation is present, the factors are not orthogonal and different results are obtained by the two methods. This usage arises from the fact that if centered (by subtracting the expected value (the mean)), uncorrelated variables are orthogonal in the geometric sense discussed above, both as observed data (i.e. vectors) and as random variables (i.e. density functions). One econometric formalism that is alternative to the maximum likelihood framework, the Generalized Method of Moments, relies on orthogonality conditions. In particular, the Ordinary Least Squares estimator may be easily derived from an orthogonality condition between dependent variables and model residuals.

## Taxonomy

In taxonomy, an orthogonal classification is one in which no item is a member of more than one group, that is, the classifications are mutually exclusive.

## Combinatorics

In combinatorics, two n×n Latin squares are said to be orthogonal if their superimposition yields all possible n2 combinations of entries.[5]

## Chemistry

In synthetic organic chemistry orthogonal protection is a strategy allowing the deprotection of functional groups independently of each other.

## System Reliability

In the field of system reliability orthogonal redundancy is that form of redundancy where the form of backup device or method is completely different from the prone to error device or method. The failure mode of an orthogonally redundant backup device or method does not intersect with and is completely different from the failure mode of the device or method in need of redundancy to safeguard the total system against catastrophic failure.

## Neuroscience

In neuroscience, a sensory map in the brain which has overlapping stimulus coding (e.g. location and quality) is called an orthogonal map.

## References

1. ^ Trefethen, Lloyd N. & Bau, David (1997). Numerical linear algebra. SIAM. p. 13. ISBN 9780898713619.
2. ^ "Lincoln Mark VIII speed-sensitive suspension (MPEG video)". Retrieved 2006-09-15.
3. ^ Null, Linda & Lobur, Julia (2006). The essentials of computer organization and architecture (2nd ed.). Jones & Bartlett Learning. p. 257. ISBN 9780763737696.
4. ^ Probability, Random Variables and Stochastic Processes. McGraw-Hill. 2002. pp. 211. ISBN 0-07-366011-6.
5. ^ Hedayat, A. et al (1999). Orthogonal arrays: theory and applications. Springer. p. 168. ISBN 9780387987668.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• orthogonality — ortogonalumas statusas T sritis fizika atitikmenys: angl. orthogonality vok. Orthogonalität, f rus. ортогональность, f pranc. orthogonalité, f …   Fizikos terminų žodynas

• orthogonality — noun see orthogonal …   New Collegiate Dictionary

• orthogonality — See orthogonal. * * * In mathematics, a property synonymous with perpendicularity when applied to vectors but applicable more generally to functions. Two elements of an inner product space are orthogonal when their inner product for vectors, the… …   Universalium

• orthogonality — noun The property of being orthogonal …   Wiktionary

• orthogonality — n. quality of having right angles, perpendicularity …   English contemporary dictionary

• orthogonality — or·thog·o·nal·i·ty …   English syllables

• orthogonality — noun 1. the relation of opposition between things at right angles • Syn: ↑perpendicularity, ↑orthogonal opposition • Derivationally related forms: ↑perpendicular (for: ↑perpendicularity) • …   Useful english dictionary

• Orthogonality (programming) — Orthogonality in a programming language means that a relatively small set of primitive constructs can be combined in a relatively small number of ways to build the control and data structures of the language. The term is most frequently used with …   Wikipedia

• Orthogonality (term rewriting) — Orthogonality as a property of term rewriting systems describes where the reduction rules of the system are all left linear, that is each variable occurs only once on the left hand side of each reduction rule, and there is no overlap between them …   Wikipedia

• Orthogonality principle — In statistics and signal processing, the orthogonality principle is a necessary and sufficient condition for the optimality of a Bayesian estimator. Loosely stated, the orthogonality principle says that the error vector of the optimal estimator… …   Wikipedia

### Share the article and excerpts

Do a right-click on the link above


text:
# Pattern recognition

(Redirected from Pattern analysis)
Jump to: navigation, search

In machine learning, pattern recognition is the assignment of a label to a given input value. In statistics, discriminant analysis was introduced for this same purpose in 1936. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes (for example, determine whether a given email is "spam" or "non-spam"). However, pattern recognition is a more general problem that encompasses other types of output as well. Other examples are regression, which assigns a real-valued output to each input; sequence labeling, which assigns a class to each member of a sequence of values (for example, part of speech tagging, which assigns a part of speech to each word in an input sentence); and parsing, which assigns a parse tree to an input sentence, describing the syntactic structure of the sentence.

Pattern recognition algorithms generally aim to provide a reasonable answer for all possible inputs and to perform "most likely" matching of the inputs, taking into account their statistical variation. This is opposed to pattern matching algorithms, which look for exact matches in the input with pre-existing patterns. A common example of a pattern-matching algorithm is regular expression matching, which looks for patterns of a given sort in textual data and is included in the search capabilities of many text editors and word processors. In contrast to pattern recognition, pattern matching is generally not considered a type of machine learning, although pattern-matching algorithms (especially with fairly general, carefully tailored patterns) can sometimes succeed in providing similar-quality output to the sort provided by pattern-recognition algorithms.

Pattern recognition is studied in many fields, including psychology, psychiatry, ethology, cognitive science, traffic flow and computer science.

## Overview

Pattern recognition is generally categorized according to the type of learning procedure used to generate the output value. Supervised learning assumes that a set of training data (the training set) has been provided, consisting of a set of instances that have been properly labeled by hand with the correct output. A learning procedure then generates a model that attempts to meet two sometimes conflicting objectives: Perform as well as possible on the training data, and generalize as well as possible to new data (usually, this means being as simple as possible, for some technical definition of "simple", in accordance with Occam's Razor, discussed below). Unsupervised learning, on the other hand, assumes training data that has not been hand-labeled, and attempts to find inherent patterns in the data that can then be used to determine the correct output value for new data instances. A combination of the two that has recently been explored is semi-supervised learning, which uses a combination of labeled and unlabeled data (typically a small set of labeled data combined with a large amount of unlabeled data). Note that in cases of unsupervised learning, there may be no training data at all to speak of; in other words, the data to be labeled is the training data.

Note that sometimes different terms are used to describe the corresponding supervised and unsupervised learning procedures for the same type of output. For example, the unsupervised equivalent of classification is normally known as clustering, based on the common perception of the task as involving no training data to speak of, and of grouping the input data into clusters based on some inherent similarity measure (e.g. the distance between instances, considered as vectors in a multi-dimensional vector space), rather than assigning each input instance into one of a set of pre-defined classes. Note also that in some fields, the terminology is different: For example, in community ecology, the term "classification" is used to refer to what is commonly known as "clustering".

The piece of input data for which an output value is generated is formally termed an instance. The instance is formally described by a vector of features, which together constitute a description of all known characteristics of the instance. (These feature vectors can be seen as defining points in an appropriate multidimensional space, and methods for manipulating vectors in vector spaces can be correspondingly applied to them, such as computing the dot product or the angle between two vectors.) Typically, features are either categorical (also known as nominal, i.e., consisting of one of a set of unordered items, such as a gender of "male" or "female", or a blood type of "A", "B", "AB" or "O"), ordinal (consisting of one of a set of ordered items, e.g., "large", "medium" or "small"), integer-valued (e.g., a count of the number of occurrences of a particular word in an email) or real-valued (e.g., a measurement of blood pressure). Often, categorical and ordinal data are grouped together; likewise for integer-valued and real-valued data. Furthermore, many algorithms work only in terms of categorical data and require that real-valued or integer-valued data be discretized into groups (e.g., less than 5, between 5 and 10, or greater than 10).

### Probabilistic classifiers

Many common pattern recognition algorithms are probabilistic in nature, in that they use statistical inference to find the best label for a given instance. Unlike other algorithms, which simply output a "best" label, often probabilistic algorithms also output a probability of the instance being described by the given label. In addition, many probabilistic algorithms output a list of the N-best labels with associated probabilities, for some value of N, instead of simply a single best label. When the number of possible labels is fairly small (e.g., in the case of classification), N may be set so that the probability of all possible labels is output. Probabilistic algorithms have many advantages over non-probabilistic algorithms:

• They output a confidence value associated with their choice. (Note that some other algorithms may also output confidence values, but in general, only for probabilistic algorithms is this value mathematically grounded in probability theory. Non-probabilistic confidence values can in general not be given any specific meaning, and only used to compare against other confidence values output by the same algorithm.)
• Correspondingly, they can abstain when the confidence of choosing any particular output is too low.
• Because of the probabilities output, probabilistic pattern-recognition algorithms can be more effectively incorporated into larger machine-learning tasks, in a way that partially or completely avoids the problem of error propagation.

### How many feature variables are important?

Feature selection algorithms, attempt to directly prune out redundant or irrelevant features. A general introduction to feature selection which summarizes approaches and challenges, has been given.[1] The complexity of feature-selection is, because of its non-monotonous character, an optimization problem where given a total of $n$ features the powerset consisting of all $2^n-1$ subsets of features need to be explored. The Branch-and-Bound algorithm [2] does reduce this complexity but is intractable for medium to large values of the number of available features $n$. For a large-scale comparison of feature-selection algorithms see .[3]

Techniques to transform the raw feature vectors (feature extraction) are sometimes used prior to application of the pattern-matching algorithm. For example, feature extraction algorithms attempt to reduce a large-dimensionality feature vector into a smaller-dimensionality vector that is easier to work with and encodes less redundancy, using mathematical techniques such as principal components analysis (PCA). The distinction between feature selection and feature extraction is that the resulting features after feature extraction has taken place are of a different sort than the original features and may not easily be interpretable, while the features left after feature selection are simply a subset of the original features.

## Problem statement (supervised version)

Formally, the problem of supervised pattern recognition can be stated as follows: Given an unknown function $g:\mathcal{X}\rightarrow\mathcal{Y}$ (the ground truth) that maps input instances $\boldsymbol{x} \in \mathcal{X}$ to output labels $y \in \mathcal{Y}$, along with training data $\mathbf{D} = \{(\boldsymbol{x}_1,y_1),\dots,(\boldsymbol{x}_n, y_n)\}$ assumed to represent accurate examples of the mapping, produce a function $h:\mathcal{X}\rightarrow\mathcal{Y}$ that approximates as closely as possible the correct mapping $g$. (For example, if the problem is filtering spam, then $\boldsymbol{x}_i$ is some representation of an email and $y$ is either "spam" or "non-spam"). In order for this to be a well-defined problem, "approximates as closely as possible" needs to be defined rigorously. In decision theory, this is defined by specifying a loss function that assigns a specific value to "loss" resulting from producing an incorrect label. The goal then is to minimize the expected loss, with the expectation taken over the probability distribution of $\mathcal{X}$. In practice, neither the distribution of $\mathcal{X}$ nor the ground truth function $g:\mathcal{X}\rightarrow\mathcal{Y}$ are known exactly, but can be computed only empirically by collecting a large number of samples of $\mathcal{X}$ and hand-labeling them using the correct value of $\mathcal{Y}$ (a time-consuming process, which is typically the limiting factor in the amount of data of this sort that can be collected). The particular loss function depends on the type of label being predicted. For example, in the case of classification, the simple zero-one loss function is often sufficient. This corresponds simply to assigning a loss of 1 to any incorrect labeling and implies that the optimal classifier minimizes the error rate on independent test data (i.e. counting up the fraction of instances that the learned function $h:\mathcal{X}\rightarrow\mathcal{Y}$ labels wrongly, which is equivalent to maximizing the number of correctly classified instances). The goal of the learning procedure is then to minimize the error rate (maximize the correctness) on a "typical" test set.

For a probabilistic pattern recognizer, the problem is instead to estimate the probability of each possible output label given a particular input instance, i.e., to estimate a function of the form

$p({\rm label}|\boldsymbol{x},\boldsymbol\theta) = f\left(\boldsymbol{x};\boldsymbol{\theta}\right)$

where the feature vector input is $\boldsymbol{x}$, and the function f is typically parameterized by some parameters $\boldsymbol{\theta}$.[4] In a discriminative approach to the problem, f is estimated directly. In a generative approach, however, the inverse probability $p({\boldsymbol{x}|\rm label})$ is instead estimated and combined with the prior probability $p({\rm label}|\boldsymbol\theta)$ using Bayes' rule, as follows:

$p({\rm label}|\boldsymbol{x},\boldsymbol\theta) = \frac{p({\boldsymbol{x}|\rm label}) p({\rm label|\boldsymbol\theta})}{\sum_{L \in \text{all labels}} p(\boldsymbol{x}|L) p(L|\boldsymbol\theta)}.$

When the labels are continuously distributed (e.g., in regression analysis), the denominator involves integration rather than summation:

$p({\rm label}|\boldsymbol{x},\boldsymbol\theta) = \frac{p({\boldsymbol{x}|\rm label}) p({\rm label|\boldsymbol\theta})}{\int_{L \in \text{all labels}} p(\boldsymbol{x}|L) p(L|\boldsymbol\theta) \operatorname{d}L}.$

The value of $\boldsymbol\theta$ is typically learned using maximum a posteriori (MAP) estimation. This finds the best value that simultaneously meets two conflicting objects: To perform as well as possible on the training data (smallest error-rate) and to find the simplest possible model. Essentially, this combines maximum likelihood estimation with a regularization procedure that favors simpler models over more complex models. In a Bayesian context, the regularization procedure can be viewed as placing a prior probability $p(\boldsymbol\theta)$ on different values of $\boldsymbol\theta$. Mathematically:

$\boldsymbol\theta^* = \arg \max_{\boldsymbol\theta} p(\boldsymbol\theta|\mathbf{D})$

where $\boldsymbol\theta^*$ is the value used for $\boldsymbol\theta$ in the subsequent evaluation procedure, and $p(\boldsymbol\theta|\mathbf{D})$, the posterior probability of $\boldsymbol\theta$, is given by

$p(\boldsymbol\theta|\mathbf{D}) = \left[\prod_{i=1}^n p(y_i|\boldsymbol{x}_i,\boldsymbol\theta) \right] p(\boldsymbol\theta).$

In the Bayesian approach to this problem, instead of choosing a single parameter vector $\boldsymbol{\theta}^*$, the probability of a given label for a new instance $\boldsymbol{x}$ is computed by integrating over all possible values of $\boldsymbol\theta$, weighted according to the posterior probability:

$p({\rm label}|\boldsymbol{x}) = \int p({\rm label}|\boldsymbol{x},\boldsymbol\theta)p(\boldsymbol{\theta}|\mathbf{D}) \operatorname{d}\boldsymbol{\theta}.$

### Frequentist or Bayesian approach to pattern recognition?

The first pattern classifier – the linear discriminant presented by Fisher – was developed in the Frequentist tradition. The frequentist approach entails that the model parameters are considered unknown, but objective. The parameters are then computed (estimated) from the collected data. For the linear discriminant, these parameters are precisely the mean vectors and the Covariance matrix. Also the probability of each class $p({\rm label}|\boldsymbol\theta)$ is estimated from the collected dataset. Note that the usage of ‘Bayes rule’ in a pattern classifier does not make the classification approach Bayesian.

Bayesian statistics has its origin in Greek philosophy where a distinction was already made between the ‘a priori’ and the ‘a posteriori’ knowledge. Later Kant defined his distinction between what is a priori known – before observation – and the empirical knowledge gained from observations. In a Bayesian pattern classifier, the class probabilities $p({\rm label}|\boldsymbol\theta)$ can be chosen by the user, which are then a priori. Moreover, experience quantified as a priori parameter values can be weighted with empirical observations – using e.g., the Beta- (conjugate prior) and Dirichlet-distributions. The Bayesian approach facilitates a seamless intermixing between expert knowledge in the form of subjective probabilities, and objective observations.

Probabilistic pattern classifiers can be used according to a frequentist or a Bayesian approach.

## Uses

Within medical science, pattern recognition is the basis for computer-aided diagnosis (CAD) systems. CAD describes a procedure that supports the doctor's interpretations and findings.

Other typical applications of pattern recognition techniques are automatic speech recognition, classification of text into several categories (e.g., spam/non-spam email messages), the automatic recognition of handwritten postal codes on postal envelopes, automatic recognition of images of human faces, or handwriting image extraction from medical forms.[5] The last two examples form the subtopic image analysis of pattern recognition that deals with digital images as input to pattern recognition systems.[6][7]

Optical character recognition is a classic example of the application of a pattern classifier, see OCR-example. The method of signing one's name was captured with stylus and overlay starting in 1990.[citation needed] The strokes, speed, relative min, relative max, acceleration and pressure is used to uniquely identify and confirm identity. Banks were first offered this technology, but were content to collect from the FDIC for any bank fraud and did not want to inconvenience customers..[citation needed]

• Artificial neural networks (neural net classifiers) and Deep Learning have many real-world applications in image processing, a few examples:
• identification and authentication: e.g., license plate recognition,[8] fingerprint analysis and face detection/verification;[9]
• medical diagnosis: e.g., screening for cervical cancer (Papnet)[10] or breast tumors;
• defence: various navigation and guidance systems, target recognition systems, etc.

For a discussion of the aforementioned applications of neural networks in image processing, see e.g.[11]

In psychology, pattern recognition, making sense of and identifying the objects we see is closely related to perception, which explains how the sensory inputs we receive are made meaningful. Pattern recognition can be thought of in two different ways: the first being template matching and the second being feature detection. A template is a pattern used to produce items of the same proportions. The template-matching hypothesis suggests that incoming stimuli are compared with templates in the long term memory. If there is a match, the stimulus is identified. Feature detection models, such as the Pandemonium system for classifying letters (Selfridge, 1959), suggest that the stimuli are broken down into their component parts for identification. For example, a capital E has three horizontal lines and one vertical line.[12]

## Algorithms

Algorithms for pattern recognition depend on the type of label output, on whether learning is supervised or unsupervised, and on whether the algorithm is statistical or non-statistical in nature. Statistical algorithms can further be categorized as generative or discriminative.

### Classification algorithms (supervised algorithms predicting categorical labels)

Parametric:[13]

Nonparametric:[14]

Unsupervised:

### Parsing algorithms (predicting tree structured labels)

Supervised and unsupervised:

Supervised (?):

Supervised:

Unsupervised:

Supervised:

Unsupervised:

## Which classifier to choose for a classification task?

This article contains an extensive list of statistical classifiers for supervised and unsupervised classification tasks, clustering and general regression prediction. When considering building a classifier e.g., for a software application, a number of different aspects influence the choice of the preferred classifier type to use.

Building or training a classifier is essentially statistical inference. This means that an attempt is made to identify stochastic (often unknown) relations between feature variables and the categories to be predicted. For example, the influence of increased cholesterol on the risk of a heart attack for a patient, within the next year. Which other variables besides the current cholesterol level determine this risk? The two categories to 'predict' by a classifier are 'heart attack likely', or 'heart attack unlikely'.

The theoretically optimal classifier is called the Bayes classifier. It minimizes the loss-function or risk as defined here. When all types of misclassifications are associated with equal losses (outcome A becomes B is as undesired as when outcome B becomes A), the Bayes classifier with the minimal error rate (on a test set) is the optimal one for the classification task. In general, it is unknown what is the optimal classifier type and true parameters $\boldsymbol{\theta}$. However, bounds on the optimal Bayes error rate have been derived. For, for example, the K-nearest neighbor classifier theoretical results are derived that bound the error rate, in relation to the optimal Bayes error rate.

In essence, building a classifier brings model selection with it. Feature selection – using only a subset of the available feature variables to predict the most likely categorical outcome – by itself entails model selection. Choosing among the extensive set of different classifiers makes model selection even more complex. A theoretical analysis of this search problem has been presented as the no free lunch theorem:[15] No particular classification algorithm is 'the best' for all problems. The pragmatic approach to this open problem is to combine prior knowledge of the classification task (e.g. distributional assumptions) with a search process where different types of classifiers are developed and their performance compared.

The search for the 'best' model that predicts observations and relations between these is a problem that was discovered already in ancient Greece. In medieval times, Occam's razor was formulated:

“plurality should not be posited without necessity”.

In this context, it means that if a simple classifier with only a few parameters (small $\boldsymbol{\theta}$) does the job as well as a much more complex classification algorithm, choose the simpler one. Only to add that the performance of a classifier is but one of the criteria to apply when choosing the best classification model. Distributional assumptions, insight provided into the discovered relations between variables, whether the classification algorithm can cope with missing feature variables, whether a change in class prior probability [16] can be incorporated, speed of the training algorithm, memory requirements, parallelization of the classification process, resemblance to the human perceptual system, and other aspects as well. In visual pattern recognition invariance to variations in color, rotation and scale are extra properties that need to be accounted for.

### Supervised classification

When choosing the most appropriate supervised classifier, the generally accepted heuristic is to:

1. Separate the available data, at random, into a training set and a test set. Use the test set only for the final performance comparison of the trained classifiers.
2. Experiment by training a number of classification algorithms, including parametric (discriminant analysis, multinomial classifier[17] ) and non-parametric algorithms (k-nearest neighbor, a support vector machine, a feed-forward neural network, a standard decision-tree algorithm).
3. Test distributional assumptions of the (continuous) feature-distributions per category. Are they Gaussian?
4. Which subset of feature variables contributes mostly to the discriminative performance of the classifier?
5. Are elaborate confidence intervals needed for the error-rates and class-predictions?[18]
6. White-box versus black-box considerations may render specific classifiers unsuited for the job.

## References

This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.

1. ^ Isabelle Guyon Clopinet, André Elisseeff (2003). An Introduction to Variable and Feature Selection. The Journal of Machine Learning Research, Vol. 3, 1157-1182. Link
2. ^ Iman Foroutan, Jack Sklansky (1987). "Feature Selection for Automatic Classification of Non-Gaussian Data". IEEE Transactions on Systems, Man and Cybernetics 17 (2): 187–198. doi:10.1109/TSMC.1987.4309029..
3. ^ Mineichi Kudo, Jack Sklansky (2000). "Comparison of algorithms that select features for pattern classifiers". Pattern Recognition 33 (1): 25–41. doi:10.1016/S0031-3203(99)00041-2..
4. ^ For linear discriminant analysis the parameter vector $\boldsymbol\theta$ consists of the two mean vectors $\boldsymbol\mu_1$ and $\boldsymbol\mu_2$ and the common covariance matrix $\boldsymbol\Sigma$.
5. ^ Milewski, Robert; Govindaraju, Venu (31 March 2008). "Binarization and cleanup of handwritten text from carbon copy medical form images". Pattern Recognition 41 (4): 1308–1315. doi:10.1016/j.patcog.2007.08.018.
6. ^ Richard O. Duda, Peter E. Hart, David G. Stork (2001) Pattern classification (2nd edition), Wiley, New York, ISBN 0-471-05669-3
7. ^ R. Brunelli, Template Matching Techniques in Computer Vision: Theory and Practice, Wiley, ISBN 978-0-470-51706-2, 2009
8. ^
9. ^ Neural Networks for Face Recognition Companion to Chapter 4 of the textbook Machine Learning.
10. ^
11. ^ Egmont-Petersen, M., de Ridder, D., Handels, H. (2002). "Image processing with neural networks - a review". Pattern Recognition 35 (10): 2279–2301. doi:10.1016/S0031-3203(01)00178-9.
12. ^ "A-level Psychology Attention Revision - Pattern recognition | S-cool, the revision website". S-cool.co.uk. Retrieved 2012-09-17.
13. ^ Assuming known distributional shape of feature distributions per class, such as the Gaussian shape.
14. ^ No distributional assumption regarding shape of feature distributions per class.
15. ^ David H. Wolpert (2001). The Supervised Learning No Free Lunch Theorems. Technical report MS-269-1, NASA Ames Research Center. Link
16. ^ Relative frequency of each class in the training and test sets.
17. ^ Ned Glick (1973) Sample-Based Multinomial Classification, Biometrics, Vol. 29, No. 2, pp. 241-256.
18. ^ Geoffrey J. McLachlan (2004) Discriminant Analysis and Statistical Pattern Recognition, Wiley Series in Probability and Statistics, New Jersey, ISBN 0-471-69115-1

## Further reading

• Fukunaga, Keinosuke (1990). Introduction to Statistical Pattern Recognition (2nd ed.). Boston: Academic Press. ISBN 0-12-269851-7.
• Bishop, Christopher (2006). Pattern Recognition and Machine Learning. Berlin: Springer. ISBN 0-387-31073-8.
• Koutroumbas, Konstantinos; Theodoridis, Sergios (2008). Pattern Recognition (4th ed.). Boston: Academic Press. ISBN 1-59749-272-8.
• Hornegger, Joachim; Paulus, Dietrich W. R. (1999). Applied Pattern Recognition: A Practical Introduction to Image and Speech Processing in C++ (2nd ed.). San Francisco: Morgan Kaufmann Publishers. ISBN 3-528-15558-2.
• Schuermann, Juergen (1996). Pattern Classification: A Unified View of Statistical and Neural Approaches. New York: Wiley. ISBN 0-471-13534-8.
• Godfried T. Toussaint, ed. (1988). Computational Morphology. Amsterdam: North-Holland Publishing Company.
• Kulikowski, Casimir A.; Weiss, Sholom M. (1991). Computer Systems That Learn: Classification and Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert Systems. Machine Learning. San Francisco: Morgan Kaufmann Publishers. ISBN 1-55860-065-5.
• Jain, Anil.K.; Duin, Robert.P.W.; Mao, Jianchang (2000). "Statistical pattern recognition: a review". IEEE Transactions on Pattern Analysis and Machine Intelligence 22 (1): 4–37. doi:10.1109/34.824819.
• An introductory tutorial to classifiers (introducing the basic terms, with numeric example)

format: plain


text:
# Substitution

## Substitution

It is often useful to make a substitution for a repeated expression in a quadratic equation. This makes the equation simpler and much easier to solve.

## Example

### Question

Solve for $$x$$: $$x^2 – 2x – \dfrac{3}{x^2 – 2x} = 2$$

### Determine the restrictions for $$x$$

The restrictions are the values for $$x$$ that would result in the denominator being equal to $$\text{0}$$, which would make the fraction undefined. Therefore $$x \ne 0$$ and $$x \ne 2$$.

### Substitute a single variable for the repeated expression

We notice that $$x^2 – 2x$$ is a repeated expression and we therefore let $$k = x^2 – 2x$$ so that the equation becomes

$k – \cfrac{3}{k} = 2$

### Determine the restrictions for $$k$$

The restrictions are the values for $$k$$ that would result in the denominator being equal to $$\text{0}$$, which would make the fraction undefined. Therefore $$k \ne 0$$.

### Solve for $$k$$

\begin{aligned} k – \cfrac{3}{k}&= 2 \\ k^2 – 3 &= 2k \\ k^2 – 2k – 3 &= 0 \\ (k + 1)(k – 3)&= 0 \\ \text{Therefore } k = -1 &\text{ or } k = 3 \end{aligned}

We check these two roots against the restrictions for $$k$$ and confirm that both are valid.

### Use values obtained for $$k$$ to solve for the original variable $$x$$

For $$k = -1$$ \begin{aligned} x^2 – 2x &= -1 \\ x^2 – 2x + 1 &= 0 \\ (x – 1)(x – 1) &= 0 \\ \text{Therefore } x &= 1 \end{aligned}

For $$k = 3$$ \begin{aligned} x^2 – 2x &= 3 \\ x^2 – 2x – 3 &= 0 \\ (x + 1)(x – 3)&= 0 \\ \text{Therefore } x = -1 &\text{ or } x = 3 \end{aligned}

We check these roots against the restrictions for $$x$$ and confirm that all three values are valid.

The roots of the equation are $$x = -1$$, $$x = 1$$ and $$x = 3$$.


text:
# How many millliters of 2.75 M H_2SO_4(aq) are needed to react completely with 47.5 g of BaO_2(s)?

Jul 7, 2016

$102 \setminus m L$

#### Explanation:

Write a balanced chemical equation for the reaction between barium peroxide and sulfuric acid.

$B a {O}_{2} + {H}_{2} S {O}_{4} \to B a S {O}_{4} + {H}_{2} {O}_{2}$

Use the stoichiometry of the equation to find the number of moles of sulfuric acid reacted.

$47.5 \setminus g \setminus B a {O}_{2} \times \frac{1 m o l . B a {O}_{2}}{169.33 \setminus g \setminus B a {O}_{2}} \times \frac{1 \setminus m o l . {H}_{2} S {O}_{4}}{1 \setminus m o l . \setminus B a {O}_{2}}$

$47.5 \cancel{\setminus g \setminus B a {O}_{2}} \times \frac{1 \textcolor{red}{\cancel{\setminus m o l . B a {O}_{2}}}}{169.33 \cancel{\setminus g \setminus B a {O}_{2}}} \times \frac{1 \setminus m o l . {H}_{2} S {O}_{4}}{1 \textcolor{red}{\cancel{\setminus m o l . \setminus B a {O}_{2}}}}$

$0.281 \setminus m o l . \setminus {H}_{2} S {O}_{4}$

Now, use the molarity formula to find the volume of the sulfuric acid used.

${C}_{M} = \frac{n}{V}$

Where:

${C}_{M} \text{ }$ is the molarity of the acid solution expressed in mol/L.

$V \text{ }$ is the volume of the acid solution expressed L.

$n \text{ }$ is the number of moles.

$V = \frac{n}{C} _ M$

$V = \frac{0.281 \setminus m o l .}{2.75 \setminus m o l . {L}^{-} 1}$

$V = 0.102 \setminus L$

$V = 102 \setminus m L$


text:
Feeds:
Posts

## Young diagrams, q-analogues, and one of my favorite proofs

I’ve decided to start blogging a little more about the algebraic combinatorics I’ve learned over the past year. In particular, I’d like to present one of my favorite proofs from Stanley’s Enumerative Combinatorics I.

The theory of Young tableaux is a great example of the richness of modern mathematics: although they can be defined in an elementary combinatorial fashion, interest in the theory is primarily driven (as I understand it) by their applications to representation theory and other fields of mathematics. The standard application is in describing the irreducible representations of the symmetric group in characteristic zero. I’ll be describing a more elementary aspect of the theory: the relationship between Young diagrams and $q$-binomial coefficients.

Young diagrams can be defined as a visual representations of partitions. A partition of $k$ is a weakly decreasing sequence $\lambda_1 \ge \lambda_2 \ge ... \ge \lambda_i$ such that $\lambda_1 + ... + \lambda_i = k$. Partitions uniquely describe cycle decompositions, hence conjugacy classes, of the symmetric group, which is a hint at the connection to representation theory. A Young diagram of the partition $\lambda$ consists of $i$ rows of boxes where the $j^{th}$ row has $\lambda_j$ boxes. Let $L(m, n)$ denote the poset of Young diagrams that fit into an $m \times n$ box, ordered by inclusion: equivalently, one can define the full Young lattice and define $L(m, n)$ to be the elements less than or equal to the $m \times n$ partition. (One can then define a standard Young tableau to be a chain in the Young lattice, but we will not need this notion.) One can easily check that the following is true.

Proposition: $|L(m, n)| = {m+n \choose m}$.

The rest of this post explains the $q$-analogue of this result.

If this counting result isn’t clear, note that a Young diagram uniquely describes a path from the bottom left to the top right corner of an $m \times n$ box, so this is a path-counting exercise.

Now, to specialize a counting result we usually introduce an auxiliary combinatorial parameter. There are many natural parameters associated to Young diagrams, such as size of the largest partition, but the one we want to investigate is perhaps the simplest: the number of boxes, which we’ll denote $\text{rank}(\lambda)$ since the number of boxes in a Young diagram describes its rank in the Young lattice, hence in $L(m, n)$. Our goal today is to compute the rank generating function

$\displaystyle R_q(m, n) = \sum_{\lambda \in L(m, n)} q^{\text{rank}(\lambda)}$.

Since $R_1(m, n) = {m+n \choose m}$, we should expect this function to behave like a generalization of the binomial coefficients. This hypothetical (for now) generalization we’ll refer to as a $q$-binomial coefficient. By taking “transposes” of Young diagrams (flipping them across the diagonal), it’s clear that $R_q(n, m) = R_q(m, n)$, so at least one property of the usual binomial coefficients carry through. What other properties do we want to prove? Well, the usual binomial coefficients are characterized by the identities

$\displaystyle {n \choose 0} = {n \choose n} = 1, {n+1 \choose k+1} = {n \choose k+1} + {n \choose k}.$

(The binomial coefficient ${n \choose k}, n < k$ is equal to zero both for the obvious combinatorial reason and so that the second identity is true without qualification.) The first identity is also true for $R_q$; the empty partition has rank zero. The second identity generalizes as follows.

Proposition: $R_q(m, n) = R_q(m, n-1) + q^n R_q(m-1, n)$.

The proof is more or less a generalization of the proof for the binomial coefficient identity. Consider the first (longest) row of a Young diagram in $L(m, n)$. If it is not of length $n$, then the Young diagram fits into a “thinner” box; that is, it is an element of $L(m, n-1)$. Otherwise, we can delete it to obtain a “shorter” box; that is, it corresponds to an element of $L(m-1, n)$. The factor of $q^n$ accounts for the deletion.

This last identity characterizes the $q$-binomial coefficients, which are defined as follows: define

$(n)_q = R_q(n-1, 1) = 1 + q + ... + q^{n-1}$.

Since $R_1(n-1, 1) = n$, we take this as our $q$-analogue of the number $n$. We then define the $q$-factorial

$(n)!_q = (n)_q (n-1)_q ... (1)_q$

and finally the $q$-binomial coefficient

$\displaystyle {m+n \choose n}_q = \frac{(m+n)!_q}{(m)!_q (n)!_q}$.

Although it is not obvious from the definition, the $q$-binomial coefficient is a polynomial with non-negative integer coefficients in $q$. I claim that

$\displaystyle {m+n \choose n}_q = {m+n-1 \choose n-1}_q + q^n {m+n-1 \choose n}_q$,

which then gives the desired identity $R_q(m, n) = {m+n \choose n}_q$ by induction over $m, n$. However, without a combinatorial interpretation of the $q$-binomial coefficient it is difficult to give a conceptual (read: bijective) proof of either this identity or the desired result, so it’s time to give one.

Proposition: If $q$ is a power of a prime, then ${n \choose k}_q$ is the number of $k$-dimensional subspaces of $\mathbb{F}_q^{n}$.

The philosophy here is that there is a strong formal similarity between the poset of subspaces of a vector space and the poset of subsets of a set; there is an even deeper philosophy that (pointed) sets are “really” vector spaces over a mysterious object called $\mathbb{F}_1$, the field with one element. Of course, there is no field with one element. You can find some interesting discussion of this idea at the Wikipedia article, week186, week259, the n-category cafe, the Secret Blogging Seminar, Neverending Books, …. In any case, isn’t it great that mathematicians can think about statements like “Coxeter groups are algebraic groups over $\mathbb{F}_1$before having a rigorous framework in which to prove them?

Anyway, this is all a little bit over my head, to say the least, but at least this particular proof is not too bad. Stanley’s proof is by a neat counting argument, but I’d like to take this opportunity to introduce another object. The group $GL_n(\mathbb{F}_q)$ consists of the group of invertible linear transformations on $\mathbb{F}_q^n$, i.e. invertible $n \times n$ matrices with entries in $\mathbb{F}_q$. We construct such a matrix column-by-column. The first column can be an arbitrary nonzero vector, so there are $q^n - 1$ possibilities. The next columns are arbitrary, except that they must be linearly independent of the previous choices, so there are $q^n - q$ possibilities for the second column, $q^n - q^2$ for the third, etc.; finally, there are $q^n - q^{n-1}$ possibilities for the last column. We find that

$|GL_n(\mathbb{F}_q)| = q^{ {n \choose 2} } (q - 1)^n (n)!_q$.

Of course, we should expect this; there is a sense in which $GL_n(\mathbb{F}_q)$ should reduce to the symmetric group $S_n$ in the limit $q \to 1$. (Actually, for reasons Stanley discusses, this analogy is not quite right.) $GL_n(\mathbb{F}_q)$ acts transitively on the set $\text{Gr}(n, k)$ of $k$-dimensional subspaces of $\mathbb{F}_q^n$, which is an example of a Grassmannian. It follows from the orbit-stabilizer theorem that

$\displaystyle |\text{Gr}(n, k)| = \frac{|GL_n(\mathbb{F}_q)|}{ |\text{Stab}(x)| }$

where $\text{Stab}(x)$ denotes the stabilizer subgroup of any particular $k$-dimensional subspace. Without loss of generality, we can compute the stabilizer subgroup of the space spanned by the first $k$ standard basis vectors, which is not too hard to describe: any stabilizer is block upper-triangular with a $k \times k$ block consisting of an element of $GL_k(\mathbb{F}_q)$ and $n - k$ columns chosen arbitrarily so that the resulting transformation has full rank. By the same argument as in the $GL_n(\mathbb{F}_q)$ case, the first block can be chosen in $(q^k - 1)...(q^k - q^{k-1})$ ways and the rest of the columns can be chosen in $(q^n - q^k)...(q^n - q^{n-1})$ ways. We find that

$\displaystyle |\text{Gr}(n, k)| = \frac{ q^{ {n \choose 2} } (n)!_q }{ q^{ {n \choose 2} } (k)!_q (n-k)!_q } = {n \choose k}_q$

as desired. For comparison’s sake, here is the corresponding $q = 1$ proof: $S_n$ acts transitively on the set of subsets of size $k$, and a stabilizer of a subset of size $k$ consists of a permutation in $S_k$ fixing the subset and a permutation in $S_{n-k}$ fixing its complement.

As interesting as this computation is, what does it have to do with Young diagrams? Remember that we’re trying to prove the following:

Theorem: $\displaystyle R_q(m, n) = {m+n \choose n}_q$.

So Young diagrams should appear as a convenient way to organize some “decomposition” of the Grassmannian. According to Stanley, this decomposition is called the “cellular decomposition” of the Grassmannian, and it touches on some deep stuff like Bruhat decomposition and Schubert cells. The actual decomposition, however, is wonderfully simple: it’s just row reduction!

More precisely, to every $n \times (m+n)$ matrix with entries in $\mathbb{F}_q$ of full rank one can associate its row space, which is an element of $\text{Gr}(m+n, n)$; this gives an equivalence relation on such matrices. The standard choice of representative of each equivalence class is a matrix in row-reduced echelon form. Stanley’s example of a typical such matrix for $n = 4, m = 3$ is

$\left[ \begin{array}{ccccccc} 1 & * & 0 & 0 & * & 0 & * \\ 0 & 0 & 1 & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \\ \end{array} \right]$

where the asterisks denote that the entry in that location is arbitrary. Such matrices are uniquely characterized by the locations of the first nonzero entry in each row, which must be a $1$, and the entries in asterisks. But as you can see, the asterisked entries have precisely the shape of a Young diagram in $L(m, n)$. (The columns without asterisks are the ones occupied by $1$s, of which there are $n$.) Constructing an rref matrix from a Young diagram is easy as well. I hope the placement of $1$s is clear from the example; if not, you can refer to the details in the second edition of the first chapter of EC1, which is freely available online.

In other words, $R_q(m, n)$ counts the number of ways to fill each box of a Young diagram in $L(m, n)$ with entries from $\mathbb{F}_q$. Such a filling uniquely determines a reduced row echelon form of a $n \times (m+n)$ matrix whose row space uniquely determines an element of $\text{Gr}(m+n, n)$. And the result follows. (More precisely, we have proven that two polynomials in one variable take the same value at an infinite number of integers, from which it follows that the two polynomials are identically equal.) As far as I can tell, the abstract theory of Grassmannians is a way to repeat this argument in a coordinate-free setting. I wish I knew more about it.

Questions

Sometimes there’s a way to interpret the $q$-binomial coefficients at non-integer values. The big example I’m thinking of is $q = - \phi^2$, for the following reason: let $F_n$ be the Fibonacci numbers and define the “fibotorial”

$\displaystyle (n)!_f = F_n F_{n-1} ... F_1$.

Then we have the curious identity

$\displaystyle {m+n \choose n}_{-\phi^2} = \frac{(m+n)!_f}{(m)!_f (n)!_f }$.

(This is just an application of Binet’s formula.) These functions are sometimes referred to as Fibonomial coefficients. So, what combinatorial can be attached to Fibonomial coefficients that relates them to Young diagrams? In what sense is it possible to construct an analogue of finite field theory for non-integer values of $q$?

### 10 Responses

1. I don’t know the answers to any of the questions you’ve asked, but I’ll mention a few things this post reminds me of.

(1) Young tableaux with at most n rows classify irreps of SL(n) (over complex numbers, or rather over any algebraically closed field of characteristic zero). So this provides one connection between GL(n) and the symmetric group.

(2) Over C, it makes sense to talk about “quantum SL(n)” for any non-zero number q. When q is not a root of unity, the representation theory of quantum SL(n) is almost exactly the same as the classical theory — only the Clebch-Gordon decomposition changes, because quantizing only changes the tensor product to be noncommutative (just like it makes multiplication noncommutative). But when q is a pth root of unity, the representation theory is very close to the representation theory “in characteristic p”, except that p need not be a prime.

So this is an answer to what the non-integer values of q should be like. Although it’s a little disappointing.

(3) There is another project, which is to understand SL(n) when n is not a positive integer. Some of this is known: when n is a negative integer there is a reasonable theory, called “supersymmetry” (because it’s better than symmetry). My adviser has suggested that I might look try to understand the non-integer story (and more generally try to classify “semisimple Lie categories” better than has been done). But I haven’t thought about it yet. And for me it would only be over characteristic 0, probably.

Point being, there are really two parameters: q and n. And then one can consider quantum groups in positive characteristic, when I guess there are three parameters, but I believe that these are very poorly understood. Indeed, one of the reasons to study quantum groups is that they give characteristic-zero approximations of positive-characteristic groups of Lie type, as I mentioned above.

• Theo-

(1) That connection of the symmetric group to GL(n) is rather different from the one gotten by looking at the field with one element. For one thing, it actually goes horribly wrong (or beautifully wrong, if you like Schur algebras) in characteristic p. Also, it’s wrong for other groups. It’s just one of those odd things about type A that the “Brauer algebra” of GL(n) is the group algebra of the symmetric group.

(3) I hope you’ve read this post http://sbseminar.wordpress.com/2009/02/25/a-warmup-gl_t-for-t-not-an-integer/

2. Qiaochu, have you looked at Bruce Sagan’s The Symmetric Group? I don’t really grok a lot of the things in this post, but it’s a wonderful introduction to Young tableaux and the representation theory of S_n.

• on June 12, 2009 at 4:56 pm | Reply Qiaochu Yuan

No, I haven’t, but thanks for the suggestion. There’s a lot of books I need to find at MIT once I get back…

3. […] the weight enumerator is equal to the -factorial […]

4. […] IV: The unreaso… on GILA III: The orbit-counting …GILA IV: The unreaso… on Young diagrams, q-analogues, a…fermatprime on Self-referential jokes in popu…Qiaochu Yuan on GILA I: Group actions and […]

5. […] In this post, I plan to discuss two (and a half) different applications of category theory to combinatorics. One is reasonably well-known; one is silly and (as far as I know) original, but hopefully gives some insight into something else that’s interested me ever since Qiaochu mentioned it. […]

6. […] I should check the previous post first. Ok, now I’m back to Qiaochu Yuan’s post “Young diagrams, q-analogues, and one of my favorite proofs“, which at first sight, seem accessible by me. Young […]

7. Great article! By the way, your count of the size of GL(n,q) seems to be off by a factor of (q-1)^n.

• Whoops. So it is. Thanks for the correction!