We introduce a new type of fully computable problems, for DSS dedicated to maximal spanning tree problems, based on deduction and choice: preferential consistency problems. To show its interest, we describe a new compact representation of preferences specific to spanning trees, identifying an efficient maximal spanning tree sub-problem. Next, we compare this problem with the Pareto-based multiobjective one. And at last, we propose an efficient algorithm solving the associated preferential consistency problem.

Targeting at sparse learning, we construct Banach spaces B of functions on an input space X with the properties that (1) B possesses an l1 norm in the sense that it is isometrically isomorphic to the Banach space of integrable functions on X with respect to the counting measure; (2) point evaluations are continuous linear functionals on B and are representable through a bilinear form with a kernel function; (3) regularized learning schemes on B satisfy the linear representer theorem. Examples of kernel functions admissible for the construction of such spaces are given.

Given a collection of objects and an associated similarity measure, the all-pairs similarity search problem asks us to find all pairs of objects with similarity greater than a certain user-specified threshold. Locality-sensitive hashing (LSH) based methods have become a very popular approach for this problem. However, most such methods only use LSH for the first phase of similarity search - i.e. efficient indexing for candidate generation. In this paper, we present BayesLSH, a principled Bayesian algorithm for the subsequent phase of similarity search - performing candidate pruning and similarity estimation using LSH. A simpler variant, BayesLSH-Lite, which calculates similarities exactly, is also presented. BayesLSH is able to quickly prune away a large majority of the false positive candidate pairs, leading to significant speedups over baseline approaches. For BayesLSH, we also provide probabilistic guarantees on the quality of the output, both in terms of accuracy and recall. Finally, the quality of BayesLSH's output can be easily tuned and does not require any manual setting of the number of hashes to use for similarity estimation, unlike standard approaches. For two state-of-the-art candidate generation algorithms, AllPairs and LSH, BayesLSH enables significant speedups, typically in the range 2x-20x for a wide variety of datasets.

In this correspondence, we obtain exact recovery conditions for regularized modified basis pursuit (reg-mod-BP) and discuss when the obtained conditions are weaker than those for modified-CS or for basis pursuit (BP). The discussion is also supported by simulation comparisons. Reg-mod-BP provides a solution to the sparse recovery problem when both an erroneous estimate of the signal's support, denoted by $T$, and an erroneous estimate of the signal values on $T$ are available.

Large bilingual parallel texts (also known as bitexts) are usually stored in a compressed form, and previous work has shown that they can be more efficiently compressed if the fact that the two texts are mutual translations is exploited. For example, a bitext can be seen as a sequence of biwords ---pairs of parallel words with a high probability of co-occurrence--- that can be used as an intermediate representation in the compression process. However, the simple biword approach described in the literature can only exploit one-to-one word alignments and cannot tackle the reordering of words. We therefore introduce a generalization of biwords which can describe multi-word expressions and reorderings. We also describe some methods for the binary compression of generalized biword sequences, and compare their performance when different schemes are applied to the extraction of the biword sequence. In addition, we show that this generalization of biwords allows for the implementation of an efficient algorithm to look on the compressed bitext for words or text segments in one of the texts and retrieve their counterpart translations in the other text ---an application usually referred to as translation spotting--- with only some minor modifications in the compression algorithm.

We combine Bayesian networks (BNs) and structural reliability methods (SRMs) to create a new computational framework, termed enhanced Bayesian network (eBN), for reliability and risk analysis of engineering structures and infrastructure. BNs are efficient in representing and evaluating complex probabilistic dependence structures, as present in infrastructure and structural systems, and they facilitate Bayesian updating of the model when new information becomes available. On the other hand, SRMs enable accurate assessment of probabilities of rare events represented by computationally demanding, physically-based models. By combining the two methods, the eBN framework provides a unified and powerful tool for efficiently computing probabilities of rare events in complex structural and infrastructure systems in which information evolves in time. Strategies for modeling and efficiently analyzing the eBN are described by way of several conceptual examples. The companion paper applies the eBN methodology to example structural and infrastructure systems.

This paper describes a novel method to approximate the polynomial coefficients of regression functions, with particular interest on multi-dimensional classification. The derivation is simple, and offers a fast, robust classification technique that is resistant to over-fitting.

Approximating non-linear kernels using feature maps has gained a lot of interest in recent years due to applications in reducing training and testing times of SVM classifiers and other kernel based learning algorithms. We extend this line of work and present low distortion embeddings for dot product kernels into linear Euclidean spaces. We base our results on a classical result in harmonic analysis characterizing all dot product kernels and use it to define randomized feature maps into explicit low dimensional Euclidean spaces in which the native dot product provides an approximation to the dot product kernel with high confidence.

Over the last decade, we have seen an increasing demand for robotscapable of coexisting with people. Enabling robots to operatesafely and effectively alongside human partners withinunstructured environments poses interesting research challengesthat broadly span the field of artificial intelligence. This paperpreviews some of the challenges that we faced in developing arobot "envoy" that operates for extended periods of timethroughout an office-like environment, assisting human occupantswith everyday activities that include greeting and escortingguests as well as retrieving and delivering objects. We see threeskill areas as critical for the robot to effectively perform thesetasks. The first is shared situational awareness-the robot mustinterpret its environment through a world model that is sharedwith its human partners. Secondly, the robot should act in a safe,predictable manner and be capable of intuitive interaction withpeople, through such means as natural language speech. Thirdly,the robot, which we initially treat as a rookie, shouldefficiently utilize information provided by human partners,requesting assistance when necessary and learning from suchassistance to become more competent with time.

Open query answering is the idea of answering queries that are not given using the vocabulary of the queried knowledge base but instead the vocabulary of the inquirer. Many aspects of open query answering can be tackled through the combination of human effort with algorithmic techniques. In this paper we explore its applicability to crowdsourcing, using a framework in which human and computational intelligence can co-exist by augmenting existing Linked Data and Linked Service technology with crowdsourcing functionality. We analyze how the task can be decomposed and translated into Mechanical Turk projects in order to achieve this vision.