OpenRaiser/Intern-Atlas huggingface dataset:
Mining Educational Data Using Classification to Decrease Dropout Rate of Students
Venue: arXiv cs.IR 2012
Year: 2012

In the last two decades, number of Higher Education Institutions (HEI) grows rapidly in India. Since most of the institutions are opened in private mode therefore, a cut throat competition rises among these institutions while attracting the student to got admission. This is the reason for institutions to focus on the strength of students not on the quality of education. This paper presents a data mining application to generate predictive models for engineering student's dropout management. Given new records of incoming students, the predictive model can produce short accurate prediction list identifying students who tend to need the support from the student dropout program most. The results show that the machine learning algorithm is able to establish effective predictive model from the existing student dropout data.
On Modulo-Sum Computation over an Erasure Multiple Access Channel
Venue: arXiv cs.IT 2012
Year: 2012

We study computation of a modulo-sum of two binary source sequences over a two-user erasure multiple access channel. The channel is modeled as a binary-input, erasure multiple access channel, which can be in one of three states - either the channel output is a modulo-sum of the two input symbols, or the channel output equals the input symbol on the first link and an erasure on the second link, or vice versa. The associated state sequence is independent and identically distributed. We develop a new upper bound on the sum-rate by revealing only part of the state sequence to the transmitters. Our coding scheme is based on the compute and forward and the decode and forward techniques. When a (strictly) causal feedback of the channel state is available to the encoders, we show that the modulo-sum capacity is increased. Extensions to the case of lossy reconstruction of the modulo-sum and to channels involving additional states are also treated briefly.
Learning Inclusion-Optimal Chordal Graphs
Venue: arXiv cs.LG 2012
Year: 2012

Chordal graphs can be used to encode dependency models that are representable by both directed acyclic and undirected graphs. This paper discusses a very simple and efficient algorithm to learn the chordal structure of a probabilistic model from data. The algorithm is a greedy hill-climbing search algorithm that uses the inclusion boundary neighborhood over chordal graphs. In the limit of a large sample size and under appropriate hypotheses on the scoring criterion, we prove that the algorithm will find a structure that is inclusion-optimal when the dependency model of the data-generating distribution can be represented exactly by an undirected graph. The algorithm is evaluated on simulated datasets.
Identifying Optimal Sequential Decisions
Venue: arXiv cs.AI 2012
Year: 2012

We consider conditions that allow us to find an optimal strategy for sequential decisions from a given data situation. For the case where all interventions are unconditional (atomic), identifiability has been discussed by Pearl & Robins (1995). We argue here that an optimal strategy must be conditional, i.e. take the information available at each decision point into account. We show that the identification of an optimal sequential decision strategy is more restrictive, in the sense that conditional interventions might not always be identified when atomic interventions are. We further demonstrate that a simple graphical criterion for the identifiability of an optimal strategy can be given.
Strategy Selection in Influence Diagrams using Imprecise Probabilities
Venue: arXiv cs.AI 2012
Year: 2012

This paper describes a new algorithm to solve the decision making problem in Influence Diagrams based on algorithms for credal networks. Decision nodes are associated to imprecise probability distributions and a reformulation is introduced that finds the global maximum strategy with respect to the expected utility. We work with Limited Memory Influence Diagrams, which generalize most Influence Diagram proposals and handle simultaneous decisions. Besides the global optimum method, we explore an anytime approximate solution with a guaranteed maximum error and show that imprecise probabilities are handled in a straightforward way. Complexity issues and experiments with random diagrams and an effects-based military planning problem are discussed.
Sampling First Order Logical Particles
Venue: arXiv cs.AI 2012
Year: 2012

Approximate inference in dynamic systems is the problem of estimating the state of the system given a sequence of actions and partial observations. High precision estimation is fundamental in many applications like diagnosis, natural language processing, tracking, planning, and robotics. In this paper we present an algorithm that samples possible deterministic executions of a probabilistic sequence. The algorithm takes advantage of a compact representation (using first order logic) for actions and world states to improve the precision of its estimation. Theoretical and empirical results show that the algorithm's expected error is smaller than propositional sampling and Sequential Monte Carlo (SMC) sampling techniques.
Small Sample Inference for Generalization Error in Classification Using the CUD Bound
Venue: arXiv cs.LG 2012
Year: 2012

Confidence measures for the generalization error are crucial when small training samples are used to construct classifiers. A common approach is to estimate the generalization error by resampling and then assume the resampled estimator follows a known distribution to form a confidence set [Kohavi 1995, Martin 1996,Yang 2006]. Alternatively, one might bootstrap the resampled estimator of the generalization error to form a confidence set. Unfortunately, these methods do not reliably provide sets of the desired confidence. The poor performance appears to be due to the lack of smoothness of the generalization error as a function of the learned classifier. This results in a non-normal distribution of the estimated generalization error. We construct a confidence set for the generalization error by use of a smooth upper bound on the deviation between the resampled estimate and generalization error. The confidence set is formed by bootstrapping this upper bound. In cases in which the approximation class for the classifier can be represented as a parametric additive model, we provide a computationally efficient algorithm. This method exhibits superior performance across a series of test and simulated data sets.
The Phylogenetic Indian Buffet Process: A Non-Exchangeable Nonparametric Prior for Latent Features
Venue: arXiv cs.LG 2012
Year: 2012

Nonparametric Bayesian models are often based on the assumption that the objects being modeled are exchangeable. While appropriate in some applications (e.g., bag-of-words models for documents), exchangeability is sometimes assumed simply for computational reasons; non-exchangeable models might be a better choice for applications based on subject matter. Drawing on ideas from graphical models and phylogenetics, we describe a non-exchangeable prior for a class of nonparametric latent feature models that is nearly as efficient computationally as its exchangeable counterpart. Our model is applicable to the general setting in which the dependencies between objects can be expressed using a tree, where edge lengths indicate the strength of relationships. We demonstrate an application to modeling probabilistic choice.
Improving the Accuracy and Efficiency of MAP Inference for Markov Logic
Venue: arXiv cs.AI 2012
Year: 2012

In this work we present Cutting Plane Inference (CPI), a Maximum A Posteriori (MAP) inference method for Statistical Relational Learning. Framed in terms of Markov Logic and inspired by the Cutting Plane Method, it can be seen as a meta algorithm that instantiates small parts of a large and complex Markov Network and then solves these using a conventional MAP method. We evaluate CPI on two tasks, Semantic Role Labelling and Joint Entity Resolution, while plugging in two different MAP inference methods: the current method of choice for MAP inference in Markov Logic, MaxWalkSAT, and Integer Linear Programming. We observe that when used with CPI both methods are significantly faster than when used alone. In addition, CPI improves the accuracy of MaxWalkSAT and maintains the exactness of Integer Linear Programming.
Tightening LP Relaxations for MAP using Message Passing
Venue: arXiv cs.DS 2012
Year: 2012

Linear Programming (LP) relaxations have become powerful tools for finding the most probable (MAP) configuration in graphical models. These relaxations can be solved efficiently using message-passing algorithms such as belief propagation and, when the relaxation is tight, provably find the MAP configuration. The standard LP relaxation is not tight enough in many real-world problems, however, and this has lead to the use of higher order cluster-based LP relaxations. The computational cost increases exponentially with the size of the clusters and limits the number and type of clusters we can use. We propose to solve the cluster selection problem monotonically in the dual LP, iteratively selecting clusters with guaranteed improvement, and quickly re-solving with the added clusters by reusing the existing solution. Our dual message-passing algorithm finds the MAP configuration in protein sidechain placement, protein design, and stereo problems, in cases where the standard LP relaxation fails.
Identifying Dynamic Sequential Plans
Venue: arXiv cs.AI 2012
Year: 2012

We address the problem of identifying dynamic sequential plans in the framework of causal Bayesian networks, and show that the problem is reduced to identifying causal effects, for which there are complete identi cation algorithms available in the literature.
Efficient Utilization of Channels Using Dynamic Guard Channel Allocation with Channel Borrowing Strategy in Handoffs
Venue: arXiv cs.NI 2012
Year: 2012

User mobility in wireless data networks is increasing because of technological advances and the desire for voice and multimedia applications. These applications, however, require fast handoffs between base stations to maintain the quality of the connections. In this paper, the authors describe the use of novel and efficient data structure which dynamically allocates guard channel for handoffs and introduces the concept of channel borrowing strategy. The proposed scheme allocates the guard channels for handoff requests dynamically, based on the traffic load for certain time period. A new originating call in the cell coverage area also uses these guard channels if they are unused. Our basic idea is to allow Guard channels to be shared between new calls and handoff calls. This approach maximizes the channel utilization. The simulation results prove that the channel borrowing scheme improves the overall throughput.
Comparison of Bucket Sort and RADIX Sort
Venue: arXiv cs.DS 2012
Year: 2012

Bucket sort and RADIX sort are two well-known integer sorting algorithms. This paper measures empirically what is the time usage and memory consumption for different kinds of input sequences. The algorithms are compared both from a theoretical standpoint but also on how well they do in six different use cases using randomized sequences of numbers. The measurements provide data on how good they are in different real-life situations. It was found that bucket sort was faster than RADIX sort, but that bucket sort uses more memory in most cases. The sorting algorithms performed faster with smaller integers. The RADIX sort was not quicker with already sorted inputs, but the bucket sort was.
General Upper Bounds on the Running Time of Parallel Evolutionary Algorithms
Venue: arXiv cs.NE 2012
Year: 2012

We present a new method for analyzing the running time of parallel evolutionary algorithms with spatially structured populations. Based on the fitness-level method, it yields upper bounds on the expected parallel running time. This allows to rigorously estimate the speedup gained by parallelization. Tailored results are given for common migration topologies: ring graphs, torus graphs, hypercubes, and the complete graph. Example applications for pseudo-Boolean optimization show that our method is easy to apply and that it gives powerful results. In our examples the possible speedup increases with the density of the topology. Surprisingly, even sparse topologies like ring graphs lead to a significant speedup for many functions while not increasing the total number of function evaluations by more than a constant factor. We also identify which number of processors yield asymptotically optimal speedups, thus giving hints on how to parametrize parallel evolutionary algorithms.
A static cost analysis for a higher-order language
Venue: arXiv cs.PL 2012
Year: 2012

We develop a static complexity analysis for a higher-order functional language with structural list recursion. The complexity of an expression is a pair consisting of a cost and a potential. The former is defined to be the size of the expression's evaluation derivation in a standard big-step operational semantics. The latter is a measure of the "future" cost of using the value of that expression. A translation function tr maps target expressions to complexities. Our main result is the following Soundness Theorem: If t is a term in the target language, then the cost component of tr(t) is an upper bound on the cost of evaluating t. The proof of the Soundness Theorem is formalized in Coq, providing certified upper bounds on the cost of any expression in the target language.
A Classification for Community Discovery Methods in Complex Networks
Venue: arXiv cs.SI 2012
Year: 2012

In the last few years many real-world networks have been found to show a so-called community structure organization. Much effort has been devoted in the literature to develop methods and algorithms that can efficiently highlight this hidden structure of the network, traditionally by partitioning the graph. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition it then extracts the communities that are able to reflect only some of the features of real communities. The aim of this survey is to provide a manual for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery based on their own definition of community. Given a desired definition of community and the features of a problem (size of network, direction of edges, multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on.
A Novel Low Power UWB Cascode SiGe BiCMOS LNA with Current Reuse and Zero-Pole Cancellation
Venue: arXiv cs.OH 2012
Year: 2012

A low power cascode SiGe BiCMOS low noise amplifier (LNA) with current reuse and zero-pole cancellation is presented for ultra-wideband (UWB) application. The LNA is composed of cascode input stage and common emitter (CE) output stage with dual loop feedbacks. The novel cascode-CE current reuse topology replaces the traditional two stages topology so as to obtain low power consumption. The emitter degenerative inductor in input stage is adopted to achieve good input impedance matching and noise performance. The two poles are introduced by the emitter inductor, which will degrade the gain performance, are cancelled by the dual loop feedbacks of the resistance-inductor (RL) shunt-shunt feedback and resistance-capacitor (RC) series-series feedback in the output stage. Meanwhile, output impedance matching is also achieved. Based on TSMC 0.35μm SiGe BiCMOS process, the topology and chip layout of the proposed LNA are designed and post-simulated. The LNA achieves the noise figure of 2.3~4.1dB, gain of 18.9~20.2dB, gain flatness of \pm0.65dB, input third order intercept point (IIP3) of -7dBm at 6GHz, exhibits less than 16ps of group delay variation, good input and output impedances matching, and unconditionally stable over the whole band. The power consuming is only 18mW.
Feature Based Fuzzy Rule Base Design for Image Extraction
Venue: arXiv cs.CV 2012
Year: 2012

In the recent advancement of multimedia technologies, it becomes a major concern of detecting visual attention regions in the field of image processing. The popularity of the terminal devices in a heterogeneous environment of the multimedia technology gives us enough scope for the betterment of image visualization. Although there exist numerous methods, feature based image extraction becomes a popular one in the field of image processing. The objective of image segmentation is the domain-independent partition of the image into a set of regions, which are visually distinct and uniform with respect to some property, such as grey level, texture or colour. Segmentation and subsequent extraction can be considered the first step and key issue in object recognition, scene understanding and image analysis. Its application area encompasses mobile devices, industrial quality control, medical appliances, robot navigation, geophysical exploration, military applications, etc. In all these areas, the quality of the final results depends largely on the quality of the preprocessing work. Most of the times, acquiring spurious-free preprocessing data requires a lot of application cum mathematical intensive background works. We propose a feature based fuzzy rule guided novel technique that is functionally devoid of any external intervention during execution. Experimental results suggest that this approach is an efficient one in comparison to different other techniques extensively addressed in literature. In order to justify the supremacy of performance of our proposed technique in respect of its competitors, we take recourse to effective metrics like Mean Squared Error (MSE), Mean Absolute Error (MAE) and Peak Signal to Noise Ratio (PSNR).
Broadcast Approaches to the Diamond Channel
Venue: arXiv cs.IT 2012
Year: 2012

The problem of dual-hop transmission from a source to a destination via two parallel full-duplex relays in block Rayleigh fading environment is investigated. All nodes in the network are assumed to be oblivious to their forward channel gains; however, they have perfect information about their backward channel gains. The focus of this paper is on simple, efficient, and practical relaying schemes to increase the expected-rate at the destination. For this purpose, various combinations of relaying protocols and the broadcast approach (multi-layer coding) are proposed. For the decode-forward (DF) relaying, the maximum finite-layer expected-rate as well as two upper-bounds on the continuous-layer expected-rate are obtained. The main feature of the proposed DF scheme is that the layers being decoded at both relays are added coherently at the destination although each relay has no information about the number of layers being successfully decoded by the other relay. It is proved that the optimal coding scheme is transmitting uncorrelated signals via the relays. Next, the maximum expected-rate of ON/OFF based amplify-forward (AF) relaying is analytically derived. For further performance improvement, a hybrid decode-amplify-forward (DAF) relaying strategy, adopting the broadcast approach at the source and relays, is proposed and its maximum throughput and maximum finite-layer expected-rate are presented. Moreover, the maximum throughput and maximum expected-rate in the compress-forward (CF) relaying adopting the broadcast approach, using optimal quantizers and Wyner-Ziv compression at the relays, are fully derived. All theoretical results are illustrated by numerical simulations. As it turns out from the results, when the ratio of the relay power to the source power is high, the CF relaying outperforms DAF (and hence outperforms both DF and AF relaying); otherwise, DAF scheme is superior.
Performance Limits for Distributed Estimation Over LMS Adaptive Networks
Venue: arXiv cs.IT 2012
Year: 2012

In this work we analyze the mean-square performance of different strategies for distributed estimation over least-mean-squares (LMS) adaptive networks. The results highlight some useful properties for distributed adaptation in comparison to fusion-based centralized solutions. The analysis establishes that, by optimizing over the combination weights, diffusion strategies can deliver lower excess-mean-square-error than centralized solutions employing traditional block or incremental LMS strategies. We first study in some detail the situation involving combinations of two adaptive agents and then extend the results to generic N-node ad-hoc networks. In the later case, we establish that, for sufficiently small step-sizes, diffusion strategies can outperform centralized block or incremental LMS strategies by optimizing over left-stochastic combination weighting matrices. The results suggest more efficient ways for organizing and processing data at fusion centers, and present useful adaptive strategies that are able to enhance performance when implemented in a distributed manner.
Statistics for the Dynamic Analysis of Scientometric Data: The evolution of the sciences in terms of trajectories and regimes
Venue: arXiv cs.DL 2012
Year: 2012

The gap in statistics between multi-variate and time-series analysis can be bridged by using entropy statistics and recent developments in multi-dimensional scaling. For explaining the evolution of the sciences as non-linear dynamics, the configurations among variables can be important in addition to the statistics of individual variables and trend lines. Animations enable us to combine multiple perspectives (based on configurations of variables) and to visualize path-dependencies in terms of trajectories and regimes. Path-dependent transitions and systems formation can be tested using entropy statistics.
A distributed classification/estimation algorithm for sensor networks
Venue: arXiv cs.MA 2012
Year: 2012

In this paper, we address the problem of simultaneous classification and estimation of hidden parameters in a sensor network with communications constraints. In particular, we consider a network of noisy sensors which measure a common scalar unknown parameter. We assume that a fraction of the nodes represent faulty sensors, whose measurements are poorly reliable. The goal for each node is to simultaneously identify its class (faulty or non-faulty) and estimate the common parameter. We propose a novel cooperative iterative algorithm which copes with the communication constraints imposed by the network and shows remarkable performance. Our main result is a rigorous proof of the convergence of the algorithm and a characterization of the limit behavior. We also show that, in the limit when the number of sensors goes to infinity, the common unknown parameter is estimated with arbitrary small error, while the classification error converges to that of the optimal centralized maximum likelihood estimator. We also show numerical results that validate the theoretical analysis and support their possible generalization. We compare our strategy with the Expectation-Maximization algorithm and we discuss trade-offs in terms of robustness, speed of convergence and implementation simplicity.