text:
Complex behaviour emerges from interactions between objects produced by different generating mechanisms. Yet to decode their causal origin(s) from observations remains one of the most fundamental challenges in science. Here we introduce a universal, unsupervised and parameter-free model-oriented approach, based on the seminal concept and the first principles of algorithmic probability, to decompose an observation into its most likely algorithmic generative models. Our approach uses a perturbation-based causal calculus to infer model representations. We demonstrate its ability to deconvolve interacting mechanisms regardless of whether the resultant objects are bit strings, space–time evolution diagrams, images or networks. Although this is mostly a conceptual contribution and an algorithmic framework, we also provide numerical evidence evaluating the ability of our methods to extract models from data produced by discrete dynamical systems such as cellular automata and complex networks. We think that these separating techniques can contribute to tackling the challenge of causation, thus complementing statistically oriented approaches.

A preprint version of the article is available at ArXiv.

We have introduced a suite of algorithms based on mathematical notions acknowledged to fully characterize the concept of randomness1 . These algorithms enable us to study the algorithmic information dynamics of evolving systems, and to devise methods of reducing the dimensions of data2 grounded on the first mathematical principles of randomness. Deconvolution of data by generative sources can be viewed as the ultimate goal of some supervised and unsupervised machine learning algorithms. This is a hard problem. Unsurprisingly, these approaches often lose sight of their goal of causal decomposition and instead seek to identify shared features of data, construed as evidence of their possible common origin. For example, in signal processing, popular methods such as k-means3 or k-medoids4 define heuristics based on the minimization of distance among data points according to a specific metric. Other popular methods, such as support vector clustering5 and some traditional machine learning techniques, draw on probability distributions, regression and correlation techniques to achieve linear separation and produce different groups. For instance, most deep neural networks use gradient-based learning techniques to statistically map elements to a differentiable landscape. Another type of separation method relies on graph-theoretic properties. Methods that separate graphs by indices such as edge betweenness or the frequency of over-representation of certain subgraphs (for example, see ref. 6), or by more sophisticated criteria such as shared graph spectral features, fall into this category7,8,9,10. All these methods make the assumption that, because the objects they study share statistical, topological or algebraic features11, such objects may be generated by the same means or from the same sources.

Despite their wide use and popularity, current approaches to causation are still both fundamentally and pragmatically dependent on linear regression and correlation tests, ranging from Granger’s causality12 to transfer entropy13 and Pearl’s interventionist do-calculus14. Nevertheless, considerable progress has been made in these areas, in particular through the introduction of Pearl’s interventionist do-calculus14, even when they are limited by their high dependency on probability distributions.

Our approach contributes to the discussion of disruptive techniques for introducing symbolic computation and causation into machine learning so as to better deal with hierarchically structured data and inductive inference. To this end, we combine techniques from perturbation analysis as introduced by Pearl14 and algorithmic probability15.

For illustration purposes, let us consider the area of convolutional neural networks, one of the most promising approaches to image classification in machine learning, in which a set of primitive features is extracted from a distribution of images. In contrast, or in addition to convolutional neural networks, algorithmic causal deconvolution requires separating features by their most likely common generative mechanisms rather than by their most discriminative statistical features, with those combinations that have the greatest variance serving to distinguish an image from all others. Synthesizing generative computer programs rather than using traditional pattern recognition amounts to producing a truly algorithmic explanatory generative model based on a deeper understanding of a causal mechanism than is possible through (non)linear regression. By way of analogy, storing angles in a deep convolutional neural network layer from a distribution of images does not (necessarily) mean that these angles put together in some order are responsible for generating the object itself, just as the digits of the Fibonacci sequence do not build the Fibonacci sequence by simply arranging themselves in the right order (something that may be difficult to scale and generalize), but are constructed from an algorithmic process implementing a formula able to produce the digits of the Fibonacci sequence in the natural order according to a generative process.

We complement our work with techniques borrowed from classical information theory when we cannot do better, but at the core of our approach is the seminal concept of Solomonoff induction15.

The notion of deconvolution is similar and related to the notion of decomposition in methods of pattern recognition16, classical information theory17 (a survey can be found in ref. 18) and clustering by lossless compression19 such as those methods based on information distances20 and compression—for instance, the so-called ‘normalized information distance’21, and its related measure, the ‘normalized compression distance’22, and other variations.

Classical information theory23 has provided techniques for capturing and encoding statistical properties from data that affect almost all areas of science. For example, mutual information captures various averages based on associated distributions of statistical properties that are contained in one variable about another; that is, it captures how information can be combined and decomposed in purely statistical terms. Recent developments based on information decomposition have been introduced17,24 with the purpose of separating multivariate signals into their alleged generative sources. A proposal that has gained some traction is the so-called ‘partial information decomposition’17, which falls short24, among other reasons, because it can tell only what a variable can statistically reveal about some other variable.

Our approach can be viewed as replacing the methods used in computational mechanics25,26 (traditionally based on, for example, Markov processes and Bayesian inference) with a measure based on algorithmic probability and an empirical estimation of the so-called universal distribution27,28 (the distribution associated with algorithmic probability), while preserving the spirit of computational mechanics. In another related line of investigation into inductive inference, albeit mostly of a theoretical nature, there are approaches (such as AIXI) that combine algorithmic probability with decision theory, replacing the prior with the universal distribution29, something that we have also proposed in the context of algorithmic cognition research30.

In actual deployments, however, many approaches circumvent uncomputability and intractability by relying heavily on popular lossless compression algorithms such as Lempel–Ziv–Welch (LZW), minimum description length31, Monte Carlo search and Markov processes, thereby effectively adopting weaker models of computation. Another related theoretical approach is Levin’s search32 and variations33, based on a dovetailing algorithm interleaving computer programs one step at a time, from shortest to longest, with each program assigned a fraction of time proportional to its probability during each iteration. Resource-bounded algorithmic (Kolmogorov–Chaitin) complexity34 is also related to our approach. It imposes an upper bound on program length, which effectively adopts a linear finite automaton computational model35, which we circumvent by allowing improvements while increasing the running time (though in practice each calculation is restricted to a resource-bounded calculation). In another category are methods of inductive inference such as computational measures of information gain and reinforcement36,37.

One strength in our approach that Solomonoff himself defended38 is that if machines are going to have a problem-solving capability similar to those of humans, machines should not start from scratch every time for each new problem. Therefore, we precompute and store estimations of the universal distribution from explorations of large sets of small computer programs that are able to explain small pieces of data. Each computer program represents a discrete generative model of its corresponding piece of data, which, when assembled in sequence, represents a full model. The precomputation allows practical applications to be implemented in linear time by querying a look-up table27,28 acting as a working (Turing machine) tape and exchanging memory for computational time. This technique, combined with classical information theory in the way that the sequence model is assembled, provides key hints on the algorithmic content of a piece of data39. The estimations of our approach, denoted ‘BDM’, can always be improved on by running the original uncomputable process, with the advantage that partial results exponentially decrease the multiplicative constant involved in approaches such as Levin’s search. Our BDM approach (see Supplementary Information) has been shown to go beyond statistical capabilities39, capturing features that cannot be grasped by methods such as Shannon entropy, traditional pattern recognition, or lossless compression.

Our approach to deconvolution, based on algorithmic information dynamics1, is a bottom-up approach deeply rooted in Solomonoff’s inductive inference15,40,41; it is motivated by previous approaches, but conceived and designed for scalability without compromising the power of the computational model too early on. Behind the number or sequence of numbers matching observations or data to a complexity value using our methods, we also offer access to the generating rules explaining the data as candidate models that can be used for validation against present and future data, thus enabling predictions.

At the core of algorithmic information dynamics1 is the process of finding algorithmic candidate models in the form of computer programs able to explain pieces of observed data and group them by same/similar source or generating mechanism, using as a guide the length of the set of computer programs that produce each piece of data when a larger piece of data is decomposed in all possible ways by perturbation analysis. The main point is that if a computer program generates the data, different regions of the same data can be explained by the same algorithms.

### Deconvolution algorithms

The algorithm in the context of networks is as follows. Let G be a graph and let E = E(G) denote the set of edges. Let G\e denote the graph obtained after deleting an edge e from G. Let C(G) be the estimation of the algorithmic complexity of G (see Supplementary Information). The ‘information contribution’ of e to G is given by I(G, e) := C(G) − C(G\e). A positive information contribution corresponds to information loss and a negative contribution to information gain. Here we wish to find the subset FE such that the removal of the edges in F disconnects G into N components and minimizes the loss of information among all subsets of edges, that is the subset such that I(G, F) ≤ I(G, S) for all SE. Algorithm (1) in Supplementary Information allows us to obtain the subgraph (V, E\F) subject to the above conditions. The desired subset of edges is then given by F = E(G)\E(DECONVOLVE(G, N)).

The only parameter that the algorithm (see algorithm (1) in Supplementary Information) requires is N, the maximum number of components into which an object will be decomposed. However, there is a natural way to find the optimal terminating step, and therefore the number of maximum possible components that minimize the sum of the lengths of the candidate generating mechanisms, making the algorithm truly parameter-free, as it is not required to have a preset number of desired components. We provide the pseudo-code (in algorithm (2) of the Supplementary Information) that determines the optimal number of components; it requires no N parameter.

Clearly, if components s1 and s2 have the same algorithmic complexity, this does not immediately imply that s1 and s2 are generated by exactly the same generating mechanism. However, because of the exponential decay of the algorithmic probability of an increasingly random object, we know that the less random an object is, the exponentially more likely it is that the underlying mechanism will be the same. This is because there are exponentially fewer short (far from randomness) programs than long ones (see Supplementary Fig. 9c). For example, in the extreme case of fully connected graphs, we see that the complete graph denoted by Kn, with n the node count, has the smallest possible algorithmic complexity growth as a function of n, that is, ~c + log[n], where c is the length of the shortest computer program that implements the program that produces the matrix of size n × n with all 1 entries representing the complete graph. If |C(s1) − C(s2)| ≈ log[n], and s1 and s2 are connected graphs, then s1 and s2 are with high probability produced by the same algorithm. Conversely, if |C(s1) − C(s2)| departs from log(n), then the likelihood of being generated by the same algorithm exponentially vanishes. So the information regarding both the algorithmic complexity of the components and their relative size sheds light on the candidate generating mechanisms.

#### Algorithm unsupervised termination criterion

The algorithm suggests a natural terminating criterion. Let S be the object that has been produced by N mostly independent generative mechanisms. We decompose S into n parts s1, …, sn in such a way that each si, i {1 … n} has an underlying generating mechanism found by running the algorithm iteratively for increasing n. But after each iteration we calculate the minimum of the differences in algorithmic complexity among all components. The algorithm should then stop when the number of components is exactly N and the sum of the lengths—the estimated algorithmic complexity—of each of the programs diverges from the expected log[N]), because the length of the individual causal mechanisms producing each new component will be breaking down a component that could previously be explained by the causal mechanism at an earlier iteration of the algorithm. An implementation of this idea for a graph is shown in algorithm (2) in Supplementary Information).

As a trivial example, let us take the string 1n, where Sn means that the pattern S is repeated n times. After application of the algorithm, the terminating criterion will suggest that 1n cannot be broken down into smaller segments, each with a different causal generating mechanism, the sum of whose total lengths will be shorter than the length of the generating mechanism producing 1n itself. This is because the sum of the length of the shortest programs $${\sum }_{i}\left|{p}_{i}\right|$$ running on a universal Turing machine generating segments of 1n of length mi < n each, such that the concatenation i=1 pi = 1n will be strictly greater than C(1n), given that each pi halting criterion will require i log mi bits more than C(1n).

### Application to intertwined computer programs

A cellular automaton is a computer program that applies in parallel a global rule composed of local rules on a tape of cells with symbols (for example, binary). Thoroughly studied in ref. 1, elementary cellular automata (or ECA) are one-dimensional cellular automata that take into consideration in their local rules the cell next to the centre and the centre cell. For technical details see ‘Cellular automata’ section in the Supplementary Information.

Cellular automata offer an optimal testbed for our purposes because they are discrete dynamical systems able to illustrate their operation in a visual fashion. A cellular automaton can be interpreted as a one-dimensional object that produces a highly integrated two-dimensional image whose rows are causally connected and are thus ideal testing cases. Clearly, the deconvolution algorithms can be adapted to any object. In this case, instead of edge removal we apply row removal to the evolution of interacting cellular automata (see ‘Cellular automata’ section in the Supplementary Information for technical details). In what follows we perform experiments using interacting programs such as cellular automata as examples to illustrate the deconvolution algorithms. Interacting programs need to define how the interaction happens (see section ‘Interacting CA’ in Supplementary Information).

Behind our deconvolution methods is the idea that we can find a set of small computer rules or programs able to reconstruct a piece of data. Figure 1c,d illustrates this. In the deconvolution of a string generated by two different mechanisms (Fig. 1a,b) and thus in two different regimes (random versus non-random), computer programs such as those in Fig. 1c,d help to deconvolute the string. We then do the same in all other cases, but extending the number of degrees of freedom of a Turing machine tape. We note that our methods, as illustrated in Fig. 1a,b, are invariant to production or representation direction, given that the algorithmic probability and its reversal (and the entire set of computable transformations) are the same up to a small constant (the length of the computable transformation)42.

### Decomposition of sequences and space–time diagrams

We used different programs to produce different parts of a string, that is, a program p to generate segment s1 and a program p′ to generate segment s2 put next to each other. Clearly, the string has been generated by two generating mechanisms (p and p′). Next we used the algorithm to deconvolve the string and find the number of generating mechanisms and most likely model mechanisms (the programs themselves), inducing a form of ‘algorithmic partition’ based on the likelihood of each segment being produced by different generating mechanisms.

Figure 1a–e illustrates how strings that have short generating mechanisms are significantly and consistently more sensitive to perturbations. The resulting string is 0101010101010101010101010101010101010101010101010101110100101010100000001001100111100110000011100110, with the bolding corresponding to the parts suggested by the different regimes, according to their algorithmic contribution and the segment’s resilience in the face of perturbations (by deletion and replacement) of the original string. Behind every real number providing an estimation of the algorithmic complexity of a string or object, our methods also provide a set of generating computer programs able to produce such object when using our algorithmic-probability-based measure BDM.

Not only did we find the correct number of mechanisms (Fig. 1a,b), but also we found the candidate programs (which for this trivial example are exactly the original) that generate each segment (Fig. 1c–e) by seeking the shortest computer programs in a bottom-up approach27,28. Finding the shortest programs is, however, secondary, because we only care about the explanatory powers that different programs have to explain the data in full or in part, pinpointing the different causal nature of the segments and helping in the deconvolution of the original observation.

Figure 1c–e depicts the computer program (a non-terminating Turing machine) that is found when calculating the BDM of the 01n string. The BDM approximation to the algorithmic complexity of any 01n string is thus the number of small computer programs that are found capable of generating the same string or, conversely (via the algorithmic coding theorem, see refs. 39,43), the length of the shortest program producing the string. For example, the string 01n was trivially found to be generated by a large number of small computer programs (Fig. 1c,d depicts a non-terminating Turing machine with E its output) using our algorithmic methods (as opposed to, for example, using lossless compression, which would only obfuscate the possible generating model) with only two rules out of 2 × 2 rules for the size of Turing machine with only two states and two symbols and no more, and thus of very low algorithmic complexity compared to, for example, generating a random-looking string that would require a more complex (longer) computer program. The computer program of a truly random string will grow in proportion to the length of the random string, but for a low-complexity string such as 01n, repeated any number of times n, the length of the computer program is of (almost) fixed size, growing only by log(n) if the computer program is required to stop after n iterations. In this case, 01n is a trivial example with a strong statistical regularity whose low complexity could be captured by applying Shannon entropy alone on blocks of size 2.

### Cellular automaton two-dimensional deconvolution

Figure 1f–g illustrates how the algorithm can separate regions produced by generating mechanisms of different algorithmic information content by observing their space–time dynamics, thereby contributing to the deconvolution of regions that are produced by different generating mechanisms. In this example, both programs are sufficiently robust to not break down (see section ‘Robustness and limitations’ in Supplementary Information) when they interact with each other, with rule 110 prevailing over 255. Yet, in the general case, it is not always easy to tell these mechanisms apart. In more sophisticated examples, such as in Fig. 2d,e, we see how the algorithm can break down contiguous regions separating an object into two major components, corresponding to the different generating computer programs that are intertwined and actively interacting with each other. The experiment was repeated 20 times using programs with differing qualitative (for example, Wolfram class) behaviour.

Figure 2f demonstrates that perturbations of regions in red have a more random effect after their application and are thus by themselves less algorithmically random. When regions are of the same algorithmic complexity they are likely to be generated by similar algorithms, that is, from algorithms that are of similar minimal length. The removal of pixels in the blue regions moves the interacting system away from randomness and the pixels are themselves more algorithmically random. Blue structures on the left-hand side correspond to large triangles occurring in ECA rule 110 that are usually used to compute and transfer information in the form of particles.

However, triangular patterns transfer information in a limited way because their light cone of influence reduces at the greatest possible speed of the automaton, and they are assigned an absolute neutral information value. Absolute neutral values are those closest to 0. Once separated, the two regions have clearly different algorithmic characteristics given by their causal perturbation sensitivity, with the right-hand side being more sensitive to both random and non-random perturbations. Moreover, Fig. 2f shows results compatible with the theoretical expectation and findings in ref. 1, where a measure of reprogrammability associated with the number and magnitude of elements that can move a dynamical system towards or away from randomness was introduced and shown to be related to fundamental properties of the attractor space of the system.

Figure 2c–f shows that by iterating the deconvolution algorithm not only do the two main components of the image correspond to the two generating ECA rules, but a second application of the algorithm would produce a third or more components corresponding to further resilient features generated by the rules, which can be considered rules themselves within a smaller rule (state/symbol) space. However, in the deconvolved observations, the interacting rule determining how two or more rules may interact effectively constitutes a third global rule to which the algorithm has no direct access, or an apparent region in the observed window.

In the case of Fig. 2, the terminating criterion retrieves N = 3 components from the two interacting ECA (rule 60 and 110). This does not contradict the fact that we started from two generating mechanisms, because there are three clear regimes that are in fact likely to be reproducible by three different generating mechanisms, as suggested by the deconvolution algorithm itself, and as found in ref. 44, where it has been shown that rule 110 can be emulated by the composition of two simpler ECA rules (rules 51 and 118). As seen in Fig. 2, among the possible causal partitions, N = 2 successfully deconvolves ECA rule 60 from rule 110 on the first run, with a greater difference than the difference found between N = 3 components when breaking down rule 110 into its two different regimes.

### Unsupervised network deconvolution

Clustering can usually be viewed as solving a problem which has an underlying tree structure according to some measure of interest. One way to think of optimal classification is to discover a tree structure at some level of depth, with tree leaves closer to each other when such objects have a common or similar causal mechanism and for which no feature of interest has been selected. Figure 3 illustrates how the algorithm may partition data, in this case starting from a trivial example that breaks down complete K-ary trees. Traditionally, both partitioning and clustering are induced by an arbitrary distance measure of interest that determines the connections in a tree, with elements closer to a cluster centre connected by edges. The algorithm breaks down the trees (see Fig. 3) into as many components as desired by iterating over remaining elements if required until the number of desired components is obtained or the terminating criterion is applied (see subsection ‘Algorithm unsupervised termination criterion’). Figure 3a,b provides examples illustrating how to maximize topological symmetry. The algorithm can be applied, without loss of generalization, to any non-trivial graph, as in Fig. 3c,d, or to any dataset for that matter.

Figure 4 illustrates the algorithm and terminating criterion starting from an artificial graph composed of several graphs (two simple and one that is Erdős-Rényi random: a small Erdős-Rényi-random graph connected to a star graph and to a complete graph). The graph can be successfully decomposed by algorithmic probability (see Fig. 4d) by identifying the likelihood of an edge being produced by the same mechanism by virtue of being close to each other in the information contribution (which theoretically should be removed by only log(2) if it follows the normal evolution of the same process), hence what we call causal separation/partition and clustering. Figure 4d, with the broken components that were found above log(2) + ε, also shows the distribution of edges coloured by graph membership, perfectly corresponding to the different subgraphs that were used to compose the original graph in Fig. 4a.

The same task using classical information theory (Shannon entropy) is shown not to be sensitive enough, and a popular lossless compression algorithm (compression based on LZW) provided a noisy approximation of the results obtained by using the block decomposition method, as defined in ref. 39 (see section ‘Other methods and measures’ in Supplementary Information for details).

Figure 3c–e illustrates how randomly connected graphs with different topologies can be broken down into their respective generative mechanisms. Figure 3c is a complete graph of size 20 randomly connected by three edges to a scale-free graph of size 100. The graphs are generated by different mechanisms. One is a small program that, given a number N of nodes, produces a graph with all nodes connected to all other N − 1 nodes and has a program of short length that grows only by log N11. The scale-free network is generated by the canonical preferential attachment algorithm with two edges per node and requires a slightly longer algorithm that grows by log N + c (ref. 11), where c is a small constant accounting for the pseudo-random choice of attachment nodes. The algorithm breaks the graphs into two components, each of which corresponds to the graphs with different degree distributions (depicted below each case) associated with its generating mechanism. This is because $$\left|P\left({G}_{1}\right)\right|$$ + $$\left|P\left({G}_{2}\right)\right|$$ + … + $$\left|P\left({G}_{n}\right)\right|$$ + $$\left|P\left({e}_{{G}_{i}}\right)\right|$$ > $$\left|P\left({G}_{1}{G}_{2}\ldots {G}_{n}\right)\right|$$ for any Gi, where $${e}_{{G}_{i}}$$ is the set of edges randomly connecting Gi to Gj for any i and j for all G of low algorithmic complexity.

Figure 3d illustrates a case similar to that in Fig. 3c, but instead of a complete graph, an Erdős-Rényi graph with edge density 0.5 is produced and connected by three random edges to a scale-free network produced in the same fashion as in Fig. 3c. Again, the algorithm was able to break it down into the two corresponding subgraphs.

Current approaches to machine and deep learning are45 ill-equipped to deal with inductive inference, explanation and causation. Our methods are different from those used in other approaches (even those based on lossless compression algorithms) to estimate algorithmic complexity, and in particular, those from classical information theory and other statistical traditions. The methods introduced here promote the use of techniques from causal and perturbation analysis14 complemented by universal principles drawn from the theory of computability and algorithmic complexity.

Comparisons to other methods indicate that our approach is accurate and sensitive even in simplified form based on single-pixel perturbation (as opposed to, for example, full subset perturbations). This means there is also a lot of room for improvement and further exploration of other applications and other areas based on the same principles.

Our approach contributes to the discussion on ways to teach machine learning cause and effect, as recently called for by Pearl45 so as to depart from traditional statistical approaches in machine learning. We strongly believe (just as did Minsky46) that moving in the algorithmic direction and introducing symbolic computation complemented by previous achievements in the area of causation such as counterfactuals and the perturbation analysis introduced by Pearl et al.14, combined with the combinatorial power of current approaches to deep learning, is the way forward in addressing the challenge of causation in machine learning. Approaches like ours open up the possibility of designing more elaborate machine learning techniques with complementary and better equipped abilities grounded on completely different first principles.

### Code availability

A basic online implementation is available at http://www.complexitycalculator.com/deconvolution. Implementations in R and the Wolfram Language are available at https://github.com/allgebrist/Causal-Deconvolution-of-Networks/ and https://www.algorithmicdynamics.net/software.html. Some functions are also included in the Supplementary Information (Supplementary Methods).

The data that support the plots within this paper are available from the corresponding author upon request.

H.Z. was supported by Swedish Research Council (Vetenskapsrådet) grant number 2015-05299. J.T. was supported by the King Abdullah University of Science and Technology.


text:
# Output Variables¶

There are a large variety of possible output variables catmap can produce as demonstrated by the “output_variables” tutorial, which provides a comprehensive list of them. You can verify that they all work by running the tutorial and inspecting the plots generated or inspect the raw data in the .pkl file. A brief description of some of the more common ones are presented here below.

• free_energy: contains the free energy of all species in the reaction model as calculated by the scaler. This, in conjunction with the MechanismAnalysis module can be useful in diagnosing issues in the model where the free energies of intermediates are unexpected in some way. Along with the related scaler-originated variables rxn_parameter, frequency, electronic_energy, zero_point_energy, enthalpy, and entropy, these are not typically plotted on a contour plot as they are in the tutorial without manual adjustment to the plotting parameters.
• rate_control and selectivity_control: see Sensitivity analyses
• production_rate: The rate of the production of each gas phase species. If the gas is being consumed, consumption_rate or turnover_frequency (which encapsulates both production and consumption rates) may be more useful.
• coverage: Coverage of each adsorbed species. Very useful for quick sanity checks of “does this model output make sense”.
• rate: net rate (forward - backward) for each elementary step. The derived quantities forward_rate and reverse_rate are the absolute values of rate corresponding to the overall reaction direction. Specifically for the forward and reverse rates before they are summed, use directional_rates.

format: plain


text:
## 2006-11-24

### How to write a screen presentation

If you are looking for a way to write a screen presentation you probably think about PowerPoint, or hopefully OpenOffice Impress. But such an application is t' suck to load. Actually all you need for a professional and beautiful presentation is a simple text editor.

Beamer is a LaTeX package which helps to create a PDF presentation. You will select a theme for the presentation, and type the titles, the sections and/or subsections, add some lists and the content.

To install Beamer on a Debian system type apt-get install latex-beamer.

Next try to "compile" this LaTeX example into PDF with the command pdflatex:
% example.tex\documentclass{beamer}\usepackage[utf-8]{inputenc}\usetheme{Berlin}\title{Wireless Networks}\author{P. Pepin, M. Massonnet}\institute{IUT Nancy-Charlemagne}\begin{document}% A nice frontpage\frame{\titlepage}% Followed by the outline\section[Outline]{}\frame{\tableofcontents}\section{Panorama of technologies}\frame{        % This is an animation        \begin{itemize}        \item<1-> Bluetooth        \item<2-> UMTS        \item<3-> Wifi        \end{itemize}}\frame{    \frametitle{Bluetooth}    caca}\frame{    \frametitle{UMTS}    pipi}\frame{    \frametitle{Wifi}    cucul}\section{Local wireless networks}\frame{        \textsc{Beamer}, is really beautiful!}\section{Network protocols}\frame{        And it's easy.}\section{Security}\frame{        \begin{itemize}        \item<1-> Easy        \item<2-> Fast        \item<3-> Simple        \end{itemize}}\end{document}

Brilliant! Isn't it? ;-)

## 2006-11-20

### Auto update the background list for Xfdestkop

I have written a quick script to update the list of the images for the background in Xfdesktop.
#!/bin/sh# Update the background.list so the new downloaded wallpapers are available# to show up in Xfdesktop.LIST=$HOME/.config/xfce4/desktop/background.listecho "# xfce backdrop list" >$LISTfind $HOME/images/background/ -type f >>$LIST

Note: change in the last line the folder to the backgrounds.

This script can be either putted in an .zshrc file. Or better, if you use Xfce, save the script, under the name update-desktop-list.sh for example, to your personal bin folder (in my case $HOME/.local/bin) which is correctly set in the PATH, and run xfce4-autostart-editor. You can add the command update-desktop-list.sh. Finally you have to set up Xfdesktop to use the list (located at$LIST) of backgrounds. Go to Settings > Desktop manager, and select the list as the file. If it doesn't exist run the script a first time.

## 2006-11-11

### Real-transparent Terminal (yet again)

I have looked around the patch for gnome-terminal from Kristian Høgsberg and also the one for Terminal from Benny, and I managed to do the same for Terminal again since the vte libs have been modified, and support for real-transparency has been added. It was really simple, just init the rgba colormap, and call vte_terminal_set_opacity :) It requires version 0.13.3 or higher of vte.

Now someone could come with a good solution to integrate this nicely in Terminal. I think about a hidden option in ~/.config/Terminal/terminalrc, or even a slider.

Here is a first patch. It sets a hard-coded color for the alpha channel (0xDDDD).

Edit: And here comes a second patch which adds a hidden option for the opacity (ColorOpacity). It has to be in decimal, where 0xCCCC is 52428. Don't apply it over the first patch.

Edit 2: Benny commited changes to the trunk with support for real transparency, and a check for the version of libvte.


text:
Definition 10.53.1. Let $R \to S$ be a ring map.

1. We say that $R \to S$ is essentially of finite type if $S$ is the localization of an $R$-algebra of finite type.

2. We say that $R \to S$ is essentially of finite presentation if $S$ is the localization of an $R$-algebra of finite presentation.

Comment #2605 by Oliver on

Does this notion have an "official" scheme theoretic analogue? To me there are at least two choices. One would be to require the induced morphisms of stalks to be essentially of finite type as maps of rings, the other would be via open affine covers.

Comment #2606 by on

Do you think it would be useful to have such a notion?

There are also:

• 5 comment(s) on Section 10.53: Homomorphisms essentially of finite type

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
# How to negate a specific symbol?

I want to negate the symbol whose code is \models (this would be specific to Formal Logic). How can I do that? I tried a number of combination, but didn't find how this could be done. I tried \neqmodels, \nemodels, \notmodels, \nmodels but all of them are wrong.

Is there a general way to negate symbols?

• Does \not\models work for you? – Scott H. Oct 27 '13 at 18:06
• @ScottH. , Oh this works! thanx! but is there a general rule to negate symbols ? – Element Oct 27 '13 at 18:08
• There may be other ways, but all I know for a general rule is to throw a \not in front of they symbol to be negated. – Scott H. Oct 27 '13 at 18:10
• There are a couple of good answers here that might be adapted if you don't like the looks of \not. – Scott H. Oct 27 '13 at 18:15
• @ScottH.: Perhaps we can generalize this question into something that requests the negation of a symbol (the question as well), and write up something that uses a bunch of methods. \cancel, \not, and more? – Werner Oct 27 '13 at 18:25

There are a number of ways to achieve the negation of a symbol:

1. Follow the guidelines in How to look up a symbol or identify a math symbol or character? to see whether such a symbol already exists.

This is usually the best course of action, since the symbol would have been constructed to match certain specification (say, placement and height/depth of negation symbol). If such a symbol is only available in a different font, then consider including only that symbol by following the instructions in Importing a Single Symbol From a Different Font.

\documentclass{article}
\usepackage{amssymb}% http://ctan.org/pkg/amssymb
\begin{document}
$a \neq b \nparallel c \nvDash d \nprec e$
\end{document}

2. For a symbol \mysymbol, try \not\mysymbol. \not is a zero-width math relation that is set "on the right" of where it's called. As such, it visually overlaps the typical math relation/symbol. Not always perfect, but works in general.

\documentclass{article}
\begin{document}
$a \not= b \not\geq c \not\sim d \not\approx e \not\in f$
\end{document}

3. centernot works well when symbols are somewhat wider than usual, yet you still want the regular \not-like visual.

\documentclass{article}
\usepackage{centernot}% http://ctan.org/pkg/centernot
\begin{document}
$a \not= b \centernot= c \not\parallel d \centernot\parallel e \not\longrightarrow f \centernot\longrightarrow g$
\end{document}

4. The cancel package draws a diagonal line across a symbol to "cancel" it.

\documentclass{article}
\usepackage{centernot,cancel}% http://ctan.org/pkg/{centernot,cancel}
\begin{document}
$a \not= b \centernot= c \mathrel{\cancel{=}} d \not\longrightarrow e \centernot\longrightarrow f \mathrel{\cancel{\longrightarrow}} g$
\end{document}

5. Other methods include using graphics packages like tikz or pstricks to draw rules in specific locations across a symbol/construction.

• This is a great answer :) thanx for editing the question and providing this answer , it's a reference , I think! – Element Oct 27 '13 at 19:59
• \not\in shows why \notin is defined – egreg Oct 27 '13 at 20:24

A good compromise is usually \centernot (from the package centernot).

But sometimes \centernot is good, sometimes it isn't. For instance, \centernot{\in} produces a poorer result than \notin that uses the common slash instead.

In other cases, some small adjustments are necessary:

\documentclass{article}
\usepackage{centernot}

\begin{document}

$\centernot{\eta}$

$\mkern-1mu\not\mathrel{\mkern1mu\eta}\mkern1mu$

\end{document}

The first \mkern does a small backing up; then \not is typeset, which takes no horizontal space, then \eta is printed with no intervening space, because it has been turned into a relation symbol and TeX adds no space between consecutive relation symbols, but preceded by a small space that compensates for the negative space inserted before. A final space is added to take care of the fact that the slash ends right of \eta.

Note that all the construction will be considered as a relation symbol as far as spacing is concerned:

\documentclass{article}

\newcommand{\noteta}{%
\mkern-1mu\not\mathrel{\mkern1mu\eta}\mkern1mu
}

\begin{document}

$A \noteta B$

\end{document}

If an ordinary symbol is desired, add \mathord or just a pair of additional braces:

\newcommand{\noteta}{%
\mathord{\mkern-1mu\not\mathrel{\mkern1mu\eta}\mkern1mu}%
}

is equivalent to, but clearer than,

\newcommand{\noteta}{%
{\mkern-1mu\not\mathrel{\mkern1mu\eta}\mkern1mu}%
}

Such manual adjustments may be needed depending on the shape of the symbols involved.

How to get \not\to arrow?

## Probably best test code with amssymb

\documentclass{article}
\usepackage{amssymb}
\usepackage{unicode-math} % if you also need maths

\begin{document}
$\nrightarrow$
\end{document}

giving

## Test code with centernot package but negative complications with unicode-math

\documentclass{article}
\usepackage{centernot}% http://ctan.org/pkg/centernot

\begin{document}
$\centernot\to$
\end{document}

giving

Errors with centernot package

• with unicode-math: Latex Error: ./file.tex:9 Missing { inserted.

## \not\to alone gives unaligned arrow but unicode-math package works

\documentclass{article}
\usepackage{unicode-math} % if you also need maths
\begin{document}
$\not\to$
\end{document}

• Your question about this subject was closed as duplicate. If you change the question to reflect the actual problem you have, then it can be reopened. Making a question here is not the way to go. – egreg Sep 15 '15 at 13:50
• @egreg This is not a question! It is an answer to the thing. This is a specific task to negate \to symbol. I already deleted the old question because it was closed. I think this one is here ok because it fits the title. – Léo Léopold Hertz 준영 Sep 15 '15 at 14:00
• You do seem to answer a different question to what was asked though. Especially when referring to \nrightarrow which is not necessarily present for all symbols. And centernot was already covered by Werner and egreg. I fell you could re-work this answer quite a bit and it would be OK. You would have to make it more general. Your first point could be to try and find a negated version of the symbol (often called \n...), of course here the OP already tried that. – moewe Sep 15 '15 at 14:18
• \centernot was not covered for the symbol \to. It is the case here. Therefore, I left it like that. Feel free to edit if you can improve it, but without losing the information about \to and its negation. – Léo Léopold Hertz 준영 Sep 15 '15 at 14:20
• Mhhh, but then there are other symbols that are not explicitly covered in the other answers, do you want to add an answer for those as well? I appreciate that there was some lateral thinking needed to get from \to to \rightarrow and then to \nrightarrow as a negated version of \not. But from the other answer people can easily infer that trying \centernot\to might be an option. – moewe Sep 15 '15 at 14:41


text:
Preprint

# Learning to Separate Domains in Generalized Zero-Shot and Open Set Learning: a probabilistic perspective

Authors:
Preprints and early-stage research may not have been peer reviewed yet.
To read the file of this research, you can request a copy directly from the authors.

## Abstract

This paper studies the problem of domain division problem which aims to segment instances drawn from different probabilistic distributions. Such a problem exists in many previous recognition tasks, such as Open Set Learning (OSL) and Generalized Zero-Shot Learning (G-ZSL), where the testing instances come from either seen or novel/unseen classes of different probabilistic distributions. Previous works focused on either only calibrating the confident prediction of classifiers of seen classes (W-SVM), or taking unseen classes as outliers. In contrast, this paper proposes a probabilistic way of directly estimating and fine-tuning the decision boundary between seen and novel/unseen classes. In particular, we propose a domain division algorithm of learning to split the testing instances into known, unknown and uncertain domains, and then conduct recognize tasks in each domain. Two statistical tools, namely, bootstrapping and Kolmogorov-Smirnov (K-S) Test, for the first time, are introduced to discover and fine-tune the decision boundary of each domain. Critically, the uncertain domain is newly introduced in our framework to adopt those instances whose domain cannot be predicted confidently. Extensive experiments demonstrate that our approach achieved the state-of-the-art performance on OSL and G-ZSL benchmarks.

## No file available

ResearchGate has not been able to resolve any citations for this publication.
Conference Paper
Full-text available
Article
Full-text available
The number of categories for action recognition is growing rapidly and it has become increasingly hard to label sufficient training data for learning conventional models for all categories. Instead of collecting ever more data and labelling them exhaustively for all categories, an attractive alternative approach is "zeroshot learning" (ZSL). To that end, in this study we construct a mapping between visual features and a semantic descriptor of each action category, allowing new categories to be recognised in the absence of any visual training data. Existing ZSL studies focus primarily on still images, and attribute-based semantic representations. In this work, we explore word-vectors as the shared semantic space to embed videos and category labels for ZSL action recognition. This is a more challenging problem than existing ZSL of still images and/or attributes, because the mapping between the semantic space and video space-time features of actions is more complex and harder to learn for the purpose of generalising over any cross-category domain shift. To solve this generalisation problem in ZSL action recognition, we investigate a series of synergistic improvements to the standard ZSL pipeline. First, we enhance significantly the semantic space mapping by proposing manifold-regularised regression and data augmentation strategies. Second, we evaluate two existing post processing strategies (transductive self-training and hubness correction), and show that they are complementary. We evaluate extensively our model on a wide range of human action datasets including HMDB51, UCF101, OlympicSports, CCV and TRECVID MED 13. The results demonstrate that our approach achieves the state-of-the-art zero-shot action recognition performance with a simple and efficient pipeline, and without supervised annotation of attributes.
Conference Paper
Full-text available
Image classification has advanced significantly in recent years with the availability of large-scale image sets. However, fine-grained classification remains a major challenge due to the annotation cost of large numbers of fine-grained categories. This project shows that compelling classification performance can be achieved on such categories even without labeled training data. Given image and class embeddings, we learn a compatibility function such that matching embeddings are assigned a higher score than mismatching ones; zero-shot classification of an image proceeds by finding the label yielding the highest joint compatibility score. We use state-of-the-art image features and focus on different supervised attributes and unsuper-vised output embeddings either derived from hierarchies or learned from unlabeled text corpora. We establish a substantially improved state-of-the-art on the Animals with Attributes and Caltech-UCSD Birds datasets. Most encourag-ingly, we demonstrate that purely unsupervised output em-beddings (learned from Wikipedia and improved with fine-grained text) achieve compelling results, even outperform-ing the previous supervised state-of-the-art. By combining different output embeddings, we further improve results.
Article
Full-text available
Attributes act as intermediate representations that enable parameter sharing between classes, a must when training data is scarce. We propose to view attribute-based image classification as a label-embedding problem: each class is embedded in the space of attribute vectors. We introduce a function that measures the compatibility between an image and a label embedding. The parameters of this function are learned on a training set of labeled samples to ensure that, given an image, the correct classes rank higher than the incorrect ones. Results on the Animals With Attributes and Caltech-UCSD-Birds datasets show that the proposed framework outperforms the standard Direct Attribute Prediction baseline in a zero-shot learning scenario. Label embedding enjoys a built-in ability to leverage alternative sources of information instead of or in addition to attributes, such as e.g. class hierarchies or textual descriptions. Moreover, label embedding encompasses the whole range of learning settings from zero-shot learning to regular learning with a large number of labeled examples.
Article
Full-text available
Most existing zero-shot learning approaches exploit transfer learning via an intermediate-level semantic representation shared between an annotated auxiliary dataset and a target dataset with different classes and no annotation. A projection from a low-level feature space to the semantic representation space is learned from the auxiliary dataset and is applied without adaptation to the target dataset. In this paper we identify two inherent limitations with these approaches. First, due to having disjoint and potentially unrelated classes, the projection functions learned from the auxiliary dataset/domain are biased when applied directly to the target dataset/domain. We call this problem the projection domain shift problem and propose a novel framework, transductive multi-view embedding, to solve it. The second limitation is the prototype sparsity problem which refers to the fact that for each target class, only a single prototype is available for zero-shot learning given a semantic representation. To overcome this problem, a novel heterogeneous multi-view hypergraph label propagation method is formulated for zero-shot learning in the transductive embedding space. It effectively exploits the complementary information offered by different semantic representations and takes advantage of the manifold structures of multiple representation spaces in a coherent manner. We demonstrate through extensive experiments that the proposed approach (1) rectifies the projection shift between the auxiliary and target domains, (2) exploits the complementarity of multiple semantic representations, (3) significantly outperforms existing methods for both zero-shot and N-shot recognition on three image and video benchmark datasets, and (4) enables novel cross-view annotation tasks.
Article
Full-text available
Real-world tasks in computer vision often touch upon open set recognition: multi-class recognition with incomplete knowledge of the world and many unknown inputs. Recent work on this problem has proposed a model incorporating an open space risk term to account for the space beyond the reasonable support of known classes. This paper extends the general idea of open space risk limiting classification to accommodate non-linear classifiers in a multi-class setting. We introduce a new open set recognition model called compact abating probability (CAP), where the probability of class membership decreases in value (abates) as points move from known data toward open space. We show that CAP models improve open set recognition for multiple algorithms. Leveraging the CAP formulation, we go on to describe the novel Weibull-calibrated SVM (W-SVM) algorithm, which combines the useful properties of statistical extreme value theory for score calibration with one-class and binary support vector machines. Our experiments show that the W-SVM is significantly better for open set object detection and OCR problems when compared to the state-of-the-art for the same tasks.
Article
Full-text available
Several recent publications have proposed methods for mapping images into continuous semantic embedding spaces. In some cases the semantic embedding space is trained jointly with the image transformation, while in other cases the semantic embedding space is established independently by a separate task, such as a natural language processing task on a text corpus, and then the image transformation into that space is learned in a second stage. Proponents of these image embedding systems have stressed their advantages over the traditional n-way classification framing of image understanding, particularly in terms of the promise of zero-shot learning -- the ability to correctly annotate images of previously unseen object categories. Here we propose a simple method for constructing an image embedding system from any existing n-way image classification mechanism and any existing semantic embedding space which contains the n class labels in its vocabulary. Our method maps images into the semantic embedding space via convex combination of the class label embedding vectors, and requires no additional learning. We show that this simple and direct method confers many of the advantages associated with more complex image embedding schemes, and indeed outperforms state of the art methods on the ImageNet zero-shot learning task.
Article
Full-text available
To date, almost all experimental evaluations of machine learning-based recognition algorithms in computer vision have taken the form of "closed set" recognition, whereby all testing classes are known at training time. A more realistic scenario for vision applications is "open set" recognition, where incomplete knowledge of the world is present at training time, and unknown classes can be submitted to an algorithm during testing. This paper explores the nature of open set recognition and formalizes its definition as a constrained minimization problem. The open set recognition problem is not well addressed by existing algorithms because it requires strong generalization. As a step toward a solution, we introduce a novel "1-vs-set machine," which sculpts a decision space from the marginal distances of a 1-class or binary SVM with a linear kernel. This methodology applies to several different applications in computer vision where open set recognition is a challenging problem, including object recognition and face verification. We consider both in this work, with large scale cross-dataset experiments performed over the Caltech 256 and ImageNet sets, as well as face matching experiments performed over the Labeled Faces in the Wild set. The experiments highlight the effectiveness of machines adapted for open set evaluation compared to existing 1-class and binary SVMs for the same tasks.
Conference Paper
Full-text available
We study the problem of object classification when training and test classes are disjoint, i.e. no training examples of the target classes are available. This setup has hardly been studied in computer vision research, but it is the rule rather than the exception, because the world contains tens of thousands of different object classes and for only a very few of them image, collections have been formed and annotated with suitable class labels. In this paper, we tackle the problem by introducing attribute-based classification. It performs object detection based on a human-specified high-level description of the target objects instead of training images. The description consists of arbitrary semantic attributes, like shape, color or even geographic information. Because such properties transcend the specific learning task at hand, they can be pre-learned, e.g. from image datasets unrelated to the current task. Afterwards, new classes can be detected based on their attribute representation, without the need for a new training phase. In order to evaluate our method and to facilitate research in this area, we have assembled a new largescale dataset, "Animals with Attributes", of over 30,000 animal images that match the 50 classes in Osherson's classic table of how strongly humans associate 85 semantic attributes with animal classes. Our experiments show that by using an attribute layer it is indeed possible to build a learning object detection system that does not require any training images of the target classes.
Conference Paper
Full-text available
For many KDD applications, such as detecting criminal activities in E-commerce, finding the rare instances or the outliers, can be more interesting than finding the common patterns. Existing work in outlier detection regards being an outlier as a binary property. In this paper, we contend that for many scenarios, it is more meaningful to assign to each object a degree of being an outlier. This degree is called the local outlier factor (LOF) of an object. It is local in that the degree depends on how isolated the object is with respect to the surrounding neighborhood. We give a detailed formal analysis showing that LOF enjoys many desirable properties. Using real-world datasets, we demonstrate that LOF can be used to find outliers which appear to be meaningful, but can otherwise not be identified with existing approaches. Finally, a careful performance evaluation of our algorithm confirms we show that our approach of finding local outliers can be practical.
Article
Full-text available
Suppose you are given some data set drawn from an underlying probability distribution P and you want to estimate a “simple” subset S of input space such that the probability that a test point drawn from P lies outside of S equals some a priori specified value between 0 and 1. We propose a method to approach this problem by trying to estimate a function f that is positive on S and negative on the complement. The functional form of f is given by a kernel expansion in terms of a potentially small subset of the training data; it is regularized by controlling the length of the weight vector in an associated feature space. The expansion coefficients are found by solving a quadratic programming problem, which we do by carrying out sequential optimization over pairs of input patterns. We also provide a theoretical analysis of the statistical performance of our algorithm. The algorithm is a natural extension of the support vector algorithm to the case of unlabeled data.
Article
Full-text available
In this paper, we define meta-recognition, a performance prediction method for recognition algorithms, and examine the theoretical basis for its post-recognition score analysis form through the use of the statistical extreme value theory (EVT). The ability to predict the performance of a recognition system based on its outputs for each match instance is desirable for a number of important reasons, including automatic threshold selection for determining matches and non-matches, and automatic algorithm selection or weighting for multi-algorithm fusion. The emerging body of literature on post-recognition score analysis has been largely constrained to biometrics, where the analysis has been shown to successfully complement or replace image quality metrics as a predictor. We develop a new statistical predictor based upon the Weibull distribution, which produces accurate results on a per instance recognition basis across different recognition problems. Experimental results are provided for two different face recognition algorithms, a fingerprint recognition algorithm, a SIFT-based object recognition system, and a content-based image retrieval system.
Article
Full-text available
Under fairly general assumptions on the underlying distribution function, the bootstrap process, pertaining to the sample $q$-quantile, converges weakly in $D_\mathbb{R}$ to the standard Brownian motion. Furthermore, weak convergence of a smoothed bootstrap quantile estimate is proved which entails that in this particular case the smoothed bootstrap estimate outperforms the nonsmoothed one.
Article
Full-text available
Kolmogorov's goodness-of-fit measure, D_n , for a sample CDF has consistently been set aside for methods such as the D^+_n or D^-_n of Smirnov, primarily, it seems, because of the difficulty of computing the distribution of D_n . As far as we know, no easy way to compute that distribution has ever been provided in the 70+ years since Kolmogorov's fundamental paper. We provide one here, a C procedure that provides Pr(D_n < d) with 13-15 digit accuracy for n ranging from 2 to at least 16000. We assess the (rather slow) approach to limiting form, and because computing time can become excessive for probabilities>.999 with n's of several thousand, we provide a quick approximation that gives accuracy to the 7th digit for such cases.
Conference Paper
Zero-shot learning consists in learning how to recognize new concepts by just having a description of them. Many sophisticated approaches have been proposed to address the challenges this problem comprises. In this paper we describe a zero-shot learning approach that can be implemented in just one line of code, yet it is able to outperform state of the art approaches on standard datasets. The approach is based on a more general framework which models the relationships between features, attributes, and classes as a two linear layers network, where the weights of the top layer are not learned but are given by the environment. We further provide a learning bound on the generalization error of this kind of approaches, by casting them as domain adaptation methods. In experiments carried out on three standard real datasets, we found that our approach is able to perform significantly better than the state of art on all of them, obtaining a ratio of improvement up to 17%17$backslash$%.
Article
Due to the importance of zero-shot learning, the number of proposed approaches has increased steadily recently. We argue that it is time to take a step back and to analyze the status quo of the area. The purpose of this paper is three-fold. First, given the fact that there is no agreed upon zero-shot learning benchmark, we first define a new benchmark by unifying both the evaluation protocols and data splits. This is an important contribution as published results are often not comparable and sometimes even flawed due to, e.g. pre-training on zero-shot test classes. Second, we compare and analyze a significant number of the state-of-the-art methods in depth, both in the classic zero-shot setting but also in the more realistic generalized zero-shot setting. Finally, we discuss limitations of the current status of the area which can be taken as a basis for advancing it.
Conference Paper
Conference Paper
We investigate the problem of generalized zero-shot learning (GZSL). GZSL relaxes the unrealistic assumption in conventional zero-shot learning (ZSL) that test data belong only to unseen novel classes. In GZSL, test data might also come from seen classes and the labeling space is the union of both types of classes. We show empirically that a straightforward application of classifiers provided by existing ZSL approaches does not perform well in the setting of GZSL. Motivated by this, we propose a surprisingly simple but effective method to adapt ZSL approaches for GZSL. The main idea is to introduce a calibration factor to calibrate the classifiers for both seen and unseen classes so as to balance two conflicting forces: recognizing data from seen classes and those from unseen ones. We develop a new performance metric called the Area Under Seen-Unseen accuracy Curve to characterize this trade-off. We demonstrate the utility of this metric by analyzing existing ZSL approaches applied to the generalized setting. Extensive empirical studies reveal strengths and weaknesses of those approaches on three well-studied benchmark datasets, including the large-scale ImageNet with more than 20,000 unseen categories. We complement our comparative studies in learning methods by further establishing an upper bound on the performance limit of GZSL. In particular, our idea is to use class-representative visual features as the idealized semantic embeddings. We show that there is a large gap between the performance of existing approaches and the performance limit, suggesting that improving the quality of class semantic embeddings is vital to improving ZSL.
Article
Modern visual recognition systems are often limited in their ability to scale to large numbers of object categories. This limitation is in part due to the increasing difficulty of acquiring sufficient training data in the form of labeled images as the number of object categories grows. One remedy is to leverage data from other sources - such as text data - both to train visual models and to constrain their predictions. In this paper we present a new deep visual-semantic embedding model trained to identify visual objects using both labeled image data as well as semantic information gleaned from unannotated text. We demonstrate that this model matches state-of-the-art performance on the 1000-class ImageNet object recognition challenge while making more semantically reasonable errors, and also show that the semantic information can be exploited to make predictions about tens of thousands of image labels not observed during training. Semantic knowledge improves such zero-shot predictions achieving hit rates of up to 18% across thousands of novel labels never seen by the visual model.
Article
The test is based on the maximum difference between an empirical and a hypothetical cumulative distribution. Percentage points are tabled, and a lower bound to the power function is charted. Confidence limits for a cumulative distribution are described. Examples are given. Indications that the test is superior to the chi-square test are cited.
Conference Paper
We consider the problem of semi-supervised bootstrap learning for scene categorization. Existing semi-supervised approaches are typically unreliable and face semantic drift because the learning task is under-constrained. This is primarily because they ignore the strong interactions that often exist between scene categories, such as the common attributes shared across categories as well as the attributes which make one scene different from another. The goal of this paper is to exploit these relationships and constrain the semi-supervised learning problem. For example, the knowledge that an image is an auditorium can improve labeling of amphitheaters by enforcing constraint that an amphitheater image should have more circular structures than an auditorium image. We propose constraints based on mutual exclusion, binary attributes and comparative attributes and show that they help us to constrain the learning problem and avoid semantic drift. We demonstrate the effectiveness of our approach through extensive experiments, including results on a very large dataset of one million images.
Conference Paper
Recent work has shown that visual attributes are a powerful approach for applications such as recognition, image description and retrieval. However, fusing multiple attribute scores - as required during multi-attribute queries or similarity searches - presents a significant challenge. Scores from different attribute classifiers cannot be combined in a simple way; the same score for different attributes can mean different things. In this work, we show how to construct normalized “multi-attribute spaces” from raw classifier outputs, using techniques based on the statistical Extreme Value Theory. Our method calibrates each raw score to a probability that the given attribute is present in the image. We describe how these probabilities can be fused in a simple way to perform more accurate multiattribute searches, as well as enable attribute-based similarity searches. A significant advantage of our approach is that the normalization is done after-the-fact, requiring neither modification to the attribute classification system nor ground truth attribute annotations. We demonstrate results on a large data set of nearly 2 million face images and show significant improvements over prior work. We also show that perceptual similarity of search results increases by using contextual attributes.
Article
We study the problem of object recognition for categories for which we have no training examples, a task also called zero--data or zero-shot learning. This situation has hardly been studied in computer vision research, even though it occurs frequently; the world contains tens of thousands of different object classes, and image collections have been formed and suitably annotated for only a few of them. To tackle the problem, we introduce attribute-based classification: Objects are identified based on a high-level description that is phrased in terms of semantic attributes, such as the object's color or shape. Because the identification of each such property transcends the specific learning task at hand, the attribute classifiers can be prelearned independently, for example, from existing image data sets unrelated to the current task. Afterward, new classes can be detected based on their attribute representation, without the need for a new training phase. In this paper, we also introduce a new data set, Animals with Attributes, of over 30,000 images of 50 animal classes, annotated with 85 semantic attributes. Extensive experiments on this and two more data sets show that attribute-based classification indeed is able to categorize images without access to any training images of the target classes.
Article
A simple method for testing the probability that a set of numbers is a sample from a known distribution consists of comparing the empirical cumulative distribution function of the sample, Sn(x), with the known cumulative distribution function F(x). Both Dn = maximum {Sn(x) – F{x)} and Dn* = maximum | Sn(x) – F(x) | are random variables, independent of the special form of F(x), if F(x) is continuous. This paper contains more extensive tables of the percentage points in the distributions of Dn and Dn* than have been published previously. These values are obtained by empirical modification of a known asymptotic formula.* This study was supported in part by funds granted to Ohio State University by the Research Foundation for aid in fundamental research. The author acknowledges the assistance of Nelson Prentiss, Vincent Donato, Milton Glanz, and Richard Thomas in carrying out numerical computations.
Conference Paper
Remarkable performance has been reported to recognize single object classes. Scalability to large numbers of classes however remains an important challenge for today's recognition methods. Several authors have promoted knowledge transfer between classes as a key ingredient to address this challenge. However, in previous work the decision which knowledge to transfer has required either manual supervision or at least a few training examples limiting the scalability of these approaches. In this work we explicitly address the question of how to automatically decide which information to transfer between classes without the need of any human intervention. For this we tap into linguistic knowledge bases to provide the semantic link between sources (what) and targets (where) of knowledge transfer. We provide a rigorous experimental evaluation of different knowledge bases and state-of-the-art techniques from Natural Language Processing which goes far beyond the limited use of language in related work. We also give insights into the applicability (why) of different knowledge sources and similarity measures for knowledge transfer.
Article
We discuss the following problem given a random sample X = (X 1, X 2,…, X n) from an unknown probability distribution F, estimate the sampling distribution of some prespecified random variable R(X, F), on the basis of the observed data x. (Standard jackknife theory gives an approximate mean and variance in the case R(X, F) = $$\theta \left( {\hat F} \right) - \theta \left( F \right)$$, θ some parameter of interest.) A general method, called the “bootstrap”, is introduced, and shown to work satisfactorily on a variety of estimation problems. The jackknife is shown to be a linear approximation method for the bootstrap. The exposition proceeds by a series of examples: variance of the sample median, error rates in a linear discriminant analysis, ratio estimation, estimating regression parameters, etc.
Towards open world recognition
• Abhijit Bendale
• Terrance Boult
Abhijit Bendale and Terrance Boult. Towards open world recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1893-1902, 2015. 2
Zero-shot learning through cross-modal transfer
• Richard Socher
• Milind Ganjoo
• D Christopher
• Andrew Manning
• Ng
Richard Socher, Milind Ganjoo, Christopher D Manning, and Andrew Ng. Zero-shot learning through cross-modal transfer. In Advances in neural information processing systems, pp. 935-943, 2013. (document), 3.3, 3.3, 6.3


text:
# An impractical but difficult problem I stumbled upon

1. Sep 13, 2011

### bigmoneyhat

I'm only a high school physics/calculus student, so bear with me.

The problem is as such: There are two planetary masses, with no pre-existing velocity or acceleration that exist in a vacuum with no other forces being acted on them other than their gravity. What I want to find is how long it would take for these two masses to collide.

I've tried working on this problem myself for a while. So any help would be appreciated.

2. Sep 13, 2011

### rcgldr

3. Sep 14, 2011

### rcgldr

Call the spheres A and B, and let the origin of the coordinate system lie at the midpoint of the line segment defined by their centres.
Calling the sphere centres' positions as functions of time

$$x_{A} (t) , x_{B} (t) , x_{A} (0) = -5 , x_{B} (0) = 5$$

respectively, we define the distance function between them as:

$$D(t)=x_{B} (t) - x_{A} (t) , D(0) = D_{0} = 10$$

Setting up Newton's 2nd law for both, we get, with unit masses:

$$\frac{d^{2}x_{A}}{dt^{2}} = \frac{G}{D^{2}}$$

$$\frac{d^{2}x_{B}}{dt^{2}} = -\frac{G}{D^{2}}$$

whereby the equation for d(t) is readily derived:

$$\frac{d^{2} D}{dt^{2}} = -\frac{2G}{D^{2}} (*)$$

We assume that the initial velocities are 0, i.e

$$\frac{dD}{dt}\mid_{t=0}=0$$

Let us multiply (*) with dD/dt:

$$\frac{d^{2}D}{dt^{2}}\frac{dD}{dt}=-\frac{2G}{D^{2}}\frac{dD}{dt}$$

Integrating both sides from t=0 to some arbitrary t-value, taking due notice of the initial conditions, yields:

$$\frac{1}{2}(\frac{dD}{dt})^{2}=\frac{2G}{D}-\frac{2G}{D_{0}}$$

multiplying with two, taking the square root and remembering that D(t) will be decreasing, we get the diff. eq:

$$\frac{dD}{dt} = -\sqrt{ \frac{4G}{D_{0}}} \sqrt{ \frac{D_{0} - D} {D}}$$

This is a separable diff.eq; we write:

$$\sqrt{ \frac{D}{D_{0} - D}} dD = -\sqrt{ \frac{4G}{D_{0}}} dt$$

We now remember that when they spheres make contact, D(T)=2, where T is the time we're looking for! Thus, we get the equation for T, integrating both sides:

$$\int_{10}^{2} \sqrt{ \frac{D}{D_{0}-D}} dD = -\sqrt{ \frac{4G}{D_{0}}} T$$

or equivalently:

$$T = \sqrt{ \frac{D_{0}}{4G}} \int_{2}^{10} \sqrt{ \frac{D}{D_{0}-D}}dD$$

In order to crack that integral, let us set:

$$u=\sqrt{\frac{D}{D_{0}-D}}\to{D}=D_{0}-\frac{D_{0}}{1+u^{2}}$$

$$dD=\frac{D_{0}2u}{(1+u^{2})^{2}}du$$

The limits are

$$D=10\to{u}=\infty,D=2\to{u}=\frac{1}{2}$$

We thereby get the expression for T in u:

$$T = D_{0} \sqrt{ \frac{D_{0}}{G}} \int_{ \frac{1}{2}}^{ \infty} \frac{u^{2}du} {(1+u^{2})^{2}}$$

doing integration by parts.

$$\int \frac{1}{1+u^{2}}du = \frac{u}{1+u^{2}} + \int \frac{2u^{2}}{(1+u^{2})^{2}}du$$

$$\int \frac{u^{2}}{(1+u^{2})^{2}}du = \frac{1}{2}( \arctan(u) - \frac{u}{1+u^{2}})+C$$

and

$$T = \frac{10^{ \frac{3}{2}}} {2 \sqrt{G}} ( \frac{ \pi}{2} - \arctan( \frac{1}{2}) + \frac{2}{5})$$

Last edited: Sep 14, 2011


text:
# In what sense if any does java have multiple dispatch?

I'm trying to get my head around the difference between message passing (with which we are all familiar as by far the most common form of object orientation today) vs generic functions as implemented in CLOS (Common Lisp Object System).

In what sense is it possible to say java has a kind of multiple-dispatch system due to method overloading?

To sketch my understanding, in message passing you might do:

tell obja move objb
tell objb move obja

but where the function is first class and not in any object, you might do:

move obja objb

The part I do think I understand is that with generics there is no dilemma on where to place a function, whereas in message passing you may have to arbitrarily choose which class to put a function on, then just remember which one you put it on. With message passing, if you want to be able to call the behaviour from either, you have to duplicate the code (yes I know there are ways round that, but that's not the point).

I'm not sure I'm really getting the rest of how generics are different yet.

I just found a key reference on this point.

The wiki page on CLOS is also very good.

So, maybe best method is to hold off with the theory and just practice with clojure multi-methods at some point... unless anyone wishes to chip in.

• I think this is language-specific enough to be off-topic, here at Computer Science. – David Richerby Aug 9 '19 at 12:16
• Idea - If you used one class to be a global container of all methods, (which would actually have to be static functions in this case), you could simulate multiple dispatch. You would always pass as the first parameter to any 'method' on this god object the first object concerned (in the single dispatch world this would be the class it belonged to), but then all the remaining parameters too could cause dispatch to different method bodies based on their type, via method overloading, so you'd have multiple dispatch, allbeit in very limited form (and barely OO any more perhaps, because static)... – mwal Aug 11 '19 at 23:36


text:
The {$K$}-groups and the index theory of certain comparison {$C^*$}-algebras

@article{Monthubert2011TheA,
title={The \{\$K\$\}-groups and the index theory of certain comparison \{\$C^*\$\}-algebras},
author={Bertrand Monthubert and Victor Nistor},
journal={arXiv: K-Theory and Homology},
year={2011}
}
• Published 11 May 2010
• Mathematics
• arXiv: K-Theory and Homology
We compute the $K$-theory of comparison $C^*$-algebra associated to a manifold with corners. These comparison algebras are an example of the abstract pseudodifferential algebras introduced by Connes and Moscovici \cite{M3}. Our calculation is obtained by showing that the comparison algebras are a homomorphic image of a groupoid $C^*$-algebra. We then prove an index theorem with values in the $K$-theory groups of the comparison algebra.
4 Citations
The principal-symbol index map for an algebra of pseudodifferential operators
A C*algebra A generated by a class of zero-order classical pseudodifferential operator on a cylinder RxB, where B is a compact riemannian manifold, containing operators with periodic symbols, is
An Index Formula for Perturbed Dirac Operators on Lie Manifolds
• Mathematics
• 2011
We prove an index formula for a class of Dirac operators coupled with unbounded potentials, also called “Callias-type operators”. More precisely, we study operators of the form $P := \hspace* {.5mm} References SHOWING 1-10 OF 53 REFERENCES Hopf algebroids and secondary characteristic classes • Mathematics • 2007 We study a Hopf algebroid,$\calh$, naturally associated to the groupoid$U_n^\delta\ltimes U_n$. We show that classes in the Hopf cyclic cohomology of$\calh$can be used to define secondary K-theory of C*-algebras of b-pseudodifferential Operators • Mathematics • 1998 Abstract. We compute K-theory invariants of algebras of pseudodifferential operators on manifolds with corners and prove an equivariant index theorem for operators invariant with respect to an action SPECTRAL INVARIANCE FOR CERTAIN ALGEBRAS OF PSEUDODIFFERENTIAL OPERATORS • Mathematics Journal of the Institute of Mathematics of Jussieu • 2005 We construct algebras of pseudodifferential operators on a continuous family groupoid$\mathcal{G}\$ that are closed under holomorphic functional calculus, contain the algebra of all
Index Theory and Non-Commutative Geometry I. Higher Families Index Theory
• Mathematics
• 2004
We prove an index theorem for foliated manifolds. We do so by constructing a push forward map in cohomology for a K-oriented map from an arbitrary manifold to the space of leaves of an oriented
The Atiyah-Singer index formula for subelliptic operators on contact manifolds. Part I
The Atiyah-Singer index theorem gives a topological formula for the index of an elliptic differential operator. The topological index depends on a cohomology class that is constructed from the
A topological index theorem for manifolds with corners
• Mathematics
Compositio Mathematica
• 2011
Abstract We define an analytic index and prove a topological index theorem for a non-compact manifold M0 with poly-cylindrical ends. Our topological index theorem depends only on the principal
Groupoids and an index theorem for conical pseudo-manifolds
• Mathematics
• 2006
Abstract We define an analytical index map and a topological index map for conical pseudomanifolds. These constructions generalize the analogous constructions used by Atiyah and Singer in the proof


text:
# If $a,b,c$ are all different and $\begin{vmatrix}a&a^3&a^4-1\\b&b^3&b^4-1\\c&c^3&c^4-1\end{vmatrix}=0$ then the value of $abc(ab+bc+ca)$ is
$\begin{array}{1 1}(A)\;a+b+c&(B)\;0\\(C)\;a^2+b^2+c^2&(D)\;a^2-b^2+c^2\end{array}$


text:
41. pingcat

Most data on the Internet is transferred over TCP or UDP. The former works best when the transport needs to be reliable, and the latter is for when lower latency is more important than data loss or packet reordering. However, for a laugh, you can also transfer it over ICMP, aka ping.

As a quick refresher, the ping(8) command works by sending ICMP echo-request packets with some random data, then waiting for ICMP echo-reply packets with the same data. The key point is that the data doesn’t really have to be random.

A                       B
|  echo-request(data)   |
| --------------------> |
|                       |
| <-------------------- |
|                       |

Here, we’ll only be focusing on the interesting bits; the full code listing for pingcat is available here. Be aware that the program only works when run by root (or by messing with the sticky bit or capabilities). For the complete ping(8) implementation, see the iputils package.

The first problem is that we need to send ICMP packets. Looking at the docs for socket(2), we see it’s easy to create TCP (SOCK_STREAM) or UDP (SOCK_DGRAM) sockets. With ICMP, it’s a bit trickier: we have to use a raw socket (SOCK_RAW), and compose the packets manually.

int icmp_sock = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP);

Composing ICMP packets sounds a bit daunting, but it’s particularly easy in C. All we need to do is allocate a chunk of memory, cast it to the right type, and fill in the fields.

u_char buf[0x10000];
struct icmphdr *icp = (struct icmphdr *)buf;
icp->type = ICMP_ECHO;
icp->code = 0;
icp->checksum = 0;
icp->un.echo.sequence = count;  // an incrementing number
icp->un.echo.id = id;           // something to identify this process
// the first 8 bytes are the ICMP packet, the rest is the data
memcpy(buf + 8, data, datalen);
icp->checksum = in_cksum((u_short*)icp, datalen + 8, 0);

We still need to send out the packet. Strictly speaking, all we need to do is write it to the socket, but because we dislike copying data around, we’ll do it the hard way and use scatter-gather network IO.

struct sockaddr_in addr;
struct iovec iov = { buf, 0 };
iov.iov_len = datalen + 8;
struct msghdr hdr = { &addr, sizeof(addr),
&iov, 1, 0, 0, 0 };
sendmsg(icmp_sock, &hdr, 0);

That’s it for the sending side. As for receiving, it’s almost the inverse process: we open a raw socket, read packets from it, and parse them.

int icmp_sock = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP);
u_char buf[0x10000];
struct iovec iov = { buf, sizeof(buf) };
struct iphdr *ip = (struct iphdr *)buf;
struct msghdr msg;
memset(&msg, 0, sizeof(msg));
msg.msg_name = 0;
msg.msg_namelen = 0;
msg.msg_iov = &iov;
msg.msg_iovlen = 1;
int datalen = recvmsg(icmp_sock, &msg, MSG_DONTWAIT);

Parsing is a bit more complex because we get IP packets, so we first need to extract the ICMP part.

int hlen = ip->ihl*4;
datalen -= hlen;
struct icmphdr *icp = (struct icmphdr *)(buf + hlen);

Next, we need to filter out the noise. Our ICMP socket will get a copy of every ICMP packet received by the host. Since we only care about echo-reply packets, we need to filter by icp->type == ICMP_ECHOREPLY. We also don’t care about packets from other processes, so we need to filter by icp->un.echo.id == id. Since ICMP packets may be reordered, dropped, or duplicated, we also need to inspect icp->un.echo.sequence to make sure it’s the reply to the right packet. Finally, to get to the data, we just skip the 8 bytes of ICMP header: (char*)icp + 8.

And that’s all there is to it. Of course, the devil’s in details, as iputils’ ping demonstrates. For pingcat, the difficulty lies in that we have to implement reliable transmission on top of an unreliable protocol, so we have to deal with the usual issues of missing, reordered, and duplicate packets. To keep the code clear, pingcat does the simple thing and sends data synchronously: it sends some data, waits for the reply, maybe it resends the data if the reply was corrupted or lost, but it never has more than one data chunk in-flight.

One last interesting point about echo-reply packets is that they contain the full data sent. This essentially means we can use the network as a storage medium. The back of the envelope calculation for me goes like this: the ICMP round-trip time between me and www.tv-tokyo.co.jp is about 0.3s; my upload speed is about 6Mb/s; this means I can have about 1.8 Mb, or one copy of Hamlet by William Shakespeare, stored in the very links of the Internet at any given time.


text:
# Calculus: Fundamental Theorem of Calculus (FTC) – #28726

Question: Compute the following definite integral

$\int\limits_{0}^{\pi /6}{\frac{dx}{{{\cos }^{2}}\left( 2x \right)}}$


text:
# Entropy of a Linear Toral Automorphism

I'm trying to calculate the entropy of the Linear Toral Automorphism induced by

$$f(x,y,z)=(x,y+x,y+z)$$

This is an exercise in the Katok book.

This map has all eigenvalues equal to 1. But I do not want to use that $~~ h_{top}(f)= log (max|\lambda_i|)$. would like to use Katok's suggestion that says that the cardinality separate sets grow quadratically with $n$ where $n$ is the size of the orbit. But I can not see it clearly.

-
Hint: start by computing eigenvalues of $Df$. The largest eigenvalue will tell you about expansion rate along that tangent direction. What does this tell you about entropy? – William Jun 22 '12 at 4:04
@William: This map has all eigenvalues equal to 1. But I do not want to use that $~~ h_{top}(f)= log (max|\lambda_i|)$. – user27456 Jun 22 '12 at 16:40
Could anybody tell me what branch of math is this? And what is that entropy? Wikipedia article or something similar will suffice. – Yrogirg Jun 25 '12 at 6:13
@ Yrogirg: Look at this page, maths.bristol.ac.uk/~maxcu/DynSysErgTh.html . For something more specific look at the reading titled topological entropy – user27456 Jun 25 '12 at 15:57

We have $$f^n(x,y,z)=(x,\,y+nx,\,z+ny+\tbinom n 2 x)$$ Taking $\|\cdot\|_\infty$ as a metric on $(\mathbb R/\mathbb Z)^3$, this implies $$d_n(a,b) \le (1+n+n(n-1)/2) \|a-b\|_\infty$$ where $d_n$ is the maximum distance between the two orbits $(a,f(a),\dots,f^n(a))$.
So that an $(n,\varepsilon)$-separated set must be $(0,\Omega(\varepsilon/n^2))$-separated (in other words, the metric $d_n$ grows at most quadratically) and therefore, since we are in dimension $d=3$, for fixed $\varepsilon$ its cardinality grows as $O(n^{2d})$, which suffices to conclude that $h_{top}(f)=0$.
Note that the cardinality itself does grow faster than quadratically, as can be seen with the following $n^2(n-1)/2$ points $M_{uv}$: \left\{\begin{aligned} x=&u/\tbinom n 2\\ y=&v/n\\ z=&0 \end{aligned}\right. If $d_n(M_{uv},M_{u'v'})<\varepsilon<1/4$ for some odd $n$, then we have $$|n(y'-y)+\tbinom n 2 (x'-x)|<\varepsilon\\ |v'-v+u'-u|<1\\ v'-v = -(u'-u)$$ $$|(n+1)/2\cdot(y'-y)+\tbinom{(n+1)/2}{2}(x'-x)|<\varepsilon\\ |u'-u|<\frac{n}{(n+1)/4}\varepsilon<1\\ u=u'\\ v=v'$$ So that we have a set of $\Omega(n^3)$ points that is $(n,\varepsilon)$-separated.


text:
1. ## Substitution and Integrate

The integral is 1/(1+cubert[x]) dx from 0 to 1. I'm supposed to make a substitution to express the integrand as a rational function and then evaluate the integral.

I got the part of x=u^2-1 and dx=2du but plugging into the equation and going from there I'm getting messed up somewhere.

2. Originally Posted by sfgiants13
The integral is 1/(1+cubert[x]) dx from 0 to 1. I'm supposed to make a substitution to express the integrand as a rational function and then evaluate the integral.

I got the part of x=u^2-1 and dx=2du but plugging into the equation and going from there I'm getting messed up somewhere.
$\int\frac{dx}{1+\sqrt[3]{x}}\overbrace{\mapsto}^{z^3=x}\int\frac{3z^2}{1+z }dz$