OpenRaiser/Intern-Atlas huggingface dataset:
Flexible Priors for Exemplar-based Clustering
Venue: arXiv cs.LG 2012
Year: 2012

Exemplar-based clustering methods have been shown to produce state-of-the-art results on a number of synthetic and real-world clustering problems. They are appealing because they offer computational benefits over latent-mean models and can handle arbitrary pairwise similarity measures between data points. However, when trying to recover underlying structure in clustering problems, tailored similarity measures are often not enough; we also desire control over the distribution of cluster sizes. Priors such as Dirichlet process priors allow the number of clusters to be unspecified while expressing priors over data partitions. To our knowledge, they have not been applied to exemplar-based models. We show how to incorporate priors, including Dirichlet process priors, into the recently introduced affinity propagation algorithm. We develop an efficient maxproduct belief propagation algorithm for our new model and demonstrate experimentally how the expanded range of clustering priors allows us to better recover true clusterings in situations where we have some information about the generating process.
Inference for Multiplicative Models
Venue: arXiv cs.AI 2012
Year: 2012

The paper introduces a generalization for known probabilistic models such as log-linear and graphical models, called here multiplicative models. These models, that express probabilities via product of parameters are shown to capture multiple forms of contextual independence between variables, including decision graphs and noisy-OR functions. An inference algorithm for multiplicative models is provided and its correctness is proved. The complexity analysis of the inference algorithm uses a more refined parameter than the tree-width of the underlying graph, and shows the computational cost does not exceed that of the variable elimination algorithm in graphical models. The paper ends with examples where using the new models and algorithm is computationally beneficial.
Hybrid Variational/Gibbs Collapsed Inference in Topic Models
Venue: arXiv cs.LG 2012
Year: 2012

Variational Bayesian inference and (collapsed) Gibbs sampling are the two important classes of inference algorithms for Bayesian networks. Both have their advantages and disadvantages: collapsed Gibbs sampling is unbiased but is also inefficient for large count values and requires averaging over many samples to reduce variance. On the other hand, variational Bayesian inference is efficient and accurate for large count values but suffers from bias for small counts. We propose a hybrid algorithm that combines the best of both worlds: it samples very small counts and applies variational updates to large counts. This hybridization is shown to significantly improve testset perplexity relative to variational inference at no computational cost.
On Local Regret
Venue: arXiv cs.AI 2012
Year: 2012

Online learning aims to perform nearly as well as the best hypothesis in hindsight. For some hypothesis classes, though, even finding the best hypothesis offline is challenging. In such offline cases, local search techniques are often employed and only local optimality guaranteed. For online decision-making with such hypothesis classes, we introduce local regret, a generalization of regret that aims to perform nearly as well as only nearby hypotheses. We then present a general algorithm to minimize local regret with arbitrary locality graphs. We also show how the graph structure can be exploited to drastically speed learning. These algorithms are then demonstrated on a diverse set of online problems: online disjunct learning, online Max-SAT, and online decision tree learning.
An Improved WBF Algorithm for Higher-Speed Decoding of LDPC Codes
Venue: arXiv cs.IT 2012
Year: 2012

Due to the speed limitation of the conventional bit-chosen strategy in the existing weighted bit flipping algorithms, a high-speed LDPC decoder cannot be realized. To solve this problem, we propose a fast weighted bit flipping (FWBF) algorithm. Specifically, based on the stochastic error bitmap of the received vector, a partially parallel bit-choose strategy is adopted to lower the delay of choosing the bit flipped. Because of its partially parallel structure, the novel strategy can be well incorporated into the LDPC decoder [1]. The analysis of the decoding delay demonstrates that, the decoding speed can be greatly improved by adopting the proposed FWBF algorithm. Further, simulation results verify the validity of the proposed algorithm.
Hardness of Vertex Deletion and Project Scheduling
Venue: arXiv cs.CC 2012
Year: 2012

Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer $k\geq 2$ and arbitrary small $ε> 0$, the Feedback Vertex Set problem and the DAG Vertex Deletion problem are inapproximable within a factor $k-ε$ even on graphs where the vertices can be almost partitioned into $k$ solutions. This gives a more structured and therefore stronger UGC-based hardness result for the Feedback Vertex Set problem that is also simpler (albeit using the "It Ain't Over Till It's Over" theorem) than the previous hardness result. In comparison to the classical Feedback Vertex Set problem, the DAG Vertex Deletion problem has received little attention and, although we think it is a natural and interesting problem, the main motivation for our inapproximability result stems from its relationship with the classical Discrete Time-Cost Tradeoff Problem. More specifically, our results imply that the deadline version is NP-hard to approximate within any constant assuming the Unique Games Conjecture. This explains the difficulty in obtaining good approximation algorithms for that problem and further motivates previous alternative approaches such as bicriteria approximations.
Constrained multilinear detection for faster functional motif discovery
Venue: arXiv cs.DS 2012
Year: 2012

The GRAPH MOTIF problem asks whether a given multiset of colors appears on a connected subgraph of a vertex-colored graph. The fastest known parameterized algorithm for this problem is based on a reduction to the $k$-Multilinear Detection (k-MlD) problem: the detection of multilinear terms of total degree k in polynomials presented as circuits. We revisit k-MLD and define k-CMLD, a constrained version of it which reflects GRAPH MOTIF more faithfully. We then give a fast algorithm for k-CMLD. As a result we obtain faster parameterized algorithms for GRAPH MOTIF and variants of it.
Sensitivity analysis in decision circuits
Venue: arXiv cs.AI 2012
Year: 2012

Decision circuits have been developed to perform efficient evaluation of influence diagrams [Bhattacharjya and Shachter, 2007], building on the advances in arithmetic circuits for belief network inference [Darwiche,2003]. In the process of model building and analysis, we perform sensitivity analysis to understand how the optimal solution changes in response to changes in the model. When sequential decision problems under uncertainty are represented as decision circuits, we can exploit the efficient solution process embodied in the decision circuit and the wealth of derivative information available to compute the value of information for the uncertainties in the problem and the effects of changes to model parameters on the value and the optimal strategy.
Real time facial expression recognition using a novel method
Venue: arXiv cs.CV 2012
Year: 2012

This paper discusses a novel method for Facial Expression Recognition System which performs facial expression analysis in a near real time from a live web cam feed. Primary objectives were to get results in a near real time with light invariant, person independent and pose invariant way. The system is composed of two different entities trainer and evaluator. Each frame of video feed is passed through a series of steps including haar classifiers, skin detection, feature extraction, feature points tracking, creating a learned Support Vector Machine model to classify emotions to achieve a tradeoff between accuracy and result rate. A processing time of 100-120 ms per 10 frames was achieved with accuracy of around 60%. We measure our accuracy in terms of variety of interaction and classification scenarios. We conclude by discussing relevance of our work to human computer interaction and exploring further measures that can be taken.
Blind PSF estimation and methods of deconvolution optimization
Venue: arXiv cs.CV 2012
Year: 2012

We have shown that the left side null space of the autoregression (AR) matrix operator is the lexicographical presentation of the point spread function (PSF) on condition the AR parameters are common for original and blurred images. The method of inverse PSF evaluation with regularization functional as the function of surface area is offered. The inverse PSF was used for primary image estimation. Two methods of original image estimate optimization were designed basing on maximum entropy generalization of sought and blurred images conditional probability density and regularization. The first method uses balanced variations of convolution and deconvolution transforms to obtaining iterative schema of image optimization. The variations balance was defined by dynamic regularization basing on condition of iteration process convergence. The regularization has dynamic character because depends on current and previous image estimate variations. The second method implements the regularization of deconvolution optimization in curved space with metric defined on image estimate surface. It is basing on target functional invariance to fluctuations of optimal argument value. The given iterative schemas have faster convergence in comparison with known ones, so they can be used for reconstruction of high resolution images series in real time.
Control Systems: an Application to a High Energy Physics Experiment (COMPASS)
Venue: arXiv cs.SY 2012
Year: 2012

The Detector Control System (DCS) of the COMPASS experiment at CERN is presented. The experiment has a high level of complexity and flexibility and a long time of operation, that constitute a challenge for its full monitorisation and control. A strategy to use a limited number of standardised, cost-effective, industrial solutions of hardware and software was pursued. When such solutions were not available or could not be used, customised solutions were developed.
Data Mining Application to Attract Students in HEI
Venue: arXiv cs.CY 2012
Year: 2012

In the last two decades, number of Higher Education Institutions (HEI) grows in leaps and bounds. This causes a cut throat competition among these institutions while attracting the student get admission in these institutions. To make reach up to the students institution makes effort of advertisement. Similarly developing and developed both type of institution launch several services also to attract students. Most of the institutions are opened in self finance mode. So all time they feel short hand in expenditure. Now a day a number of advertisement methods are available. So it is difficult for an institution to make advertisement through all modes and launch all services at the same time due to different constraints. In this paper we use support and confidence method to find out the best way of advertisement.
Best practices for HPM-assisted performance engineering on modern multicore processors
Venue: arXiv cs.PF 2012
Year: 2012

Many tools and libraries employ hardware performance monitoring (HPM) on modern processors, and using this data for performance assessment and as a starting point for code optimizations is very popular. However, such data is only useful if it is interpreted with care, and if the right metrics are chosen for the right purpose. We demonstrate the sensible use of hardware performance counters in the context of a structured performance engineering approach for applications in computational science. Typical performance patterns and their respective metric signatures are defined, and some of them are illustrated using case studies. Although these generic concepts do not depend on specific tools or environments, we restrict ourselves to modern x86-based multicore processors and use the likwid-perfctr tool under the Linux OS.
An Analysis of the Methods Employed for Breast Cancer Diagnosis
Venue: arXiv cs.NE 2012
Year: 2012

Breast cancer research over the last decade has been tremendous. The ground breaking innovations and novel methods help in the early detection, in setting the stages of the therapy and in assessing the response of the patient to the treatment. The prediction of the recurrent cancer is also crucial for the survival of the patient. This paper studies various techniques used for the diagnosis of breast cancer. Different methods are explored for their merits and de-merits for the diagnosis of breast lesion. Some of the methods are yet unproven but the studies look very encouraging. It was found that the recent use of the combination of Artificial Neural Networks in most of the instances gives accurate results for the diagnosis of breast cancer and their use can also be extended to other diseases.
On The Recovery Performance of Single- and Multipath OLSR in Wireless Multi-Hop Networks
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we study and improve the recovery properties of single and multipath routing strategies when facing network failure situations. In particular, we focus our study on two MANET routing protocols: OLSR and its multipath extension MP-OLSR. In various wireless multi-hop network environments, especially in multiple chain topologies, we define and seek to evaluate the latency introduced by these protocols to find a new path after a link failure. Theoretical estimations and simulation results show that, under dual chain-topologies, this latency can be too long and incompatible with the needs of loss and delay constrained applications. As the source nodes cannot detect link failures immediately because of the delay incurred by the well-known nature of link state protocols in general, and of OLSR Topology Control (TC) messages in particular, these nodes keep sending packets along broken paths. We thus study the inconsistencies between the actual network topology and the nodes' own representation. After analyzing the consequences of this long latency, we seek to alleviate these problems with the introduction of adapted mechanisms. We propose three new different schemes and accordingly extend the original OLSR and MP-OLSR protocols in order to decrease the expected latency and improve the protocol performance. Simulation results show a steep decrease of the latency when using these new schemes in dual chain-topologies. We also discuss these results in terms of packet loss, end-to-end delay and overhead.
On the combinatorics of suffix arrays
Venue: arXiv cs.DS 2012
Year: 2012

We prove several combinatorial properties of suffix arrays, including a characterization of suffix arrays through a bijection with a certain well-defined class of permutations. Our approach is based on the characterization of Burrows-Wheeler arrays given in [1], that we apply by reducing suffix sorting to cyclic shift sorting through the use of an additional sentinel symbol. We show that the characterization of suffix arrays for a special case of binary alphabet given in [2] easily follows from our characterization. Based on our results, we also provide simple proofs for the enumeration results for suffix arrays, obtained in [3]. Our approach to characterizing suffix arrays is the first that exploits their relationship with Burrows-Wheeler permutations.
Cooperative localization using angle of arrival measurements: sequential algorithms and non-line-of-sight suppression
Venue: arXiv cs.NI 2012
Year: 2012

We investigate localization of a source based on angle of arrival (AoA) measurements made at a geographically dispersed network of cooperating receivers. The goal is to efficiently compute accurate estimates despite outliers in the AoA measurements due to multipath reflections in non-line-of-sight (NLOS) environments. Maximal likelihood (ML) location estimation in such a setting requires exhaustive testing of estimates from all possible subsets of "good" measurements, which has exponential complexity in the number of measurements. We provide a randomized algorithm that approaches ML performance with linear complexity in the number of measurements. The building block for this algorithm is a low-complexity sequential algorithm for updating the source location estimates under line-of-sight (LOS) environments. Our Bayesian framework can exploit the ability to resolve multiple paths in wideband systems to provide significant performance gains over narrowband systems in NLOS environments, and easily extends to accommodate additional information such as range measurements and prior information about location.
Comparing paedophile activity in different P2P systems
Venue: arXiv cs.CY 2012
Year: 2012

Peer-to-peer (P2P) systems are widely used to exchange content over the Internet. Knowledge on paedophile activity in such networks remains limited while it has important social consequences. Moreover, though there are different P2P systems in use, previous academic works on this topic focused on one system at a time and their results are not directly comparable. We design a methodology for comparing \kad and \edonkey, two P2P systems among the most prominent ones and with different anonymity levels. We monitor two \edonkey servers and the \kad network during several days and record hundreds of thousands of keyword-based queries. We detect paedophile-related queries with a previously validated tool and we propose, for the first time, a large-scale comparison of paedophile activity in two different P2P systems. We conclude that there are significantly fewer paedophile queries in \kad than in \edonkey (approximately 0.09% \vs 0.25%).
Three-User Cognitive Interference Channel: Capacity Region with Strong Interference
Venue: arXiv cs.IT 2012
Year: 2012

This study investigates the capacity region of a three-user cognitive radio network with two primary users and one cognitive user. A three-user Cognitive Interference Channel (C-IFC) is proposed by considering a three-user Interference Channel (IFC) where one of the transmitters has cognitive capabilities and knows the messages of the other two transmitters in a non-causal manner. First, two inner bounds on the capacity region of the three-user C-IFC are obtained based on using the schemes which allow all receivers to decode all messages with two different orders. Next, two sets of conditions are derived, under which the capacity region of the proposed model coincides with the capacity region of a three-user C-IFC in which all three messages are required at all receivers. Under these conditions, referred to as strong interference conditions, the capacity regions for the proposed three-user C-IFC are characterized. Moreover, the Gaussian three-user C-IFC is considered and the capacity results are derived for the Gaussian case. Some numerical examples are also provided.
Joint Reconstruction of Multi-view Compressed Images
Venue: arXiv cs.MM 2012
Year: 2012

The distributed representation of correlated multi-view images is an important problem that arise in vision sensor networks. This paper concentrates on the joint reconstruction problem where the distributively compressed correlated images are jointly decoded in order to improve the reconstruction quality of all the compressed images. We consider a scenario where the images captured at different viewpoints are encoded independently using common coding solutions (e.g., JPEG, H.264 intra) with a balanced rate distribution among different cameras. A central decoder first estimates the underlying correlation model from the independently compressed images which will be used for the joint signal recovery. The joint reconstruction is then cast as a constrained convex optimization problem that reconstructs total-variation (TV) smooth images that comply with the estimated correlation model. At the same time, we add constraints that force the reconstructed images to be consistent with their compressed versions. We show by experiments that the proposed joint reconstruction scheme outperforms independent reconstruction in terms of image quality, for a given target bit rate. In addition, the decoding performance of our proposed algorithm compares advantageously to state-of-the-art distributed coding schemes based on disparity learning and on the DISCOVER.
Improved DWT Based Watermarking Using JPEG-YCbCr
Venue: arXiv cs.CR 2012
Year: 2012

In this paper a blind, Secure, imperceptible and robust watermarking algorithm based on wavelet transform domain is proposed in which for more security, the watermark W is converted to a sequence and then a random binary sequence R of size n is adopted to encrypt the watermark, where n is the size of the watermark image. Afterwards, the encrypted watermark sequence W1 is generated by executing exclusive-OR operation on W and R. This generated watermark embeds into low frequency selected coefficients of Y channel wavelet decomposition of JPEG-YCbCr using LSB insertion technique. The experimental results show that the proposed algorithm increases the security and imperceptibility of watermark and has better robustness against wavelet compression and cropping attacks compared to the earlier work in [1].
Cyclic Codes from APN and Planar Functions
Venue: arXiv cs.IT 2012
Year: 2012

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. In this paper, almost perfect nonlinear functions and planar functions over finite fields are employed to construct a number of classes of cyclic codes. Lower bounds on the minimum weight of some classes of the cyclic codes are developed. The minimum weights of some other classes of the codes constructed in this paper are determined. The dimensions of the codes are flexible. Many of the codes presented in this paper are optimal or almost optimal in the sense that they meet some bound on linear codes. Ten open problems regarding cyclic codes from highly nonlinear functions are also presented.
On the serial connection of the regular asynchronous systems
Venue: arXiv cs.GL 2012
Year: 2012

The asynchronous systems f are multi-valued functions, representing the non-deterministic models of the asynchronous circuits from the digital electrical engineering. In real time, they map an 'admissible input' function u:R\rightarrow{0,1}^{m} to a set f(u) of 'possible states' x\inf(u), where x:R\rightarrow{0,1}^{m}. When f is defined by making use of a 'generator function' Φ:{0,1}^{n}\times{0,1}^{m}\rightarrow{0,1}^{n}, the system is called regular. The usual definition of the serial connection of systems as composition of multi-valued functions does not bring the regular systems into regular systems, thus the first issue in this study is to modify in an acceptable manner the definition of the serial connection in a way that matches regularity. This intention was expressed for the first time, without proving the regularity of the serial connection of systems, in a previous work. Our present purpose is to restate with certain corrections and prove that result.