Lyft's mission is to improve people's lives with the world's best transportation. Self driving vehicles have the potential to deliver unprecedented improvements to safety and quality, at a price and convenience that challenges traditional models of vehicle ownership. A combination of hardware, software, and knowledge technologies are needed to build self-driving cars. In this talk, I'll present the core problems in self-driving and how recent advances in computer vision, robotics, and machine learning are powering this revolution. The car is carefully designed with a variety of sensors that complement each other to address a wide variety of driving scenarios. Sensor fusion bring all of these signals together into an interpretable AI engine comprising of perception, prediction, planning, and controls. For example, deep learning models and large scale machine learning have closed the gap between human and machine perception. In contrast, predicting the behavior of other humans and effectively planning and negotiating maneuvers continue to be hard problems. Combining AI technologies with deep knowledge about the real world is key to addressing these.

A variety of lossless compression schemes have been proposed to reduce the storage requirements of web graphs. One successful approach is virtual node compression [7], in which often-used patterns of links are replaced by links to virtual nodes, creating a compressed graph that succinctly represents the original. In this paper, we show that several important classes of web graph algorithms can be extended to run directly on virtual node compressed graphs, such that their running times depend on the size of the compressed graph rather than the original. These include algorithms for link analysis, estimating the size of vertex neighborhoods, and a variety of algorithms based on matrix-vector products and random walks. Similar speed-ups have been obtained previously for classical graph algorithms like shortest paths and maximum bipartite matching. We measure the performance of our modified algorithms on several publicly available web graph datasets, and demonstrate significant empirical speedups that nearly match the compression ratios.

A link server is a system designed to support efficient implementations of graph computations on the web graph. In this work, we present a compression scheme for the web graph specifically designed to accommodate community queries and other random access algorithms on link servers. We use a frequent pattern mining approach to extract meaningful connectivity formations. Our Virtual Node Miner achieves graph compression without sacrificing random access by generating virtual nodes from frequent itemsets in vertex adjacency lists. The mining phase guarantees scalability by bounding the pattern mining complexity to O(E log E). We facilitate global mining, relaxing the requirement for the graph to be sorted by URL, enabling discovery for both inter-domain as well as intra-domain patterns. As a consequence, the approach allows incremental graph updates. Further, it not only facilitates but can also expedite graph computations such as PageRank and local random walks by implementing them directly on the compressed graph. We demonstrate the effectiveness of the proposed approach on several publicly available large web graph data sets. Experimental results indicate that the proposed algorithm achieves a 10- to 15-fold compression on most real word web graph data sets

Adversarial IR in general, and search engine spam, in particular, are engaging research topics with a real-world impact for Web users, advertisers and publishers. The AIRWeb workshop will bring researchers and practitioners in these areas together, to present and discuss state-of-the-art techniques as well as real-world experiences. Given the continued growth in search engine spam creation and detection efforts, we expect interest in this AIRWeb to surpass that of the previous three editions of the workshop (held jointly with WWW 2005, SIGIR 2006, and WWW 2007 respectively).

This paper presents a redundant bit vector approach for indexing and retrieval of handwritten words captured using an electronic pen or tablet. Handwritten words (cursive or print) are first segmented into strokes and each stroke is featurized using a neural network. Oriented principal component analysis (OPCA) is used for dimensionality reduction while ensuring robustness to handwriting variation (noise). Redundant bit vectors are used to index the resulting low dimensional representations for efficient storage and retrieval. Experimental results on large datasets with 898,652 handwritten words show good retrieval performance that is robust to handwriting variations and generalizes well over different writers and writing styles.

A minimal perfect function maps a static set of n keys on to the range of integers {0,1,2,...,n - 1}. We present a scalable high performance algorithm based on random graphs for constructing minimal perfect hash functions (MPHFs). For a set of n keys, our algorithm outputs a description of h in expected time O(n). The evaluation of h(x) requires three memory accesses for any key x and the description of h takes up 0.89n bytes (7.13n bits). This is the best (most space efficient) known result to date. Using a simple heuristic and Huffman coding, the space requirement is further reduced to 0.79n bytes (6.86n bits). We present a high performance architecture that is easy to parallelize and scales well to very large data sets encountered in internet search applications. Experimental results on a one billion URL dataset obtained from Live Search crawl data, show that the proposed algorithm (a)finds an MPHF for one billion URLs in less than 4 minutes, and (b) requires only 6.86 bits/key for the description of h.

We present a new approach to personalized handwriting recognition. The problem, also known as writer adaptation, consists of converting a generic (user-independent) recognizer into a personalized (user-dependent) one, which has an improved recognition rate for a particular user. The adaptation step usually involves user-specific samples, which leads to the fundamental question of how to fuse this new information with that captured by the generic recognizer. We propose adapting the recognizer by minimizing a regularized risk functional (a modified SVM) where the prior knowledge from the generic recognizer enters through a modified regularization term. The result is a simple personalization framework with very good practical properties. Experiments on a 100 class real-world data set show that the number of errors can be reduced by over 40% with as few as five user samples per character.

HIPs, or Human Interactive Proofs, are challenges meant to be easily solved by humans, while remaining too hard to be economically solved by computers. HIPs are increasingly used to protect services against automatic script attacks. To be effective, a HIP must be difficult enough to discourage script attacks by raising the computation and/or development cost of breaking the HIP to an unprofitable level. At the same time, the HIP must be easy enough to solve in order to not discourage humans from using the service. Early HIP designs have successfully met these criteria [1]. However, the growing sophistication of attackers and correspondingly increasing profit incentives have rendered most of the currently deployed HIPs vulnerable to attack [2,7,12]. Yet, most companies have been reluctant to increase the difficulty of their HIPs for fear of making them too complex or unappealing to humans. The purpose of this study is to find the visual distortions that are most effective at foiling computer attacks without hindering humans. The contribution of this research is that we discovered that 1) automatically generating HIPs by varying particular distortion parameters renders HIPs that are too easy for computer hackers to break, yet humans still have difficulty recognizing them, and 2) it is possible to build segmentation-based HIPs that are extremely difficult and expensive for computers to solve, while remaining relatively easy for humans.

This paper proposes a glyph hashing approach to optical character recognition with applications in document conversion. The viability and efficiency of the approach is tested through its implementation in a print driver on 68,987 PDF documents containing 1.15 billion characters. Results indicate that a hash table with (a) 3.2 million hashes is sufficient to represent all characters from these documents, and (b) 480 fonts are sufficient to cover over 90% of these documents. Glyph recognizing experiments indicate that 80% of unique character glyphs and over 96% of all characters from unseen documents can be found in a hash table built using all 68,987 documents. The hashing approach is used to not only recognize the character codes but also, size, style (bold, italic, etc), and font name. We found that the hashing approach can scale to hundreds of fonts and thousands of characters per font. Further, it is extremely fast and can recognize over 100,000 characters per second. Owing to its speed, such a hashing approach can complement any existing OCR system by acting as a pre-filter to produce a 4-5 times speedup during document conversion.

Machine learning is often used to automatically solve human tasks. In this paper, we look for tasks where machine learning algorithms are not as good as humans with the hope of gaining insight into their current limitations. We studied various Human Interactive Proofs (HIPs) on the market, because they are systems designed to tell computers and humans apart by posing challenges presumably too hard for computers. We found that most HIPs are pure recognition tasks which can easily be broken using machine learning. The harder HIPs use a combination of segmentation and recognition tasks. From this observation, we found that building segmentation tasks is the most effective way to confuse machine learning algorithms. This has enabled us to build effective HIPs (which we deployed in MSN Passport), as well as design challenging segmentation tasks for machine learning algorithms.

An evolutionary algorithm has taught itself how to play the game of checkers without using features that would normally require human expertise. Using only the raw positions of pieces on the board and the piece differential, the evolutionary program optimized artificial neural networks to evaluate alternative positions in the game. Over the course of several hundred generations, the program taught itself to play at a level that is competitive with human experts (one level below human masters). This was verified by playing the best evolved neural network against 165 human players on an Internet gaming zone. The neural network's performance earned a rating that was better than 99.61% of all registered players at the Website. Control experiments between the best evolved neural network and a program that relies on material advantage indicate the superiority of the neural network both at equal levels of look ahead and CPU time. The results suggest that the principles of Darwinian evolution may he usefully applied to solving problems that have not yet been solved by human expertise.

We have been exploring the potential for a coevolutionary process to learn how to play checkers without relying on the usual inclusion of human expertise in the form of features that are believed to be important to playing well. In particular, we have focused on the use of a population of neural networks, where each network serves as an evaluation function to describe the quality of the current board position. After only a little more than 800 generations, the evolutionary process has generated a neural network that can play checkers at the expert level as designated by the US Chess Federation rating system. The current effort reports on a competition between the best-evolved neural network, named "Anaconda," and commercially available software. In a series of six games, Anaconda scored a perfect six wins.

Abstract- Under a species-level abstraction of classical evolutionary programming, the standard tournament selection model is not appropriate. When viewed in this manner, it is more appropriate to consider two modes of life histories: background evolution and extinction. The utility of this approach as an optimization procedure is evaluated on a series of test functions relative to the performance of classical evolutionary programming and fast evolutionary programming. The results indicate that on some smooth, convex landscapes and over noisy, highly multimodal landscapes, extinction evolutionary programming can outperform classical and fast evolutionary programming. On other landscapes, however, extinction evolutionary programming performs considerably worse than classical and fast evolutionary programming. Potential reasons for this variability in performance are indicated. 1

Previous studies have shown that embedding local search in classical evolutionary programming (EP) could lead to improved performance on function optimization problems. The utility of local search is investigated with fast evolutionary programming (FEP) and comparisons are offered between performance improvements obtained when using local search with Gaussian and Cauchy mutations. Experiments were conducted on a suite of four well known function optimization problems using two local search methods (conjugate gradient and F.J. Solis and R.J.-B. Wets, (1981)) with varying amounts of local search being incorporated into the evolutionary algorithm. Empirical results indicate that FEP with the conjugate gradient method outperforms other hybrid methods on three of the four functions when evolution was conducted for a fixed number of generations. Trials using local search produced solutions that were statistically as good as or better than trials without local search. However, the cost of using local search justified the enhancement in solution quality only when using Gaussian mutations but not when using Cauchy mutations.

A common data mining heuristic is, "when choosing between models with the same training error, less complex models should be preferred as they perform better on unseen data". This heuristic may not always hold. In genetic programming a preference for less complex models is implemented as: (i) placing a limit on the size of the evolved program; (ii) penalizing more complex individuals, or both. The paper presents a GP-variant with no limit on the complexity of the evolved program that generates highly accurate models on a common dataset.

Evolutionary programming was proposed more than thirty five years ago for generating artificial intelligence. The original experiments consisted of evolving populations of finite state machines (FSMs) for prediction, identification, and control. Since then, all of the studies with FSMs and evolutionary programming have been limited to the evolution of strictly non-modular FSMs. In this study, a modular FSM architecture is proposed and an evolutionary programming procedure for evolving such structures is presented. Preliminary results indicate that the proposed procedure is indeed capable of successfully evolving modular FSMs and that such modularity can result in a statistically significantly increased rate of optimization.

Multiple sequence alignment can be used as a tool for the identification of common structure in an ordered string of nucleotides (in DNA or RNA) or amino acids (in proteins). Current multiple sequence alignment algorithms work well for sequences with high similarity but do not scale well when either the length or number of the sequences is large or if the similarity is low. The focus of the paper is to develop an evolutionary programming (EP) algorithm for multiple sequence alignment. An EP method with representation specific variation operators is proposed and tested on several data sets. Comparisons to other algorithms suggests that this algorithm is well suited to the multiple sequence alignment problem.

The design of evolutionary computations based on schema processing, minimizing expected losses, and emphasizing certain genetic operators has failed to provide robust optimization performance. Recently, fitness distribution analysis has been proposed as an alternative tool for exploring operator behavior and designing efficient evolutionary computations. For example, the step size of a single parent variation operator, such as the Gaussian mutation operator, determines the corresponding probability of finding better solutions and the expected improvement that will be obtained. The paper analyses the utility of Gaussian, Cauchy, and mean mutation operators when a parent is located near a local extrema of a continuous objective function that is to be optimized.

Sequencing of DNA is among the most important tasks in molecular biology. DNA chips are considered to be a more rapid alternative to more common gel-based methods of sequencing. Previously, we demonstrated the reconstruction of DNA sequence information from a simulated DNA chip using evolutionary programming. The research presented here extends this work by relaxing several assumptions adopted in our initial investigation. We also examine the relationship between base composition of the target sequence and the useful set of probes required to decipher the target on a DNA chip. Comments regarding the nature of the optimal ratio for the target and probe lengths are offered. Our results go further to suggest that evolutionary computation is well-suited to address the sequence reconstruction problem.

Niche exploitation by an organism cumulatively results from its existing adaptations and phylogenetic history. The biological sonar of dolphins is an adaptation for object (e.g. prey or obstacle) detection and classification in visually limited environments. Current biomimetic modeling of echo discrimination by dolphins emphasizes the mechanical and neurological filtering of the peripheral auditory system prior to central nervous system processing of echoes. Anatomical data from, and psychoacoustic and neurophysiological experiments performed on bottlenose dolphins (Tursiops truncatus) have determined the structure of auditory tuning curves for a few tested frequencies. However, an optimal filter set has yet to be developed that demonstrates comparable frequency-dependent sensitivity across the range of dolphin hearing. Evolutionary computation techniques are employed to optimize the sensitivity of filters to that observed in the bottlenose dolphin, by seeding the population with bounded filter parameters and evolving the number, shape, and frequency distribution of individual filters. Comparisons of evolved and known biological tuning curves are discussed.

Different variants of evolutionary programming (EP) have been proposed recently to determine the order and parameters of time series models. Unlike conventional algorithms, the model order and coefficients are evolved simultaneously in evolutionary algorithms. In this paper, the performance of the different types of evolutionary algorithms was tested on standard problems. In particular, the algorithms considered in this paper were evolutionary programming, fast evolutionary programming and modified simulated evolutionary optimization, EP was used to evolve both the order and coefficients of the reduced parameter bilinear model and recurrent bilinear perceptron. These models were used for one-step prediction of four well investigated time series, namely the sunspot series, the Mackey-Glass series, the laser data series and the astrophysical data series. The performance of the algorithms was compared on the basis of the order of the model evolved and normalized mean square error. Fast evolutionary programming with recurrent bilinear perceptrons produced the best models with fewer parameters and lower normalized mean square error.

Mathematical games provide a framework for studying intelligent behavior in models of real-world settings or restricted domains. The obstacle comes in choosing the appropriate representation and learning algorithm. Neural networks and evolutionary algorithms provide useful means for addressing these issues. This paper describes efforts to hybridize neural and evolutionary computation to learn appropriate strategies in zero- and nonzero-sum games, including the iterated prisoner's dilemma, tic-tac-toe, and checkers. With respect to checkers, the evolutionary algorithm was able to discover a neural network that can be used to play at a near-expert level without injecting expert knowledge about how to play the game. The implications of evolutionary learning with respect to machine intelligence are also discussed. It is argued that evolution provides the framework for explaining naturally occurring intelligent entities and can be used to design machines that are also capable of intelligent behavior.

Complex adaptive systems have historically been studied using simplifications that mandate deterministic interactions between agents or instead treat their interactions only with regard to their statistical expectation. This has led to an anticipation, even in the case of agents employing inductive reasoning in light of limited information, that such systems may have equilibria that can be predicted a priori. This hypothesis is tested here using a simulation of a simple market economy in which each agent's behavior is based on the result of an iterative evolutionary process of variation and selection applied to competing internal models of its environment. The results indicate no tendency for convergence to stability or a long-term equilibrium and highlight fundamental differences between deterministic and stochastic models of complex adaptive systems.

info:eu-repo/semantics/published

An experiment was conducted where neural networks compete for survival in an evolving population based on their ability to play checkers. More specifically, multilayer feedforward neural networks were used to evaluate alternative board positions and games were played using a minimax search strategy. At each generation, the extant neural networks were paired in competitions and selection was used to eliminate those that performed poorly relative to other networks. Offspring neural networks were created from the survivors using random variation of all weights and bias terms. After a series of 250 generations, the best-evolved neural network was played against human opponents in a series of 90 games on an internet website. The neural network was able to defeat two expert-level players and played to a draw against a master. The final rating of the neural network placed it in the "Class A" category using a standard rating system. Of particular importance in the design of the experiment was the fact that no features beyond the piece differential were given to the neural networks as a priori knowledge. The process of evolution was able to extract all of the additional information required to play at this level of competency. It accomplished this based almost solely on the feedback offered in the final aggregated outcome of each game played (i.e., win, lose, or draw). This procedure stands in marked contrast to the typical artifice of explicitly injecting expert knowledge into a game-playing program.

This letter presents a new algorithm, fast evolutionary programming (FEP), for determining the model orders and parameters of reduced parameter bilinear (RPBL) models used for predicting nonlinear and chaotic time series. FEP is a variant of the conventional evolutionary programming (EP) algorithm with a new mutation operator. This new mutation operator enhances EP's ability to escape from local minima resulting in a significantly faster convergence to the optimal solution. Both the model order and the parameters are evolved simultaneously. Experimental results on the sunspot series and Mackey-Glass series show that FEP is capable of determining the optimal model order and, in comparison with conventional evolutionary programming, evolves models with lower normalized mean squared error.

Traditional investigations with evolutionary programming for continuous parameter optimization problems have used a single mutation operator with a parametrized probability density function (PDF), typically a Gaussian. Using a variety of mutation operators that can be combined during evolution to generate PDFs of varying shapes could hold the potential for producing better solutions with less computational effort. In view of this, a linear combination of Gaussian and Cauchy mutations is proposed. Simulations indicate that both the adaptive and nonadaptive versions of this operator are capable of producing solutions that are statistically as good as, or better, than those produced when using Gaussian or Cauchy mutations alone.

An evolutionary programming procedure is used for optimizing computer programs in the form of symbolic expressions. Six tree mutation operators are proposed. Recombination operators such as crossover are not included. The viability and efficiency of the method is extensively investigated on a set of well-studied problems. The evidence indicates that the technique is not only viable but is indeed capable of evolving good computer programs. The results compare well with other evolutionary methods that rely on crossover to solve the same problems.