This paper presents a Bayesian generative model for dependent Cox point processes, alongside an efficient inference scheme which scales as if the point processes were modelled independently. We can handle missing data naturally, infer latent structure, and cope with large numbers of observed processes. A further novel contribution enables the model to work effectively in higher dimensional spaces. Using this method, we achieve vastly improved predictive performance on both 2D and 1D real data, validating our structured approach.

We present new algorithms for detecting the emergence of a community in large networks from sequential observations. The networks are modeled using Erdos-Renyi random graphs with edges forming between nodes in the community with higher probability. Based on statistical changepoint detection methodology, we develop three algorithms: the Exhaustive Search (ES), the mixture, and the Hierarchical Mixture (H-Mix) methods. Performance of these methods is evaluated by the average run length (ARL), which captures the frequency of false alarms, and the detection delay. Numerical comparisons show that the ES method performs the best; however, it is exponentially complex. The mixture method is polynomially complex by exploiting the fact that the size of the community is typically small in a large network. However, it may react to a group of active edges that do not form a community. This issue is resolved by the H-Mix method, which is based on a dendrogram decomposition of the network. We present an asymptotic analytical expression for ARL of the mixture method when the threshold is large. Numerical simulation verifies that our approximation is accurate even in the non-asymptotic regime. Hence, it can be used to determine a desired threshold efficiently. Finally, numerical examples show that the mixture and the H-Mix methods can both detect a community quickly with a lower complexity than the ES method.

This paper considers the problem of clustering a partially observed unweighted graph---i.e., one where for some node pairs we know there is an edge between them, for some others we know there is no edge, and for the remaining we do not know whether or not there is an edge. We want to organize the nodes into disjoint clusters so that there is relatively dense (observed) connectivity within clusters, and sparse across clusters. We take a novel yet natural approach to this problem, by focusing on finding the clustering that minimizes the number of "disagreements"---i.e., the sum of the number of (observed) missing edges within clusters, and (observed) present edges across clusters. Our algorithm uses convex optimization; its basis is a reduction of disagreement minimization to the problem of recovering an (unknown) low-rank matrix and an (unknown) sparse matrix from their partially observed sum. We evaluate the performance of our algorithm on the classical Planted Partition/Stochastic Block Model. Our main theorem provides sufficient conditions for the success of our algorithm as a function of the minimum cluster size, edge density and observation probability; in particular, the results characterize the tradeoff between the observation probability and the edge density gap. When there are a constant number of clusters of equal size, our results are optimal up to logarithmic factors.

Learning Structured Outputs from Partial Labels using Forest Ensemble Truyen Tran, Dinh Phung, Svetha V enkatesh Centre for Pattern Recognition and Data Analytics Deakin University, Australia Abstract Learning structured outputs with general structures is computationally challenging, except for tree-structured models. Thus we propose an efficient boosting-based algorithm AdaBoost.MRF for this task. The idea is based on the realization that a graph is a superimposition of trees. Different from most existing work, our algorithm can handle partial labelling, and thus is particularly attractive in practice where reliable labels are often sparsely observed. In addition, our method works exclusively on trees and thus is guaranteed to converge. We apply the AdaBoost.MRF algorithm to an indoor video surveillance scenario, where activities are modelled at multiple levels. 1 Introduction There has been a growing research interest in developing probabilistic temporal graphical models for recognising human activities from sensory data. In this paper we address an important aspect of the problem in that there are multiple levels of abstraction, that is, an activity is often composed of several sub-activities. A popular approach to deal with such a hierarchical nature is to build a cascaded model: each level is modelled separately, and the output of the lower levels is subsequently used as the input for the upper levels [20]. This approach is sub-optimal because the information at the higher level is often very discriminative to infer about the lower levels, but it is not modelled. Moreover, the layered approach often suffers from the so-called cascading error problem, as the error introduced from the lower level will propagate to higher tasks. A better and more holistic approach is to build a joint representation at all layers. Emerging methods include generative/directed models such as abstract hidden Markov models (AH-MMs) [4], hierarchical HMMs [19], dynamic Bayesian networks [10], and their discriminative/undirected counterparts such as hierarchical conditional random field (HCRF) [17], and dynamic CRF (DCRF) [28].

We study the problem of collaborative filtering where ranking information is available. Focusing on the core of the collaborative ranking process, the user and their community, we propose new models for representation of the underlying permutations and prediction of ranks. The first approach is based on the assumption that the user makes successive choice of items in a stage-wise manner. In particular, we extend the Plackett-Luce model in two ways - introducing parameter factoring to account for user-specific contribution, and modelling the latent community in a generative setting. The second approach relies on log-linear parameterisation, which relaxes the discrete-choice assumption, but makes learning and inference much more involved. We propose MCMC-based learning and inference methods and derive linear-time prediction algorithms.

How to forecast next year's portfolio-wide credit default rate based on last year's default observations and the current score distribution? A classical approach to this problem consists of fitting a mixture of the conditional score distributions observed last year to the current score distribution. This is a special (simple) case of a finite mixture model where the mixture components are fixed and only the weights of the components are estimated. The optimum weights provide a forecast of next year's portfolio-wide default rate. We point out that the maximum-likelihood (ML) approach to fitting the mixture distribution not only gives an optimum but even an exact fit if we allow the mixture components to vary but keep their density ratio fix. From this observation we can conclude that the standard default rate forecast based on last year's conditional default rates will always be located between last year's portfolio-wide default rate and the ML forecast for next year. As an application example, then cost quantification is discussed. We also discuss how the mixture model based estimation methods can be used to forecast total loss. This involves the reinterpretation of an individual classification problem as a collective quantification problem.

Dynamic scheduling problems consist of both challenging combinatorics, as found in classical scheduling problems, and stochastics due to uncertainty about the arrival times, resource requirements, and processing times of jobs. To address these two challenges, we investigate the integration of queueing theory and scheduling. The former reasons about long-run stochastic system characteristics, whereas the latter typically deals with short-term combinatorics. We investigate two simple problems to isolate the core differences and potential synergies between the two approaches: a two-machine dynamic flowshop and a flexible queueing network. We show for the first time that stability, a fundamental characteristic in queueing theory, can be applied to approaches that periodically solve combinatorial scheduling problems. We empirically demonstrate that for a dynamic flowshop, the use of combinatorial reasoning has little impact on schedule quality beyond queueing approaches. In contrast, for the more complicated flexible queueing network, a novel algorithm that combines long-term guidance from queueing theory with short-term combinatorial decision making outperforms all other tested approaches. To our knowledge, this is the first time that such a hybrid of queueing theory and scheduling techniques has been proposed and evaluated.

Weighted search was explored significantly in recent years for path-finding problems, but until now was barely considered for optimization tasks such as MPE/MAP and Weighted CSPs. An important virtue of weighted search schemes, especially in the context of anytime search, is that they are w-optimal, i.e. when terminated, they return a weight w, and a solution cost C, such that C ≤ w · C *, where C* is the optimal cost. In this paper we introduce Weighted Branch and Bound (WBB) for graphical models and provide a broad empirical evaluation of its performance compared with one of the best unweighted anytime search scheme, BRAOBB (won Pascal 2011 competition). We also compare against weighted best-first (WBF). Our results show that W BB can be superior to both unweighted BB and to weighted BF on a significant number of instances. We also illustrate the benefit of weighted search in providing suboptimality relative error bounds.

Unit propagation (UP) based method are widely used in Branch and Bound (BnB) Max-SAT solvers for detecting disjoint inconsistent subsets (IS) during the lower bound (LB) estimation. UP consists in assigning to true (propagating) all the literals which appear in unit clauses. The existing implementations of UP only consider the first unit clause causing the assignment of each variable, thus the propagations must be done and undone chronologically to ensure that all the unit clauses are properly exploited. Max-SAT BnB solvers transforms the formulas to ensure IS disjointness. These transformations remove clauses from the formula thus propagations are frequently undone. Since the propagations are undone in chronological order, many useless unassignments and reassignments are performed. We propose in this paper a new unit propagation scheme which considers all the unit clauses causing the assignment of the variables by UP. This new scheme allows to undo propagations in a non-chronological way and thus it reduces the number of redundant propagation steps made by BnB solvers. We also show how the information available with this new scheme can be used to influence the characteristics of the IS built by BnB solvers. We propose a heuristic which aims at reducing their size, and thus improving the quality of the LB estimation. We have implemented the new propagation scheme as well as the IS building heuristic in our solver MSsolver. We present and discuss the results of the experimental study we have performed.

Many of the seminal papers in preference handling have used food preferences as motivating examples for their work. As foodies, the authors find this particularly motivating. While we think that there is both research and commercial potential in preference-based software for restaurants, we believe that serious application of the MPREF community's technology to the problem of personal preference-driven presentation of menus, seating, etc., will require significant further innovation. We broadly survey the current use of preferences in making the dining-out experience more enjoyable, and we look at the states of the art for preference representation and reasoning, and for restaurant software. We illustrate some of our points with a short story.