In mathematics, fuzzy measure theory considers generalized measures in which the additive property is replaced by the weaker property of monotonicity. The central concept of fuzzy measure theory is the fuzzy measure (also capacity, see ), which was introduced by Choquet in 1953 and independently defined by Sugeno in 1974 in the context of fuzzy integrals. There exists a number of different classes of fuzzy measures including plausibility/belief measures, possibility/necessity measures, and probability measures, which are a subset of classical measures. == Definitions == Let X {\displaystyle \mathbf {X} } be a universe of discourse, C {\displaystyle {\mathcal {C}}} be a class of subsets of X {\displaystyle \mathbf {X} } , and E , F ∈ C {\displaystyle E,F\in {\mathcal {C}}} . A function g : C → R {\displaystyle g:{\mathcal {C}}\to \mathbb {R} } where ∅ ∈ C ⇒ g ( ∅ ) = 0 {\displaystyle \emptyset \in {\mathcal {C}}\Rightarrow g(\emptyset )=0} E ⊆ F ⇒ g ( E ) ≤ g ( F ) {\displaystyle E\subseteq F\Rightarrow g(E)\leq g(F)} is called a fuzzy measure. A fuzzy measure is called normalized or regular if g ( X ) = 1 {\displaystyle g(\mathbf {X} )=1} . == Properties of fuzzy measures == A fuzzy measure is: additive if for any E , F ∈ C {\displaystyle E,F\in {\mathcal {C}}} such that E ∩ F = ∅ {\displaystyle E\cap F=\emptyset } , we have g ( E ∪ F ) = g ( E ) + g ( F ) . {\displaystyle g(E\cup F)=g(E)+g(F).} ; supermodular if for any E , F ∈ C {\displaystyle E,F\in {\mathcal {C}}} , we have g ( E ∪ F ) + g ( E ∩ F ) ≥ g ( E ) + g ( F ) {\displaystyle g(E\cup F)+g(E\cap F)\geq g(E)+g(F)} ; submodular if for any E , F ∈ C {\displaystyle E,F\in {\mathcal {C}}} , we have g ( E ∪ F ) + g ( E ∩ F ) ≤ g ( E ) + g ( F ) {\displaystyle g(E\cup F)+g(E\cap F)\leq g(E)+g(F)} ; superadditive if for any E , F ∈ C {\displaystyle E,F\in {\mathcal {C}}} such that E ∩ F = ∅ {\displaystyle E\cap F=\emptyset } , we have g ( E ∪ F ) ≥ g ( E ) + g ( F ) {\displaystyle g(E\cup F)\geq g(E)+g(F)} ; subadditive if for any E , F ∈ C {\displaystyle E,F\in {\mathcal {C}}} such that E ∩ F = ∅ {\displaystyle E\cap F=\emptyset } , we have g ( E ∪ F ) ≤ g ( E ) + g ( F ) {\displaystyle g(E\cup F)\leq g(E)+g(F)} ; symmetric if for any E , F ∈ C {\displaystyle E,F\in {\mathcal {C}}} , we have | E | = | F | {\displaystyle |E|=|F|} implies g ( E ) = g ( F ) {\displaystyle g(E)=g(F)} ; Boolean if for any E ∈ C {\displaystyle E\in {\mathcal {C}}} , we have g ( E ) = 0 {\displaystyle g(E)=0} or g ( E ) = 1 {\displaystyle g(E)=1} . Understanding the properties of fuzzy measures is useful in application. When a fuzzy measure is used to define a function such as the Sugeno integral or Choquet integral, these properties will be crucial in understanding the function's behavior. For instance, the Choquet integral with respect to an additive fuzzy measure reduces to the Lebesgue integral. In discrete cases, a symmetric fuzzy measure will result in the ordered weighted averaging (OWA) operator. Submodular fuzzy measures result in convex functions, while supermodular fuzzy measures result in concave functions when used to define a Choquet integral. == Möbius representation == Let g be a fuzzy measure. The Möbius representation of g is given by the set function M, where for every E , F ⊆ X {\displaystyle E,F\subseteq X} , M ( E ) = ∑ F ⊆ E ( − 1 ) | E ∖ F | g ( F ) . {\displaystyle M(E)=\sum _{F\subseteq E}(-1)^{|E\backslash F|}g(F).} The equivalent axioms in Möbius representation are: M ( ∅ ) = 0 {\displaystyle M(\emptyset )=0} . ∑ F ⊆ E | i ∈ F M ( F ) ≥ 0 {\displaystyle \sum _{F\subseteq E|i\in F}M(F)\geq 0} , for all E ⊆ X {\displaystyle E\subseteq \mathbf {X} } and all i ∈ E {\displaystyle i\in E} A fuzzy measure in Möbius representation M is called normalized if ∑ E ⊆ X M ( E ) = 1. {\displaystyle \sum _{E\subseteq \mathbf {X} }M(E)=1.} Möbius representation can be used to give an indication of which subsets of X interact with one another. For instance, an additive fuzzy measure has Möbius values all equal to zero except for singletons. The fuzzy measure g in standard representation can be recovered from the Möbius form using the Zeta transform: g ( E ) = ∑ F ⊆ E M ( F ) , ∀ E ⊆ X . {\displaystyle g(E)=\sum _{F\subseteq E}M(F),\forall E\subseteq \mathbf {X} .} == Simplification assumptions for fuzzy measures == Fuzzy measures are defined on a semiring of sets or monotone class, which may be as granular as the power set of X, and even in discrete cases the number of variables can be as large as 2|X|. For this reason, in the context of multi-criteria decision analysis and other disciplines, simplification assumptions on the fuzzy measure have been introduced so that it is less computationally expensive to determine and use. For instance, when it is assumed the fuzzy measure is additive, it will hold that g ( E ) = ∑ i ∈ E g ( { i } ) {\displaystyle g(E)=\sum _{i\in E}g(\{i\})} and the values of the fuzzy measure can be evaluated from the values on X. Similarly, a symmetric fuzzy measure is defined uniquely by |X| values. Two important fuzzy measures that can be used are the Sugeno- or λ {\displaystyle \lambda } -fuzzy measure and k-additive measures, introduced by Sugeno and Grabisch respectively. === Sugeno λ-measure === The Sugeno λ {\displaystyle \lambda } -measure is a special case of fuzzy measures defined iteratively. It has the following definition: ==== Definition ==== Let X = { x 1 , … , x n } {\displaystyle \mathbf {X} =\left\lbrace x_{1},\dots ,x_{n}\right\rbrace } be a finite set and let λ ∈ ( − 1 , + ∞ ) {\displaystyle \lambda \in (-1,+\infty )} . A Sugeno λ {\displaystyle \lambda } -measure is a function g : 2 X → [ 0 , 1 ] {\displaystyle g:2^{X}\to [0,1]} such that g ( X ) = 1 {\displaystyle g(X)=1} . if A , B ⊆ X {\displaystyle A,B\subseteq \mathbf {X} } (alternatively A , B ∈ 2 X {\displaystyle A,B\in 2^{\mathbf {X} }} ) with A ∩ B = ∅ {\displaystyle A\cap B=\emptyset } then g ( A ∪ B ) = g ( A ) + g ( B ) + λ g ( A ) g ( B ) {\displaystyle g(A\cup B)=g(A)+g(B)+\lambda g(A)g(B)} . As a convention, the value of g at a singleton set { x i } {\displaystyle \left\lbrace x_{i}\right\rbrace } is called a density and is denoted by g i = g ( { x i } ) {\displaystyle g_{i}=g(\left\lbrace x_{i}\right\rbrace )} . In addition, we have that λ {\displaystyle \lambda } satisfies the property λ + 1 = ∏ i = 1 n ( 1 + λ g i ) {\displaystyle \lambda +1=\prod _{i=1}^{n}(1+\lambda g_{i})} . Tahani and Keller as well as Wang and Klir have shown that once the densities are known, it is possible to use the previous polynomial to obtain the values of λ {\displaystyle \lambda } uniquely. === k-additive fuzzy measure === The k-additive fuzzy measure limits the interaction between the subsets E ⊆ X {\displaystyle E\subseteq X} to size | E | = k {\displaystyle |E|=k} . This drastically reduces the number of variables needed to define the fuzzy measure, and as k can be anything from 1 (in which case the fuzzy measure is additive) to X, it allows for a compromise between modelling ability and simplicity. ==== Definition ==== A discrete fuzzy measure g on a set X is called k-additive ( 1 ≤ k ≤ | X | {\displaystyle 1\leq k\leq |\mathbf {X} |} ) if its Möbius representation verifies M ( E ) = 0 {\displaystyle M(E)=0} , whenever | E | > k {\displaystyle |E|>k} for any E ⊆ X {\displaystyle E\subseteq \mathbf {X} } , and there exists a subset F with k elements such that M ( F ) ≠ 0 {\displaystyle M(F)\neq 0} . == Shapley and interaction indices == In game theory, the Shapley value or Shapley index is used to indicate the weight of a game. Shapley values can be calculated for fuzzy measures in order to give some indication of the importance of each singleton. In the case of additive fuzzy measures, the Shapley value will be the same as each singleton. For a given fuzzy measure g, and | X | = n {\displaystyle |\mathbf {X} |=n} , the Shapley index for every i , … , n ∈ X {\displaystyle i,\dots ,n\in X} is: ϕ ( i ) = ∑ E ⊆ X ∖ { i } ( n − | E | − 1 ) ! | E | ! n ! [ g ( E ∪ { i } ) − g ( E ) ] . {\displaystyle \phi (i)=\sum _{E\subseteq \mathbf {X} \backslash \{i\}}{\frac {(n-|E|-1)!|E|!}{n!}}[g(E\cup \{i\})-g(E)].} The Shapley value is the vector ϕ ( g ) = ( ψ ( 1 ) , … , ψ ( n ) ) . {\displaystyle \mathbf {\phi } (g)=(\psi (1),\dots ,\psi (n)).}
Verbot
The Verbot (short for Verbal-Robot) was a chatbot program and artificial intelligence software development kit (SDK) designed for Windows and web platforms. == Early beginning == The origin of verbot traces back to Michael Mauldin's research during his time as a graduate student and post-doctoral fellow at Carnegie Mellon University. The creative foundation also stems from Peter Plantec's work in personality psychology and art direction. === Historic outline === In 1994, Michael Loren Mauldin, founder of Lycos, Inc., developed a prototype chatbot, Julia, which competed in the internationally known Turing test, for the coveted Loebner Prize. The Turing test matches computer scientist judges against machines to see if they can distinguish a computer from a real human. Julia was refined and developed, and in 1997, Dr. Mauldin and Peter Plantec, a clinical psychologist and animator, formed Virtual Personalities, Inc. (now Conversive, Inc.) in order to create a virtual human interface that would incorporate real-time animation as well as speech and natural language processing. The initial release, a stand-alone virtual person called Sylvie, was beta-tested to the public. This release was well received, and finally, after several versions, the production release (deemed version 3) of the Verbally Enhanced Software Robot, or Verbot, was deployed in fall 2000. The grandfather of all Verbots is Rog-O-Matic, which, although it could not talk, could and did explore a virtual world. Julia has been active on the internet in one form or another since 1989. A close cousin of Julia is Lycos, a robot that explores the World Wide Web and answers questions about it. Sylvie was the first Verbot with a face and a voice. Sylvie was the first Virtual Human with advanced, flexible interfacing capability. === Beginnings === The Virtual Personalities story goes back to 1978, where Mauldin was attending Rice University. Fascinated by the idea of ELIZA, he proceeded to write a program called "PET" for his 8 kilobyte Commodore PET Computer. PET included simple induction as a way to post new information, for example: Subject: I like my friend (later) Subject: I like food. PET: I have heard that food is your friend. Meanwhile, Plantec was separately designing a personality for "Entity", a theoretical virtual human that would interact comfortably with humans without pretending to be one. At that time the technology was not advanced enough to realize Entity. Mauldin got so involved with this that he majored in Computer Science and minored in Linguistics. === Rogue === In the late seventies and early eighties, a popular computer game at universities was Rogue, an implementation of Dungeons and Dragons where the player would descend 26 levels in a randomly created dungeon, fighting monsters, gathering treasure, and searching for the elusive "Amulet of Yendor". Mauldin was one of four grad students who devoted a large amount of time to building a program called "Rog-O-Matic" capable of retrieving the amulet and emerging victorious from the dungeon. === TinyMUD === In 1989, when James Aspnes at Carnegie Mellon created the first TinyMUD (a descendant of MUD and AberMUD), Mauldin was one of the first to create a computer player that would explore the text-based world of TinyMUD. But his first robot, Gloria, gradually accreted more and more linguistic ability, to the point that it could pass the "unsuspecting" Turing test. In this version of the test, the human has no reason to suspect that one of the other occupants of the room is controlled by a computer, and so is more polite and asks fewer probing questions. The second generation of Mauldin's TinyMUD robots was Julia, created on Jan. 8, 1990. Julia slowly developed into a more and more capable conversational agent, and assumed useful duties in the TinyMUD world, including tour guide, information assistant, note-taker, and message-relayer. She could even play the card game hearts along with the other human players. In 1991, Julia attended the first Loebner Prize contest in Boston, Massachusetts. Although she only finished third, she was ranked by one judge as more human than one of the human confederates, winning a coveted certificate of humanness in the world's first restricted Turing test. Julia continued to log in to various TinyMUD's and TinyMucks for the next seven years, and chatted with hundreds of people a month over the internet. === Lycos === Julia's job was to explore a virtual world consisting of pages of textual descriptions, with links between them, and to construct an internal map of that world and answer questions about it (including path information such as the shortest route from one room to another, and matching information, such as which rooms contained a certain kind of object or textual description). It was therefore only a very short cognitive leap from Julia to Lycos, another robotic agent that explores a virtual world made of hyperlinked pages of text, and which answers questions about those pages. Sylvie was born and her abilities were expanded greatly to include interfacing with computers and control systems via her serial ports. === Sylvie === Sylvie was the first intelligent animated virtual human. She was designed both as a conversation agent and as a virtual human interface that would form a bridge between the two. She became more popular as a conversation agent, but her designers believe she serves as a prototype for future virtual human interface design that will help us all cope with the increasing complexity of technology. As an aside, Plantec noticed that a large number of Sylvies have been sold in Southeast Asia. Upon investigation, he found out that students had discovered a "test" mode that would allow them to type in English sentences that Sylvie would pronounce in her somewhat stylized English. == Ownership == In 1997, Dr. Mauldin and Peter Plantec formed Virtual Personalities, Inc. to create Natural Language Processing solutions for companies. In 2001 Virtual Personalities, Inc. became Conversive, Inc. to reflect the focus on providing Customer Service and Marketing to the Enterprise Market. In late 2012 Avaya, Inc. acquired Conversive's assets including Verbots. == Verbot versions == The Verbot 4 version was created and released in 2004. In 2005 Version 4.1 of the Verbot Software was released with many feature enhancements and bug fixes, including built-in support for embedding C# code in outputs and conditionals. In early 2006 Conversive launched Verbots Online allowing Verbot 4 users to upload their knowledge and show off their bots to the world. In 2009 Version 5 was released, completely free and fully featured. In early 2012 the last version of Verbot, 5.0.1.2, was released to the general public with support for Windows 7. Later in 2012 Verbots Online completely shut down. == Verbots today == Verbots.com, its community of users, and its forums no longer exist, but the software and users can still be found. There has been no active development since the early 2012 release of Verbot 5.0.1.2.
Randomized weighted majority algorithm
The randomized weighted majority algorithm is an algorithm in machine learning theory for aggregating expert predictions to a series of decision problems. It is a simple and effective method based on weighted voting which improves on the mistake bound of the deterministic weighted majority algorithm. In fact, in the limit, its prediction rate can be arbitrarily close to that of the best-predicting expert. == Example == Imagine that every morning before the stock market opens, we get a prediction from each of our "experts" about whether the stock market will go up or down. Our goal is to somehow combine this set of predictions into a single prediction that we then use to make a buy or sell decision for the day. The principal challenge is that we do not know which experts will give better or worse predictions. The RWMA gives us a way to do this combination such that our prediction record will be nearly as good as that of the single expert which, in hindsight, gave the most accurate predictions. == Motivation == In machine learning, the weighted majority algorithm (WMA) is a deterministic meta-learning algorithm for aggregating expert predictions. In pseudocode, the WMA is as follows: initialize all experts to weight 1 for each round: add each expert's weight to the option they predicted predict the option with the largest weighted sum multiply the weights of all experts who predicted wrongly by 1 2 {\displaystyle {\frac {1}{2}}} Suppose there are n {\displaystyle n} experts and the best expert makes m {\displaystyle m} mistakes. Then, the weighted majority algorithm (WMA) makes at most 2.4 ( log 2 n + m ) {\displaystyle 2.4(\log _{2}n+m)} mistakes. This bound is highly problematic in the case of highly error-prone experts. Suppose, for example, the best expert makes a mistake 20% of the time; that is, in N = 100 {\displaystyle N=100} rounds using n = 10 {\displaystyle n=10} experts, the best expert makes m = 20 {\displaystyle m=20} mistakes. Then, the weighted majority algorithm only guarantees an upper bound of 2.4 ( log 2 10 + 20 ) ≈ 56 {\displaystyle 2.4(\log _{2}10+20)\approx 56} mistakes. As this is a known limitation of the weighted majority algorithm, various strategies have been explored in order to improve the dependence on m {\displaystyle m} . In particular, we can do better by introducing randomization. Drawing inspiration from the Multiplicative Weights Update Method algorithm, we will probabilistically make predictions based on how the experts have performed in the past. Similarly to the WMA, every time an expert makes a wrong prediction, we will decrement their weight. Mirroring the MWUM, we will then use the weights to make a probability distribution over the actions and draw our action from this distribution (instead of deterministically picking the majority vote as the WMA does). == Randomized weighted majority algorithm (RWMA) == The randomized weighted majority algorithm is an attempt to improve the dependence of the mistake bound of the WMA on m {\displaystyle m} . Instead of predicting based on majority vote, the weights, are used as probabilities for choosing the experts in each round and are updated over time (hence the name randomized weighted majority). Precisely, if w i {\displaystyle w_{i}} is the weight of expert i {\displaystyle i} , let W = ∑ i w i {\displaystyle W=\sum _{i}w_{i}} . We will follow expert i {\displaystyle i} with probability w i W {\displaystyle {\frac {w_{i}}{W}}} . This results in the following algorithm: initialize all experts to weight 1. for each round: add all experts' weights together to obtain the total weight W {\displaystyle W} choose expert i {\displaystyle i} randomly with probability w i W {\displaystyle {\frac {w_{i}}{W}}} predict as the chosen expert predicts multiply the weights of all experts who predicted wrongly by β {\displaystyle \beta } The goal is to bound the worst-case expected number of mistakes, assuming that the adversary has to select one of the answers as correct before we make our coin toss. This is a reasonable assumption in, for instance, the stock market example provided above: the variance of a stock price should not depend on the opinions of experts that influence private buy or sell decisions, so we can treat the price change as if it was decided before the experts gave their recommendations for the day. The randomized algorithm is better in the worst case than the deterministic algorithm (weighted majority algorithm): in the latter, the worst case was when the weights were split 50/50. But in the randomized version, since the weights are used as probabilities, there would still be a 50/50 chance of getting it right. In addition, generalizing to multiplying the weights of the incorrect experts by β < 1 {\displaystyle \beta <1} instead of strictly 1 2 {\displaystyle {\frac {1}{2}}} allows us to trade off between dependence on m {\displaystyle m} and log 2 n {\displaystyle \log _{2}n} . This trade-off will be quantified in the analysis section. == Analysis == Let W t {\displaystyle W_{t}} denote the total weight of all experts at round t {\displaystyle t} . Also let F t {\displaystyle F_{t}} denote the fraction of weight placed on experts which predict the wrong answer at round t {\displaystyle t} . Finally, let N {\displaystyle N} be the total number of rounds in the process. By definition, F t {\displaystyle F_{t}} is the probability that the algorithm makes a mistake on round t {\displaystyle t} . It follows from the linearity of expectation that if M {\displaystyle M} denotes the total number of mistakes made during the entire process, E [ M ] = ∑ t = 1 N F t {\displaystyle E[M]=\sum _{t=1}^{N}F_{t}} . After round t {\displaystyle t} , the total weight is decreased by ( 1 − β ) F t W t {\displaystyle \ (1-\beta )F_{t}W_{t}} , since all weights corresponding to a wrong answer are multiplied by β < 1 {\displaystyle \ \beta <1} . It then follows that W t + 1 = W t ( 1 − ( 1 − β ) F t ) {\displaystyle W_{t+1}=W_{t}(1-(1-\beta )F_{t})} . By telescoping, since W 1 = n {\displaystyle W_{1}=n} , it follows that the total weight after the process concludes is On the other hand, suppose that m {\displaystyle \ m} is the number of mistakes made by the best-performing expert. At the end, this expert has weight β m {\displaystyle \ \beta ^{m}} . It follows, then, that the total weight is at least this much; in other words, W ≥ β m {\displaystyle \ W\geq \beta ^{m}} . This inequality and the above result imply Taking the natural logarithm of both sides yields Now, the Taylor series of the natural logarithm is In particular, it follows that ln ( 1 − ( 1 − β ) F t ) < − ( 1 − β ) F t {\displaystyle \ \ln(1-(1-\beta )F_{t})<-(1-\beta )F_{t}} . Thus, Recalling that E [ M ] = ∑ t = 1 N F t {\displaystyle E[M]=\sum _{t=1}^{N}F_{t}} and rearranging, it follows that Now, as β → 1 {\displaystyle \beta \to 1} from below, the first constant tends to 1 {\displaystyle 1} ; however, the second constant tends to + ∞ {\displaystyle +\infty } . To quantify this tradeoff, define ε = 1 − β {\displaystyle \varepsilon =1-\beta } to be the penalty associated with getting a prediction wrong. Then, again applying the Taylor series of the natural logarithm, It then follows that the mistake bound, for small ε {\displaystyle \varepsilon } , can be written in the form ( 1 + ϵ 2 + O ( ε 2 ) ) m + ϵ − 1 ln ( n ) {\displaystyle \ \left(1+{\frac {\epsilon }{2}}+O(\varepsilon ^{2})\right)m+\epsilon ^{-1}\ln(n)} . In English, the less that we penalize experts for their mistakes, the more that additional experts will lead to initial mistakes but the closer we get to capturing the predictive accuracy of the best expert as time goes on. In particular, given a sufficiently low value of ε {\displaystyle \varepsilon } and enough rounds, the randomized weighted majority algorithm can get arbitrarily close to the correct prediction rate of the best expert. In particular, as long as m {\displaystyle m} is sufficiently large compared to ln ( n ) {\displaystyle \ln(n)} (so that their ratio is sufficiently small), we can assign we can obtain an upper bound on the number of mistakes equal to This implies that the "regret bound" on the algorithm (that is, how much worse it performs than the best expert) is sublinear, at O ( m ln ( n ) ) {\displaystyle O({\sqrt {m\ln(n)}})} . == Revisiting the motivation == Recall that the motivation for the randomized weighted majority algorithm was given by an example where the best expert makes a mistake 20% of the time. Precisely, in N = 100 {\displaystyle N=100} rounds, with n = 10 {\displaystyle n=10} experts, where the best expert makes m = 20 {\displaystyle m=20} mistakes, the deterministic weighted majority algorithm only guarantees an upper bound of 2.4 ( log 2 10 + 20 ) ≈ 56 {\displaystyle 2.4(\log _{2}10+20)\approx 56} . By the analysis above, it follows that minimizing the number of worst-case expected mistakes is equivalent to minimizing the fun
Modes of variation
In statistics, modes of variation are a continuously indexed set of vectors or functions that are centered at a mean and are used to depict the variation in a population or sample. Typically, variation patterns in the data can be decomposed in descending order of eigenvalues with the directions represented by the corresponding eigenvectors or eigenfunctions. Modes of variation provide a visualization of this decomposition and an efficient description of variation around the mean. Both in principal component analysis (PCA) and in functional principal component analysis (FPCA), modes of variation play an important role in visualizing and describing the variation in the data contributed by each eigencomponent. In real-world applications, the eigencomponents and associated modes of variation aid to interpret complex data, especially in exploratory data analysis (EDA). == Formulation == Modes of variation are a natural extension of PCA and FPCA. === Modes of variation in PCA === If a random vector X = ( X 1 , X 2 , ⋯ , X p ) T {\displaystyle \mathbf {X} =(X_{1},X_{2},\cdots ,X_{p})^{T}} has the mean vector μ p {\displaystyle {\boldsymbol {\mu }}_{p}} , and the covariance matrix Σ p × p {\displaystyle \mathbf {\Sigma } _{p\times p}} with eigenvalues λ 1 ≥ λ 2 ≥ ⋯ ≥ λ p ≥ 0 {\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{p}\geq 0} and corresponding orthonormal eigenvectors e 1 , e 2 , ⋯ , e p {\displaystyle \mathbf {e} _{1},\mathbf {e} _{2},\cdots ,\mathbf {e} _{p}} , by eigendecomposition of a real symmetric matrix, the covariance matrix Σ {\displaystyle \mathbf {\Sigma } } can be decomposed as Σ = Q Λ Q T , {\displaystyle \mathbf {\Sigma } =\mathbf {Q} \mathbf {\Lambda } \mathbf {Q} ^{T},} where Q {\displaystyle \mathbf {Q} } is an orthogonal matrix whose columns are the eigenvectors of Σ {\displaystyle \mathbf {\Sigma } } , and Λ {\displaystyle \mathbf {\Lambda } } is a diagonal matrix whose entries are the eigenvalues of Σ {\displaystyle \mathbf {\Sigma } } . By the Karhunen–Loève expansion for random vectors, one can express the centered random vector in the eigenbasis X − μ = ∑ k = 1 p ξ k e k , {\displaystyle \mathbf {X} -{\boldsymbol {\mu }}=\sum _{k=1}^{p}\xi _{k}\mathbf {e} _{k},} where ξ k = e k T ( X − μ ) {\displaystyle \xi _{k}=\mathbf {e} _{k}^{T}(\mathbf {X} -{\boldsymbol {\mu }})} is the principal component associated with the k {\displaystyle k} -th eigenvector e k {\displaystyle \mathbf {e} _{k}} , with the properties E ( ξ k ) = 0 , Var ( ξ k ) = λ k , {\displaystyle \operatorname {E} (\xi _{k})=0,\operatorname {Var} (\xi _{k})=\lambda _{k},} and E ( ξ k ξ l ) = 0 for l ≠ k . {\displaystyle \operatorname {E} (\xi _{k}\xi _{l})=0\ {\text{for}}\ l\neq k.} Then the k {\displaystyle k} -th mode of variation of X {\displaystyle \mathbf {X} } is the set of vectors, indexed by α {\displaystyle \alpha } , m k , α = μ ± α λ k e k , α ∈ [ − A , A ] , {\displaystyle \mathbf {m} _{k,\alpha }={\boldsymbol {\mu }}\pm \alpha {\sqrt {\lambda _{k}}}\mathbf {e} _{k},\alpha \in [-A,A],} where A {\displaystyle A} is typically selected as 2 or 3 {\displaystyle 2\ {\text{or}}\ 3} . === Modes of variation in FPCA === For a square-integrable random function X ( t ) , t ∈ T ⊂ R p {\displaystyle X(t),t\in {\mathcal {T}}\subset R^{p}} , where typically p = 1 {\displaystyle p=1} and T {\displaystyle {\mathcal {T}}} is an interval, denote the mean function by μ ( t ) = E ( X ( t ) ) {\displaystyle \mu (t)=\operatorname {E} (X(t))} , and the covariance function by G ( s , t ) = Cov ( X ( s ) , X ( t ) ) = ∑ k = 1 ∞ λ k φ k ( s ) φ k ( t ) , {\displaystyle G(s,t)=\operatorname {Cov} (X(s),X(t))=\sum _{k=1}^{\infty }\lambda _{k}\varphi _{k}(s)\varphi _{k}(t),} where λ 1 ≥ λ 2 ≥ ⋯ ≥ 0 {\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq 0} are the eigenvalues and { φ 1 , φ 2 , ⋯ } {\displaystyle \{\varphi _{1},\varphi _{2},\cdots \}} are the orthonormal eigenfunctions of the linear Hilbert–Schmidt operator G : L 2 ( T ) → L 2 ( T ) , G ( f ) = ∫ T G ( s , t ) f ( s ) d s . {\displaystyle G:L^{2}({\mathcal {T}})\rightarrow L^{2}({\mathcal {T}}),\,G(f)=\int _{\mathcal {T}}G(s,t)f(s)ds.} By the Karhunen–Loève theorem, one can express the centered function in the eigenbasis, X ( t ) − μ ( t ) = ∑ k = 1 ∞ ξ k φ k ( t ) , {\displaystyle X(t)-\mu (t)=\sum _{k=1}^{\infty }\xi _{k}\varphi _{k}(t),} where ξ k = ∫ T ( X ( t ) − μ ( t ) ) φ k ( t ) d t {\displaystyle \xi _{k}=\int _{\mathcal {T}}(X(t)-\mu (t))\varphi _{k}(t)dt} is the k {\displaystyle k} -th principal component with the properties E ( ξ k ) = 0 , Var ( ξ k ) = λ k , {\displaystyle \operatorname {E} (\xi _{k})=0,\operatorname {Var} (\xi _{k})=\lambda _{k},} and E ( ξ k ξ l ) = 0 for l ≠ k . {\displaystyle \operatorname {E} (\xi _{k}\xi _{l})=0{\text{ for }}l\neq k.} Then the k {\displaystyle k} -th mode of variation of X ( t ) {\displaystyle X(t)} is the set of functions, indexed by α {\displaystyle \alpha } , m k , α ( t ) = μ ( t ) ± α λ k φ k ( t ) , t ∈ T , α ∈ [ − A , A ] {\displaystyle m_{k,\alpha }(t)=\mu (t)\pm \alpha {\sqrt {\lambda _{k}}}\varphi _{k}(t),\ t\in {\mathcal {T}},\ \alpha \in [-A,A]} that are viewed simultaneously over the range of α {\displaystyle \alpha } , usually for A = 2 or 3 {\displaystyle A=2\ {\text{or}}\ 3} . == Estimation == The formulation above is derived from properties of the population. Estimation is needed in real-world applications. The key idea is to estimate mean and covariance. === Modes of variation in PCA === Suppose the data x 1 , x 2 , ⋯ , x n {\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\cdots ,\mathbf {x} _{n}} represent n {\displaystyle n} independent drawings from some p {\displaystyle p} -dimensional population X {\displaystyle \mathbf {X} } with mean vector μ {\displaystyle {\boldsymbol {\mu }}} and covariance matrix Σ {\displaystyle \mathbf {\Sigma } } . These data yield the sample mean vector x ¯ {\displaystyle {\overline {\mathbf {x} }}} , and the sample covariance matrix S {\displaystyle \mathbf {S} } with eigenvalue-eigenvector pairs ( λ ^ 1 , e ^ 1 ) , ( λ ^ 2 , e ^ 2 ) , ⋯ , ( λ ^ p , e ^ p ) {\displaystyle ({\hat {\lambda }}_{1},{\hat {\mathbf {e} }}_{1}),({\hat {\lambda }}_{2},{\hat {\mathbf {e} }}_{2}),\cdots ,({\hat {\lambda }}_{p},{\hat {\mathbf {e} }}_{p})} . Then the k {\displaystyle k} -th mode of variation of X {\displaystyle \mathbf {X} } can be estimated by m ^ k , α = x ¯ ± α λ ^ k e ^ k , α ∈ [ − A , A ] . {\displaystyle {\hat {\mathbf {m} }}_{k,\alpha }={\overline {\mathbf {x} }}\pm \alpha {\sqrt {{\hat {\lambda }}_{k}}}{\hat {\mathbf {e} }}_{k},\alpha \in [-A,A].} === Modes of variation in FPCA === Consider n {\displaystyle n} realizations X 1 ( t ) , X 2 ( t ) , ⋯ , X n ( t ) {\displaystyle X_{1}(t),X_{2}(t),\cdots ,X_{n}(t)} of a square-integrable random function X ( t ) , t ∈ T {\displaystyle X(t),t\in {\mathcal {T}}} with the mean function μ ( t ) = E ( X ( t ) ) {\displaystyle \mu (t)=\operatorname {E} (X(t))} and the covariance function G ( s , t ) = Cov ( X ( s ) , X ( t ) ) {\displaystyle G(s,t)=\operatorname {Cov} (X(s),X(t))} . Functional principal component analysis provides methods for the estimation of μ ( t ) {\displaystyle \mu (t)} and G ( s , t ) {\displaystyle G(s,t)} in detail, often involving point wise estimate and interpolation. Substituting estimates for the unknown quantities, the k {\displaystyle k} -th mode of variation of X ( t ) {\displaystyle X(t)} can be estimated by m ^ k , α ( t ) = μ ^ ( t ) ± α λ ^ k φ ^ k ( t ) , t ∈ T , α ∈ [ − A , A ] . {\displaystyle {\hat {m}}_{k,\alpha }(t)={\hat {\mu }}(t)\pm \alpha {\sqrt {{\hat {\lambda }}_{k}}}{\hat {\varphi }}_{k}(t),t\in {\mathcal {T}},\alpha \in [-A,A].} == Applications == Modes of variation are useful to visualize and describe the variation patterns in the data sorted by the eigenvalues. In real-world applications, modes of variation associated with eigencomponents allow to interpret complex data, such as the evolution of function traits and other infinite-dimensional data. To illustrate how modes of variation work in practice, two examples are shown in the graphs to the right, which display the first two modes of variation. The solid curve represents the sample mean function. The dashed, dot-dashed, and dotted curves correspond to modes of variation with α = ± 1 , ± 2 , {\displaystyle \alpha =\pm 1,\pm 2,} and ± 3 {\displaystyle \pm 3} , respectively. The first graph displays the first two modes of variation of female mortality data from 41 countries in 2003. The object of interest is log hazard function between ages 0 and 100 years. The first mode of variation suggests that the variation of female mortality is smaller for ages around 0 or 100, and larger for ages around 25. An appropriate and intuitive interpretation is that mortality around 25 is driven by accidental death, while around 0 or 100, mortality is related to congenital disease or natural death. Compared to female mortality
C4.5 algorithm
C4.5 is an algorithm used to generate a decision tree developed by Ross Quinlan. C4.5 is an extension of Quinlan's earlier ID3 algorithm. The decision trees generated by C4.5 can be used for classification, and for this reason, C4.5 is often referred to as a statistical classifier. In 2011, authors of the Weka machine learning software described the C4.5 algorithm as "a landmark decision tree program that is probably the machine learning workhorse most widely used in practice to date". It became quite popular after ranking #1 in the Top 10 Algorithms in Data Mining pre-eminent paper published by Springer LNCS in 2008. == Algorithm == C4.5 builds decision trees from a set of training data in the same way as ID3, using the concept of information entropy. The training data is a set S = s 1 , s 2 , . . . {\displaystyle S={s_{1},s_{2},...}} of already classified samples. Each sample s i {\displaystyle s_{i}} consists of a p-dimensional vector ( x 1 , i , x 2 , i , . . . , x p , i ) {\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})} , where the x j {\displaystyle x_{j}} represent attribute values or features of the sample, as well as the class in which s i {\displaystyle s_{i}} falls. At each node of the tree, C4.5 chooses the attribute of the data that most effectively splits its set of samples into subsets enriched in one class or the other. The splitting criterion is the normalized information gain (difference in entropy). The attribute with the highest normalized information gain is chosen to make the decision. The C4.5 algorithm then recurses on the partitioned sublists. This algorithm has a few base cases. All the samples in the list belong to the same class. When this happens, it simply creates a leaf node for the decision tree saying to choose that class. None of the features provide any information gain. In this case, C4.5 creates a decision node higher up the tree using the expected value of the class. Instance of previously unseen class encountered. Again, C4.5 creates a decision node higher up the tree using the expected value. === Pseudocode === In pseudocode, the general algorithm for building decision trees is: Check for the above base cases. For each attribute a, find the normalized information gain ratio from splitting on a. Let a_best be the attribute with the highest normalized information gain. Create a decision node that splits on a_best. Recurse on the sublists obtained by splitting on a_best, and add those nodes as children of node. == Improvements from ID3 algorithm == C4.5 made a number of improvements to ID3. Some of these are: Handling both continuous and discrete attributes: In order to handle continuous attributes, C4.5 creates a threshold and then splits the list into those whose attribute value is above the threshold and those that are less than or equal to it. Handling training data with missing attribute values: C4.5 allows attribute values to be marked as missing. Missing attribute values are simply not used in gain and entropy calculations. Handling attributes with differing costs. Pruning trees after creation: C4.5 goes back through the tree once it's been created and attempts to remove branches that do not help by replacing them with leaf nodes. == Improvements in C5.0/See5 algorithm == Quinlan went on to create C5.0 and See5 (C5.0 for Unix/Linux, See5 for Windows) which he markets commercially. C5.0 offers a number of improvements on C4.5. Some of these are: Speed - C5.0 is significantly faster than C4.5 (several orders of magnitude) Memory usage - C5.0 is more memory efficient than C4.5 Smaller decision trees - C5.0 gets similar results to C4.5 with considerably smaller decision trees. Support for boosting - Boosting improves the trees and gives them more accuracy. Weighting - C5.0 allows you to weight different cases and misclassification types. Winnowing - a C5.0 option automatically winnows the attributes to remove those that may be unhelpful. Source for a single-threaded Linux version of C5.0 is available under the GNU General Public License (GPL).
Scrolling
In computer displays, filmmaking, television production, video games and other kinetic displays, scrolling is sliding text, images or video across a monitor or display, vertically or horizontally. "Scrolling," as such, does not change the layout of the text or pictures but moves (pans or tilts) the user's view across what is apparently a larger image that is not wholly seen. A common television and movie special effect is to scroll credits, while leaving the background stationary. Scrolling may take place completely without user intervention (as in film credits) or, on an interactive device, be triggered by touchscreen or a keypress and continue without further intervention until a further user action, or be entirely controlled by input devices. Scrolling may take place in discrete increments (perhaps one or a few lines of text at a time), or continuously (smooth scrolling). Frame rate is the speed at which an entire image is redisplayed. It is related to scrolling in that changes to text and image position can only happen as often as the image can be redisplayed. When frame rate is a limiting factor, one smooth scrolling technique is to blur images during movement that would otherwise appear to "jump". == Computing == === Implementation === Scrolling is often carried out on a computer by the CPU (software scrolling) or by a graphics processor. Some systems feature hardware scrolling, where an image may be offset as it is displayed, without any frame buffer manipulation (see also hardware windowing). This was especially common in 8 and 16bit video game consoles. === UI paradigms === In a WIMP-style graphical user interface (GUI), user-controlled scrolling is carried out by manipulating a scrollbar with a mouse, or using keyboard shortcuts, often the arrow keys. Scrolling is often supported by text user interfaces and command line interfaces. Older computer terminals changed the entire contents of the display one screenful ("page") at a time; this paging mode requires fewer resources than scrolling. Scrolling displays often also support page mode. Typically certain keys or key combinations page up or down; on PC-compatible keyboards the page up and page down keys or the space bar are used; earlier computers often used control key combinations. Some computer mice have a scroll wheel, which scrolls the display, often vertically, when rolled; others have scroll balls or tilt wheels which allow both vertical and horizontal scrolling. Some software supports other ways of scrolling. Adobe Reader has a mode identified by a small hand icon ("hand tool") on the document, which can then be dragged by clicking on it and moving the mouse as if sliding a large sheet of paper. When this feature is implemented on a touchscreen it is called kinetic scrolling. Touch-screens often use inertial scrolling, in which the scrolling motion of an object continues in a decaying fashion after release of the touch, simulating the appearance of an object with inertia. An early implementation of such behavior was in the "Star7" PDA of Sun Microsystems ca. 1991–1992. Scrolling can be controlled in other software-dependent ways by a PC mouse. Some scroll wheels can be pressed down, functioning like a button. Depending on the software, this allows both horizontal and vertical scrolling by dragging in the direction desired; when the mouse is moved to the original position, scrolling stops. A few scroll wheels can also be tilted, scrolling horizontally in one direction until released. On touchscreen devices, scrolling is a multi-touch gesture, done by swiping a finger on the screen vertically in the direction opposite to where the user wants to scroll to. If any content is too wide to fit on a display, horizontal scrolling is required to view all of it. In applications such as graphics and spreadsheets there is often more content than can fit either the width or the height of the screen at a comfortable scale, and scrolling in both directions is necessary. === Infinite scrolling === In contrast to material divided into discrete pages, the web design approach of infinite scrolling dynamically adds new material to the user display, leading to a continuous, apparently bottomless or endless scrolling experience. === Text === In languages written horizontally, such as most Western languages, text documents longer than will fit on the screen are often displayed wrapped and sized to fit the screen width, and scrolled vertically to bring desired content into view. It is possible to display lines too long to fit the display without wrapping, scrolling horizontally to view each entire line. However, this requires inconvenient constant line-by-line scrolling, while vertical scrolling is only needed after reading a full screenful. Software such as word processors and web browsers normally uses word-wrapping to display as many words in a single line as will fit the width of the screen or window or, for text organised in columns, each column. === Demos === Scrolling texts, also referred to as scrolltexts or scrollers, played an important part in the birth of the computer demo culture. The software crackers often used their deep knowledge of computer platforms to transform the information that accompanied their releases into crack intros. The sole role of these intros was to scroll the text on the screen in an impressive way. == Film and television == Scrolling is commonly used to display the credits at the end of films and television programs. Scrolling is often used in the form of a news ticker towards the bottom of the picture for content such as television news, scrolling sideways across the screen, delivering short-form content. In the dynamic layout of kinetic typography, scrolling typography can scroll across the flat screen, or can appear to recede or advance. An iconic example is the Star Wars opening crawl inspired by the Flash Gordon serials. == Video games == In computer and video games, scrolling of a playing field allows the player to control an object in a large contiguous area. Early examples of this method include Taito's 1974 vertical-scrolling racing video game Speed Race, Sega's 1976 forward-scrolling racing games Moto-Cross (Fonz) and Road Race, and Super Bug. Previously the flip-screen method was used to indicate moving backgrounds. The Namco Galaxian arcade system board introduced with Galaxian in 1979 pioneered a sprite system that animated pre-loaded sprites over a scrolling background, which became the basis for Nintendo's Radar Scope and Donkey Kong arcade hardware and home consoles such as the Nintendo Entertainment System. Parallax scrolling, which was first featured in Moon Patrol, involves several semi-transparent layers (called playfields), which scroll on top of each other at varying rates in order to give an early pseudo-3D illusion of depth. Belt scrolling is a method used in side-scrolling beat 'em up games with a downward camera angle where players can move up and down in addition to left and right. == Studies == A 1993 article by George Fitzmaurice studied spatially aware palmtop computers. These devices had a 3D sensor, and moving the device caused the contents to move as if the contents were fixed in place. This interaction could be referred to as “moving to scroll.” Also, if the user moved the device away from their body, they would zoom in; conversely, the device would zoom out if the user pulled the device closer to them. Smartphone cameras and “optical flow” image analysis utilize this technique nowadays. A 1996 research paper by Jun Rekimoto analyzed tilting operations as scrolling techniques on small screen interfaces. Users could not only tilt to scroll, but also tilt to select menu items. These techniques proved especially useful for field workers, since they only needed to hold and control the device with one hand. A study from 2013 by Selina Sharmin, Oleg Špakov, and Kari-Jouko Räihä explored the action of reading text on a screen while the text auto-scrolls based on the user's eye tracking patterns. The control group simply read text on a screen and manually scrolled. The study found that participants preferred to read primarily at the top of the screen, so the screen scrolled down whenever participants’ eyes began to look toward the bottom of the screen. This auto-scrolling caused no statistically significant difference in reading speed or performance. An undated study occurring during or after 2010 by Dede Frederick, James Mohler, Mihaela Vorvoreanu, and Ronald Glotzbach noted that parallax scrolling "may cause certain people to experience nausea."
Structured kNN
Structured k-nearest neighbours (SkNN) is a machine learning algorithm that generalizes k-nearest neighbors (k-NN). k-NN supports binary classification, multiclass classification, and regression, whereas SkNN allows training of a classifier for general structured output. For instance, a data sample might be a natural language sentence, and the output could be an annotated parse tree. Training a classifier consists of showing many instances of ground truth sample-output pairs. After training, the SkNN model is able to predict the corresponding output for new, unseen sample instances; that is, given a natural language sentence, the classifier can produce the most likely parse tree. == Training == As a training set, SkNN accepts sequences of elements with class labels. The type of element does not matter; the only requirement is a defined metric function that gives a distance between each pair of elements of a set. SkNN is based on idea of creating a graph, with each node representing a class label. There is an edge between a pair of nodes if there is a sequence of two elements in the training set with corresponding classes. The first step of SkNN training is the construction of such a graph from training sequences. There are two special nodes in the graph corresponding to sentence beginnings and ends: if a sequence starts with class C, the edge between node START and node C should be created. Like regular k-NN, the second part of SkNN training consists of storing the elements of a training sequence in a certain way. Each element of the training sequences is stored in the node related to the class of the previous element in the sequence. Every first element is stored in the START node. == Inference == Labelling input sequences by SkNN consists of finding the sequence of transitions in the graph, starting from node START. Each transition corresponds to a single element of the input sequence. As a result, the label of each element is determined as the target node label of the transition. The cost of the path is defined as the sum of all transitions, with the cost of transition from node A to node B being the distance from the current input sequence element to the nearest element of class B, stored in node A. Determining an optimal path may be performed using a modified Viterbi algorithm (where the sum of the distances is minimized, unlike the original algorithm which maximizes the product of probabilities).