nils-herrmann/clean_scirepeval huggingface dataset:
Pairwise Clustering and Graphical Models

Significant progress in clustering has been achieved by algorithms that are based on pairwise affinities between the datapoints. In particular, spectral clustering methods have the advantage of being able to divide arbitrarily shaped clusters and are based on efficient eigenvector calculations. However, spectral methods lack a straightforward probabilistic interpretation which makes it difficult to automatically set parameters using training data. 
 
In this paper we use the previously proposed typical cut framework for pairwise clustering. We show an equivalence between calculating the typical cut and inference in an undirected graphical model. We show that for clustering problems with hundreds of datapoints exact inference may still be possible. For more complicated datasets, we show that loopy belief propagation (BP) and generalized belief propagation (GBP) can give excellent results on challenging clustering problems. We also use graphical models to derive a learning algorithm for affinity matrices based on labeled data.
Learning to Perceive Transparency from the Statistics of Natural Scenes

Certain simple images are known to trigger a percept of transparency: the input image I is perceived as the sum of two images I(x,y) = I1(x,y) + I2(x,y). This percept is puzzling. First, why do we choose the "more complicated" description with two images rather than the "simpler" explanation I(x,y) = I1(x,y) + 0 ? Second, given the infinite number of ways to express I as a sum of two images, how do we compute the "best" decomposition? 
 
Here we suggest that transparency is the rational percept of a system that is adapted to the statistics of natural scenes. We present a probabilistic model of images based on the qualitative statistics of derivative filters and "corner detectors" in natural scenes and use this model to find the most probable decomposition of a novel image. The optimization is performed using loopy belief propagation. We show that our model computes perceptually "correct" decompositions on synthetic images and discuss its application to real images.
Maximum Likelihood and the Information Bottleneck

The information bottleneck (IB) method is an information-theoretic formulation for clustering problems. Given a joint distribution p(x, y), this method constructs a new variable T that defines partitions over the values of X that are informative about Y. Maximum likelihood (ML) of mixture models is a standard statistical approach to clustering problems. In this paper, we ask: how are the two methods related? We define a simple mapping between the IB problem and the ML problem for the multinomial mixture model. We show that under this mapping the problems are strongly related. In fact, for uniform input distribution over or for large sample size, the problems are mathematically equivalent. Specifically, in these cases, every fixed point of the IB-functional defines a fixed point of the (log) likelihood and vice versa. Moreover, the values of the functionals at the fixed points are equal under simple transformations. As a result, in these cases, every algorithm that solves one of the problems, induces a solution for the other.
Approximate Inference and Protein-Folding

Side-chain prediction is an important subtask in the protein-folding problem. We show that finding a minimal energy side-chain configuration is equivalent to performing inference in an undirected graphical model. The graphical model is relatively sparse yet has many cycles. We used this equivalence to assess the performance of approximate inference algorithms in a real-world setting. Specifically we compared belief propagation (BP), generalized BP (GBP) and naive mean field (MF). 
 
In cases where exact inference was possible, max-product BP always found the global minimum of the energy (except in few cases where it failed to converge), while other approximation algorithms of similar complexity did not. In the full protein data set, max-product BP always found a lower energy configuration than the other algorithms, including a widely used protein-folding software (SCWRL).
Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology

Graphical models, such as Bayesian networks and Markov random fields, represent statistical dependencies of variables by a graph. Local belief propagation rules of the sort proposed by Pearl (1988) are guaranteed to converge to the correct posterior probabilities in singly connected graphs. Recently, good performance has been obtained by using these same rules on graphs with loops, a method we refer to as loopy belief propagation. Perhaps the most dramatic instance is the near Shannon-limit performance of Turbo codes, whose decoding algorithm is equivalent to loopy propagation. Except for the case of graphs with a single loop, there has been little theoretical understanding of loopy propagation. Here we analyze belief propagation in networks with arbitrary topologies when the nodes in the graph describe jointly gaussian random variables. We give an analytical formula relating the true posterior probabilities with those calculated using loopy propagation. We give sufficient conditions for convergence and show that when belief propagation converges, it gives the correct posterior means for all graph topologies, not just networks with a single loop. These results motivate using the powerful belief propagation algorithm in a broader class of networks and help clarify the empirical performance results.
On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs

Graphical models, such as Bayesian networks and Markov random fields (MRFs), represent statistical dependencies of variables by a graph. The max-product "belief propagation" algorithm is a local-message-passing algorithm on this graph that is known to converge to a unique fixed point when the graph is a tree. Furthermore, when the graph is a tree, the assignment based on the fixed point yields the most probable values of the unobserved variables given the observed ones. Good empirical performance has been obtained by running the max-product algorithm (or the equivalent min-sum algorithm) on graphs with loops, for applications including the decoding of "turbo" codes. Except for two simple graphs (cycle codes and single-loop graphs) there has been little theoretical understanding of the max-product algorithm on graphs with loops. Here we prove a result on the fixed points of max-product on a graph with arbitrary topology and with arbitrary probability distributions (discrete- or continuous-valued nodes). We show that the assignment based on a fixed point is a "neighborhood maximum" of the posterior probability: the posterior probability of the max-product assignment is guaranteed to be greater than all other assignments in a particular large region around that assignment. The region includes all assignments that differ from the max-product assignment in any subset of nodes that form no more than a single loop in the graph. In some graphs, this neighborhood is exponentially large. We illustrate the analysis with examples.
Beyond Junctions: Nonlocal form Constraints on Motion Interpretation

Because of the aperture problem, local motion measurements must be combined across space. However, not all motions should be combined. Some arise from distinct objects and should be segregated, and some are due to occlusion and should be discounted because they are spurious. Humans have little difficulty ignoring spurious motions at occlusions and correctly integrating object motion, and are evidently making use of form information to do so. There is a large body of theoretical and empirical evidence supporting the importance of form processes involving junctions in the way motion is integrated. To assess the role of more complex form analysis, we manipulated nonlocal form cues that could be varied independently of local junctions. Using variants on diamond and plaid stimuli used in previous studies, we found that manipulations distant from the junctions themselves could cause large changes in motion interpretation. Nonlocal information often overrides the integration decisions that would be expected from local cues. The mechanisms implicated appear to involve surface segmentation, amodal completion, and depth ordering.
Deriving intrinsic images from image sequences

Intrinsic images are a useful midlevel description of scenes proposed by H.G. Barrow and J.M. Tenenbaum (1978). An image is de-composed into two images: a reflectance image and an illumination image. Finding such a decomposition remains a difficult problem in computer vision. We focus on a slightly, easier problem: given a sequence of T images where the reflectance is constant and the illumination changes, can we recover T illumination images and a single reflectance image? We show that this problem is still imposed and suggest approaching it as a maximum-likelihood estimation problem. Following recent work on the statistics of natural images, we use a prior that assumes that illumination images will give rise to sparse filter outputs. We show that this leads to a simple, novel algorithm for recovering reflectance images. We illustrate the algorithm's performance on real and synthetic image sequences.
The Factored Frontier Algorithm for Approximate Inference in DBNs

The Factored Frontier (FF) algorithm is a simple approximate inference algorithm for Dynamic Bayesian Networks (DBNs). It is very similar to the fully factorized version of the Boyen-Koller (BK) algorithm, but instead of doing an exact update at every step followed by marginalisation (projection), it always works with factored distributions. Hence it can be applied to models for which the exact update step is intractable. We show that FF is equivalent to (one iteration of) loopy belief propagation (LBP) on the original DBN, and that BK is equivalent (to one iteration of) LBP on a DBN where we cluster some of the nodes. We then show empirically that by iterating more than once, LBP can improve on the accuracy of both FF and BK. We compare these algorithms on two real-world DBNs: the first is a model of a water treatment plant, and the second is a coupled HMM, used to model freeway traffic.
Correctness of Local Probability Propagation in Graphical Models with Loops

Graphical models, such as Bayesian networks and Markov networks, represent joint distributions over a set of variables by means of a graph. When the graph is singly connected, local propagation rules of the sort proposed by Pearl (1988) are guaranteed to converge to the correct posterior probabilities. Recently a number of researchers have empirically demonstrated good performance of these same local propagation schemes on graphs with loops, but a theoretical understanding of this performance has yet to be achieved. For graphical models with a single loop, we derive an analytical relationship between the probabilities computed using local propagation and the correct marginals. Using this relationship we show a category of graphical models with loops for which local propagation gives rise to provably optimal maximum a posteriori assignments (although the computed marginals will be incorrect). We also show how nodes can use local information in the messages they receive in order to correct their computed marginals. We discuss how these results can be extended to graphical models with multiple loops and show simulation results suggesting that some properties of propagation on single-loop graphs may hold for a larger class of graphs. Specifically we discuss the implication of our results for understanding a class of recently proposed error-correcting codes known as turbo codes.
Adventures with Gelatinous Ellipses—Constraints on Models of Human Motion Analysis

An ellipse rotating rigidly about its center may appear to rotate rigidly or to deform nonrigidly so that it appears gelatinous. We use this ambiguous stimulus to study how motion information is propagated across space. We find that features that are quite far from the contour of the ellipse may have a strong influence on the percept of the ellipse, provided they move in a way consistent with the motion of the ellipse. We show that the percept cannot be accounted for by computational models that pool constraints over a local area only, or by models that propagate information along contours, or by models that indiscriminately propagate information across space. However, the percept can be accounted for by a class of models that assume smoothness in a layered representation.
Loopy Belief Propagation for Approximate Inference: An Empirical Study

Recently, researchers have demonstrated that "loopy belief propagation" -- the use of Pearl's polytree algorithm in a Bayesian network with loops -- can perform well in the context of error-correcting codes. The most dramatic instance of this is the near Shannon-limit performance of "Turbo Codes" -- codes whose decoding algorithm is equivalent to loopy belief propagation in a chain-structured Bayesian network. 
 
In this paper we ask: is there something special about the error-correcting code context, or does loopy propagation work as an approximate inference scheme in a more general setting? We compare the marginals computed using loopy propagation to the exact ones in four Bayesian network architectures, including two real-world networks: ALARM and QMR. We find that the loopy beliefs often converge and when they do, they give a good approximation to the correct marginals. However, on the QMR network, the loopy beliefs oscillated and had no obvious relationship to the correct posteriors. We present some initial investigations into the cause of these oscillations, and show that some simple methods of preventing them lead to the wrong results.
Segmentation using eigenvectors: a unifying view

Automatic grouping and segmentation of images remains a challenging problem in computer vision. Recently, a number of authors have demonstrated good performance on this task using methods that are based on eigenvectors of the affinity matrix. These approaches are extremely attractive in that they are based on simple eigendecomposition algorithms whose stability is well understood. Nevertheless, the use of eigendecompositions in the context of segmentation is far from well understood. In this paper we give a unified treatment of these algorithms, and show the close connections between them while highlighting their distinguishing features. We then prove results on eigenvectors of block matrices that allow us to analyze the performance of these algorithms in simple grouping settings. Finally, we use our analysis to motivate a variation on the existing methods that combines aspects from different eigenvector segmentation algorithms. We illustrate our analysis with results on real and synthetic images.
Slow and Smooth: A Bayesian theory for the combination of local motion signals in human vision

In order to estimate the motion of an object, the visual system needs to combine multiple local measurements, each of which carries some degree of ambiguity. We present a model of motion perception whereby measurements from di erent image regions are combined according to a Bayesian estimator | the estimated motion maximizes the posterior probability assuming a prior favoring slow and smooth velocities. In reviewing a large number of previously published phenomena we nd that the Bayesian estimator predicts a wide range of psychophysical results. This suggests that the seemingly complex set of illusions arise from a single computational strategy that is optimal under reasonable assumptions.  This report describes research done at the Center for Biological and Computational Learning and the Department of Brain and Cognitive Sciences of the Massachusetts Institute of Technology. Support for the Center is provided in part by a grant from the National Science Foundation under contract ASC{9217041. The work was also supported by NEI R01 EY11005 to E. H. Adelson
Phase Transitions and the Perceptual Organization of Video Sequences

Estimating motion in scenes containing multiple moving objects remains a difficult problem in computer vision. A promising approach to this problem involves using mixture models, where the motion of each object is a component in the mixture. However, existing methods typically require specifying in advance the number of components in the mixture, i.e. the number of objects in the scene. 
 
Here we show that the number of objects can be estimated automatically in a maximum likelihood framework, given an assumption about the level of noise in the video sequence. We derive analytical results showing the number of models which maximize the likelihood for a given noise level in a given sequence. We illustrate these results on a real video sequence, showing how the phase transitions correspond to different perceptual organizations of the scene.
Smoothness in layers: Motion segmentation using nonparametric mixture estimation

Grouping based on common motion, or "common fate" provides a powerful cue for segmenting image sequences. Recently a number of algorithms have been developed that successfully perform motion segmentation by assuming that the motion of each group can be described by a low dimensional parametric model (e.g. affine). Typically the assumption is that motion segments correspond to planar patches in 3D undergoing rigid motion. Here we develop an alternative approach, where the motion of each group is described by a smooth dense flow field and the stability of the estimation is ensured by means of a prior distribution on the class of flow fields. We present a variant of the EM algorithm that can segment image sequences by fitting multiple smooth flow fields to the spatiotemporal data. Using the method of Green's functions, we show how the estimation of a single smooth flow field can be performed in closed form, thus making the multiple model estimation computationally feasible. Furthermore, the number of models is estimated automatically using similar methods to those used in the parametric approach. We illustrate the algorithm's performance on synthetic and real image sequences.
Interaction of Multiple Surface Cues in Motion Grouping

A rotating ellipse and a translating ogive may appear rigid or nonrigid depending on their shapes. By placing moving dots (‘satellites’) in the space surrounding the contour one can cause the percept to switch between rigid and nonrigid, depending on how the dots move. We have studied how multiple surface cues can influence this grouping effect. One set of displays consisted of the ambiguous contour and a group of consistently moving satellites. We found that under this condition the grouping was extremely robust. The influence of the satellites on the perceived rigidity of the contour remained powerful when they were moved far away from the contour and even when they were placed at a different stereoscopic depth plane. A second set of displays consisted of the ambiguous contour and two groups of satellites: one group moving rigidly and the other nonrigidly. In these displays we found a strong effect of stereo and distance. One could cause the percept to switch from rigid to nonrigid by manipulating the relative distances of the display elements or the relative disparities. We discuss how these results can be accounted for in a computational model that combines form and motion information in a robust estimation framework.
Interpreting Images by Propagating Bayesian Beliefs

A central theme of computational vision research has been the realization that reliable estimation of local scene properties requires propagating measurements across the image. Many authors have therefore suggested solving vision problems using architectures of locally connected units updating their activity in parallel. Unfortunately, the convergence of traditional relaxation methods on such architectures has proven to be excruciatingly slow and in general they do not guarantee that the stable point will be a global minimum. 
 
In this paper we show that an architecture in which Bayesian Beliefs about image properties are propagated between neighboring units yields convergence times which are several orders of magnitude faster than traditional methods and avoids local minima. In particular our architecture is non-iterative in the sense of Marr : at every time step, the local estimates at a given location are optimal given the information which has already been propagated to that location. We illustrate the algorithm's performance on real images and compare it to several existing methods.
A unified mixture framework for motion segmentation: incorporating spatial coherence and estimating the number of models

Describing a video sequence in terms of a small number of coherently moving segments is useful for tasks ranging from video compression to event perception. A promising approach is to view the motion segmentation problem in a mixture estimation framework. However, existing formulations generally use only the motion, data and thus fail to make use of static cues when segmenting the sequence. Furthermore, the number of models is either specified in advance or estimated outside the mixture model framework. In this work we address both of these issues. We show how to add spatial constraints to the mixture formulations and present a variant of the EM algorithm that males use of both the form and the motion constraints. Moreover this algorithm estimates the number of segments given knowledge about the level of model failure expected in the sequence. The algorithm's performance is illustrated on synthetic and real image sequences.
WideGain access system

We present a commercial access and transmission fiber optic system optimized for the fiber to the curb (FTTC) and fiber to the office (FTTO) applications. The system concept is based on the incorporation of time division multiplexing (TDM), subcarrier multiple access (SCMA) and coarse wavelength division multiplexing (WDM). This system architecture provides wide applications flexibility and graceful possibilities for the provision of future advanced services on a passive optical network (PON).