IBM Research - Thomas J. Watson Research Center

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods.

Human evaluations of machine translation are extensive but expensive. Human evaluations can take months to finish and involve human labor that can not be reused. We propose a method of automatic machine translation evaluation that is quick, inexpensive, and language-independent, that correlates highly with human evaluation, and that has little marginal cost per run. We present this method as an automated understudy to skilled human judges which substitutes for them when there is need for quick or frequent evaluations.

An unknown quantum state \ensuremath{\Vert}\ensuremath{\varphi}〉 can be disassembled into, then later reconstructed from, purely classical information and purely nonclassical Einstein-Podolsky-Rosen (EPR) correlations. To do so the sender, ``Alice,'' and the receiver, ``Bob,'' must prearrange the sharing of an EPR-correlated pair of particles. Alice makes a joint measurement on her EPR particle and the unknown quantum system, and sends Bob the classical result of this measurement. Knowing this, Bob can convert the state of his EPR particle into an exact replica of the unknown state \ensuremath{\Vert}\ensuremath{\varphi}〉 which Alice destroyed.

Most current speech recognition systems use hidden Markov models (HMMs) to deal with the temporal variability of speech and Gaussian mixture models (GMMs) to determine how well each state of each HMM fits a frame or a short window of frames of coefficients that represents the acoustic input. An alternative way to evaluate the fit is to use a feed-forward neural network that takes several frames of coefficients as input and produces posterior probabilities over HMM states as output. Deep neural networks (DNNs) that have many hidden layers and are trained using new methods have been shown to outperform GMMs on a variety of speech recognition benchmarks, sometimes by a large margin. This article provides an overview of this progress and represents the shared views of four research groups that have had recent successes in using DNNs for acoustic modeling in speech recognition.

The electronic properties of inversion and accumulation layers at semiconductor-insulator interfaces and of other systems that exhibit two-dimensional or quasi-two-dimensional behavior, such as electrons in semiconductor heterojunctions and superlattices and on liquid helium, are reviewed. Energy levels, transport properties, and optical properties are considered in some detail, especially for electrons at the (100) silicon-silicon dioxide interface. Other systems are discussed more briefly.

We propose an implementation of a universal set of one- and two-quantum-bit gates for quantum computation using the spin states of coupled single-electron quantum dots. Desired operations are effected by the gating of the tunneling barrier between neighboring dots. Several measures of the gate quality are computed within a recently derived spin master equation incorporating decoherence caused by a prototypical magnetic environment. Dot-array experiments that would provide an initial demonstration of the desired nonequilibrium spin dynamics are proposed.

A 2001 IBM manifesto observed that a looming software complexity crisis -caused by applications and environments that number into the tens of millions of lines of code - threatened to halt progress in computing. The manifesto noted the almost impossible difficulty of managing current and planned computing systems, which require integrating several heterogeneous environments into corporate-wide computing systems that extend into the Internet. Autonomic computing, perhaps the most attractive approach to solving this problem, creates systems that can manage themselves when given high-level objectives from administrators. Systems manage themselves according to an administrator's goals. New components integrate as effortlessly as a new cell establishes itself in the human body. These ideas are not science fiction, but elements of the grand challenge to create self-managing computing systems.

A new technique for three-dimensional (3D) camera calibration for machine vision metrology using off-the-shelf TV cameras and lenses is described. The two-stage technique is aimed at efficient computation of camera external position and orientation relative to object reference coordinate system as well as the effective focal length, radial lens distortion, and image scanning parameters. The two-stage technique has advantage in terms of accuracy, speed, and versatility over existing state of the art. A critical review of the state of the art is given in the beginning. A theoretical framework is established, supported by comprehensive proof in five appendixes, and may pave the way for future research on 3D robotics vision. Test results using real data are described. Both accuracy and speed are reported. The experimental results are analyzed and compared with theoretical prediction. Recent effort indicates that with slight modification, the two-stage calibration can be done in real time.

As is well known, operations on one particle of an Einstein-Podolsky-Rosen (EPR) pair cannot influence the marginal statistics of measurements on the other particle. We characterize the set of states accessible from an initial EPR state by one-particle operations and show that in a sense they allow two bits to be encoded reliably in one spin-1/2 particle: One party, ``Alice,'' prepares an EPR pair and sends one of the particles to another party, ``Bob,'' who applies one of four unitary operators to the particle, and then returns it to Alice. By measuring the two particles jointly, Alice can now reliably learn which operator Bob used.

The general problem of estimating the a posteriori probabilities of the states and transitions of a Markov source observed through a discrete memoryless channel is considered. The decoding of linear block and convolutional codes to minimize symbol error probability is shown to be a special case of this problem. An optimal decoding algorithm is derived.

Extensions of percolation theory to treat transport are described. Resistor networks, from which resistors are removed at random, provide the natural generalization of the lattice models for which percolation thresholds and percolation probabilities have previously been considered. The normalized conductance, $G$, of such networks proves to be a sharply defined quantity with a characteristic concentration dependence near threshold which appears sensitive only to dimensionality. Numerical results are presented for several families of $3D$ and $2D$ network models. Except close to threshold, the models based on bond percolation are accurately described by a simple effective medium theory, which can also treat continuous media or situations less drastic than the percolation models, for example, materials in which local conductivity has a continuous distribution of values. The present calculations provide the first quantitative test of this theory. A "Green's function" derivation of the effective medium theory, which makes contact with similar treatments of disordered alloys, is presented. Finally, a general expression for the conductance of a percolation model is obtained which relates $G$ to the spin-stiffness coefficient, $D$, of an appropriately defined model dilute ferromagnet. We use this relationship to argue that the "percolation channels" through which the current flows above threshold must be regarded as three dimensional.

We consider an Ising model in which the spins are coupled by infinite-ranged random interactions independently distributed with a Gaussian probability density. Both "spinglass" and ferromagnetic phases occur. The competition between the phases and the type of order present in each are studied.

A general form is proposed for an empirical interatomic potential for multicomponent systems. This form interpolates between potentials for the respective elements to treat heteronuclear bonds. The approach is applied to C-Si and Si-Ge systems. In particular, the properties of SiC and its defects are well described.

Inspired by the brain's structure, we have developed an efficient, scalable, and flexible non-von Neumann architecture that leverages contemporary silicon technology. To demonstrate, we built a 5.4-billion-transistor chip with 4096 neurosynaptic cores interconnected via an intrachip network that integrates 1 million programmable spiking neurons and 256 million configurable synapses. Chips can be tiled in two dimensions via an interchip communication interface, seamlessly scaling the architecture to a cortexlike sheet of arbitrary size. The architecture is well suited to many applications that use complex neural networks in real time, for example, multiobject detection and classification. With 400-pixel-by-240-pixel video input at 30 frames per second, the chip consumes 63 milliwatts.

Geographical curves are so involved in their detail that their lengths are often infinite or, rather, undefinable. However, many are statistically "selfsimilar," meaning that each portion can be considered a reduced-scale image of the whole. In that case, the degree of complication can be described by a quantity D that has many properties of a "dimension," though it is fractional; that is, it exceeds the value unity associated with the ordinary, rectifiable, curves.

The problem of allocating network resources to the users of an integrated services network is investigated in the context of rate-based flow control. The network is assumed to be a virtual circuit, connection-based packet network. It is shown that the use of generalized processor sharing (GPS), when combined with leaky bucket admission control, allows the network to make a wide range of worst-case performance guarantees on throughput and delay. The scheme is flexible in that different users may be given widely different performance guarantees and is efficient in that each of the servers is work conserving. The authors present a practical packet-by-packet service discipline, PGPS that closely approximates GPS. This allows them to relate results for GPS to the packet-by-packet scheme in a precise manner. The performance of a single-server GPS system is analyzed exactly from the standpoint of worst-case packet delay and burstiness when the sources are constrained by leaky buckets. The worst-case session backlogs are also determined.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

The usual general-purpose computing automaton (e.g., a Turing machine) is logically irreversible—its transition function lacks a single-valued inverse. Here it is shown that such machines may be made logically reversible at every step, while retaining their simplicity and their ability to do general computations. This result is of great physical interest because it makes plausible the existence of thermodynamically reversible computers which could perform useful computations at useful speed while dissipating considerably less than kT of energy per logical step. In the first stage of its computation the logically reversible automaton parallels the corresponding irreversible automaton, except that it saves all intermediate results, thereby avoiding the irreversible operation of erasure. The second stage consists of printing out the desired output. The third stage then reversibly disposes of all the undesired intermediate results by retracing the steps of the first stage in backward order (a process which is only possible because the first stage has been carried out reversibly), thereby restoring the machine (except for the now-written output tape) to its original condition. The final machine configuration thus contains the desired output and a reconstructed copy of the input, but no other undesired data. The foregoing results are demonstrated explicitly using a type of three-tape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation.

We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions of expected value at least .87856 times the optimal value. These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation. This relaxation can be interpreted both as a semidefinite program and as an eigenvalue minimization problem. The best previously known approximation algorithms for these problems had perfc~rmance guarantees of ~for MAX CUT and ~for MAX 2SAT. Slight extensions of our analysis lead to a .79607-approximation algorithm for the maximum directed cut problem (MAX DICUT) and a .758-approximation algorithm for MAX SAT, where the best previously known approxim ation algorithms had performance guarantees of ~and ~, respectively. Our algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and represents the first use of :semidefinite programming in the design of approximation algorithms.

Empirical interatomic potentials permit the calculation of structural properties and energetics of complex systems. A new approach for constructing such potentials, by explicitly incorporating the dependence of bond order on local environment, permits an improved description of covalent materials. In particular, a new potential for silicon is presented, along with results of extensive tests which suggest that this potential provides a rather realistic description of silicon. The limitations of the potential are discussed in detail.

The phase diagrams and phase transitions of bosons with short-ranged repulsive interactions moving in periodic and/or random external potentials at zero temperature are investigated with emphasis on the superfluid-insulator transition induced by varying a parameter such as the density. Bosons in periodic potentials (e.g., on a lattice) at T=0 exhibit two types of phases: a superfluid phase and Mott insulating phases characterized by integer (or commensurate) boson densities, by the existence of a gap for particle-hole excitations, and by zero compressibility. Generically, the superfluid onset transition in d dimensions from a Mott insulator to superfluidity is ``ideal,'' or mean field in character, but at special multicritical points with particle-hole symmetry it is in the universality class of the (d+1)-dimensional XY model. In the presence of disorder, a third, ``Bose glass'' phase exists. This phase is insulating because of the localization effects of the randomness and analogous to the Fermi glass phase of interacting fermions in a strongly disordered potential.The Bose glass phase is characterized by a finite compressibility, no gap, but an infinite superfluid susceptibility. In the presence of disorder the transition to superfluidity is argued to occur only from the Bose glass phase, and never directly from the Mott insulator. This zero-temperature superfluid-insulator transition is studied via generalizations of the Josephson scaling relation for the superfluid density at the ordinary \ensuremath{\lambda} transition, highlighting the crucial role of quantum fluctuations. The transition is found to have a dynamic critical exponent z exactly equal to d and correlation length and order-parameter correlation exponents \ensuremath{\nu} and \ensuremath{\eta} which satisfy the bounds \ensuremath{\nu}\ensuremath{\ge}2/d and \ensuremath{\eta}\ensuremath{\le}2-d, respectively. It is argued that the superfluid-insulator transition in the presence of disorder may have an upper critical dimension ${d}_{c}$ which is infinite, but a perturbative renormalization-group calculation wherein the critical exponents have mean-field values for weak disorder above d=4 is also discussed. Many of these conclusions are verified by explicit calculations on a model of one-dimensional bosons in the presence of both random and periodic potentials. The general results are applied to experiments on $^{4}\mathrm{He}$ absorbed in porous media such as Vycor. Some measurable properties of the superfluid onset are predicted exactly [e.g., the exponent x relating the \ensuremath{\lambda} transition temperature to the zero-temperature superfluid density is found to be d/2(d-1)], while stringent bounds are placed on others. Analysis of preliminary data is consistent with these predictions.