OpenRaiser/Intern-Atlas huggingface dataset:
Regional System Identification and Computer Based Switchable Control of a Nonlinear Hot Air Blower System
Venue: arXiv cs.SY 2012
Year: 2012

This paper describes the design and implementation of linear controllers with a switching condition for a nonlinear hot air blower system (HABS) process trainer PT326. The system is interfaced with a computer through a USB based data acquisition module and interfacing circuitry. A calibration equation is implemented through computer in order to convert the amplified output of the sensor to temperature. Overall plant is nonlinear; therefore, system identification is performed in three different regions depending upon the plant input. For these three regions, three linear controllers are designed with closed-loop system having small rise time, settling time and overshoot. Switching of controllers is based on regions defined by plant input. In order to avoid the effect of discontinuity, due to switching of linear controllers, parameters of all linear controllers are taken closer to each other. Finally, discretized controllers along with switching condition are implemented for the plant through computer and practical results are demonstrated.
Markov Chains on Orbits of Permutation Groups
Venue: arXiv cs.AI 2012
Year: 2012

We present a novel approach to detecting and utilizing symmetries in probabilistic graphical models with two main contributions. First, we present a scalable approach to computing generating sets of permutation groups representing the symmetries of graphical models. Second, we introduce orbital Markov chains, a novel family of Markov chains leveraging model symmetries to reduce mixing times. We establish an insightful connection between model symmetries and rapid mixing of orbital Markov chains. Thus, we present the first lifted MCMC algorithm for probabilistic graphical models. Both analytical and empirical results demonstrate the effectiveness and efficiency of the approach.
Semantic Networks of Interests in Online NSSI Communities
Venue: arXiv cs.SI 2012
Year: 2012

Persons who engage in non-suicidal self-injury (NSSI), often conceal their practices which limits the examination and understanding of those who engage in NSSI. The goal of this research is to utilize public online social networks (namely, in LiveJournal, a major blogging network) to observe the NSSI population's communication in a naturally occurring setting. Specifically, LiveJournal users can publicly declare their interests. We collected the self-declared interests of 22,000 users who are members of or participate in 43 NSSI-related communities. We extracted a bimodal socio-semantic network of users and interests based on their similarity. The semantic subnetwork of interests contains NSSI terms (such as "self-injury" and "razors"), references to music performers (such as "Nine Inch Nails"), and general daily life and creativity related terms (such as "poetry" and "boys"). Assuming users are genuine in their declarations, the words reveal distinct patterns of interest and may signal keys to NSSI.
Practical recommendations for gradient-based training of deep architectures
Venue: arXiv cs.LG 2012
Year: 2012

Learning algorithms related to artificial neural networks and in particular for Deep Learning may seem to involve many bells and whistles, called hyper-parameters. This chapter is meant as a practical guide with recommendations for some of the most commonly used hyper-parameters, in particular in the context of learning algorithms based on back-propagated gradient and gradient-based optimization. It also discusses how to deal with the fact that more interesting results can be obtained when allowing one to adjust many hyper-parameters. Overall, it describes elements of the practice used to successfully and efficiently train and debug large-scale and often deep multi-layer neural networks. It closes with open questions about the training difficulties observed with deeper architectures.
Kernelization Lower Bounds By Cross-Composition
Venue: arXiv cs.CC 2012
Year: 2012

We introduce the cross-composition framework for proving kernelization lower bounds. A classical problem L AND/OR-cross-composes into a parameterized problem Q if it is possible to efficiently construct an instance of Q with polynomially bounded parameter value that expresses the logical AND or OR of a sequence of instances of L. Building on work by Bodlaender et al. (ICALP 2008) and using a result by Fortnow and Santhanam (STOC 2008) with a refinement by Dell and van Melkebeek (STOC 2010), we show that if an NP-hard problem OR-cross-composes into a parameterized problem Q then Q does not admit a polynomial kernel unless NP \subseteq coNP/poly and the polynomial hierarchy collapses. Similarly, an AND-cross-composition for Q rules out polynomial kernels for Q under Bodlaender et al.'s AND-distillation conjecture. Our technique generalizes and strengthens the recent techniques of using composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (non-standard) parameterizations, e.g., Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. After learning of our results, several teams of authors have successfully applied the cross-composition framework to different parameterized problems. For completeness, our presentation of the framework includes several extensions based on this follow-up work. For example, we show how a relaxed version of OR-cross-compositions may be used to give lower bounds on the degree of the polynomial in the kernel size.
Transductive Classification Methods for Mixed Graphs
Venue: arXiv cs.LG 2012
Year: 2012

In this paper we provide a principled approach to solve a transductive classification problem involving a similar graph (edges tend to connect nodes with same labels) and a dissimilar graph (edges tend to connect nodes with opposing labels). Most of the existing methods, e.g., Information Regularization (IR), Weighted vote Relational Neighbor classifier (WvRN) etc, assume that the given graph is only a similar graph. We extend the IR and WvRN methods to deal with mixed graphs. We evaluate the proposed extensions on several benchmark datasets as well as two real world datasets and demonstrate the usefulness of our ideas.
On the CNF-complexity of bipartite graphs containing no $K_{2,2}$'s
Venue: arXiv cs.CC 2012
Year: 2012

By a probabilistic construction, we find a bipartite graph having average degree $d$ which can be expressed as a conjunctive normal form using $C \log d$ clauses. This contradicts research problem 1.33 of Jukna.
Precise Location Acquisition of Mobility Data Using Cell-id
Venue: arXiv cs.NI 2012
Year: 2012

This paper has been withdrawn by the authors. Cellular network data has become a hot source of study for extraction of user-mobility and spatio-temporal trends. Location binding in mobility data can be done through different methods like GPS, service provider assisted faux-GPS and Cell Global Identity (CGI). Among these Cell Global Identity is most inexpensive method and readily available solution for mobility extraction; however exact spatial extraction is somehow a problem in it. This paper presents the spatial extraction technique of mobile phone user raw data which carries the information like location information, proximity location and activity of subjects. This work mainly focuses on the data pre-processing methodology and technique to interpret the low level mobility data into high level mobility information using the designed clustering methodology and publically available Cell-IDs databases. Work proposed the semi- supervised strategy to derive the missing locations thorough the usage of semantic tag information and removal of spatial outliers for precise mobility profile building.
Some Novel Results From Analysis of Move To Front (MTF) List Accessing Algorithm
Venue: arXiv cs.DS 2012
Year: 2012

List accessing problem has been studied as a problem of significant theoretical and practical interest in the context of linear search. Various list accessing algorithms have been proposed in the literature and their performances have been analyzed theoretically and experimentally. Move-To-Front(MTF),Transpose (TRANS) and Frequency Count (FC) are the three primitive and widely used list accessing algorithms. Most of the other list accessing algorithms are the variants of these three algorithms. As mentioned in the literature as an open problem, direct bounds on the behavior and performance of these list accessing algorithms are needed to allow realistic comparisons. MTF has been proved to be the best performing online algorithm till date in the literature for real life inputs with locality of reference. Motivated by the above challenging research issue, in this paper, we have generated four types of input request sequences corresponding to real life inputs without locality of reference. Using these types of request sequences, we have made an analytical study for evaluating the performance of MTF list accessing algorithm to obtain some novel and interesting theoretical results.
An Optimal Fully Distributed Algorithm to Minimize the Resource Consumption of Cloud Applications
Venue: arXiv cs.DC 2012
Year: 2012

According to the pay-per-use model adopted in clouds, the more the resources consumed by an application running in a cloud computing environment, the greater the amount of money the owner of the corresponding application will be charged. Therefore, applying intelligent solutions to minimize the resource consumption is of great importance. Because centralized solutions are deemed unsuitable for large-distributed systems or large-scale applications, we propose a fully distributed algorithm (called DRA) to overcome the scalability issues. Specifically, DRA migrates the inter-communicating components of an application, such as processes or virtual machines, close to each other to minimize the total resource consumption. The migration decisions are made in a dynamic way and based only on local information. We prove that DRA achieves convergence and results always in the optimal solution.
MOMCC: Market-Oriented Architecture for Mobile Cloud Computing Based on Service Oriented Architecture
Venue: arXiv cs.DC 2012
Year: 2012

The vision of augmenting computing capabilities of mobile devices, especially smartphones with least cost is likely transforming to reality leveraging cloud computing. Cloud exploitation by mobile devices breeds a new research domain called Mobile Cloud Computing (MCC). However, issues like portability and interoperability should be addressed for mobile augmentation which is a non-trivial task using component-based approaches. Service Oriented Architecture (SOA) is a promising design philosophy embraced by mobile computing and cloud computing communities to stimulate portable, complex application using prefabricated building blocks called Services. Utilizing distant cloud resources to host and run Services is hampered by long WAN latency. Exploiting mobile devices in vicinity alleviates long WAN latency, while creates new set of issues like Service publishing and discovery as well as client-server security, reliability, and Service availability. In this paper, we propose a market-oriented architecture based on SOA to stimulate publishing, discovering, and hosting Services on nearby mobiles, which reduces long WAN latency and creates a business opportunity that encourages mobile owners to embrace Service hosting. Group of mobile phones simulate a nearby cloud computing platform. We create new role of \textit{Service host} by enabling unskilled mobile owners/users to host Services developed by skilled developers. Evidently, Service availability, reliability, and Service-oriented mobile application portability will increase towards green ubiquitous computing in our mobile cloud infrastructure.
User Selection for Multi-user MIMO Downlink with Zero-Forcing Beamforming
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose a greedy user selection with swap (GUSS) algorithm based on zero-forcing beamforming (ZFBF) for the multi-user multiple-input multiple-output (MIMO) downlink channels. Since existing user selection algorithms, such as the zero-forcing with selection (ZFS), have `redundant user' and `local optimum' flaws that compromise the achieved sum rate, GUSS adds `delete' and `swap' operations to the user selection procedure of ZFS to improve the performance by eliminating `redundant user' and escaping from `local optimum', respectively. In addition, an effective channel vector based effective-channel-gain updating scheme is presented to reduce the complexity of GUSS. With the help of this updating scheme, GUSS has the same order of complexity of ZFS with only a linear increment. Simulation results indicate that on average GUSS achieves 99.3 percent of the sum rate upper bound that is achieved by exhaustive search, over the range of transmit signal-to-noise ratios considered with only three to six times the complexity of ZFS.
Scaling Life-long Off-policy Learning
Venue: arXiv cs.AI 2012
Year: 2012

We pursue a life-long learning approach to artificial intelligence that makes extensive use of reinforcement learning algorithms. We build on our prior work with general value functions (GVFs) and the Horde architecture. GVFs have been shown able to represent a wide variety of facts about the world's dynamics that may be useful to a long-lived agent (Sutton et al. 2011). We have also previously shown scaling - that thousands of on-policy GVFs can be learned accurately in real-time on a mobile robot (Modayil, White & Sutton 2011). That work was limited in that it learned about only one policy at a time, whereas the greatest potential benefits of life-long learning come from learning about many policies in parallel, as we explore in this paper. Many new challenges arise in this off-policy learning setting. To deal with convergence and efficiency challenges, we utilize the recently introduced GTD(λ) algorithm. We show that GTD(λ) with tile coding can simultaneously learn hundreds of predictions for five simple target policies while following a single random behavior policy, assessing accuracy with interspersed on-policy tests. To escape the need for the tests, which preclude further scaling, we introduce and empirically vali- date two online estimators of the off-policy objective (MSPBE). Finally, we use the more efficient of the two estimators to demonstrate off-policy learning at scale - the learning of value functions for one thousand policies in real time on a physical robot. This ability constitutes a significant step towards scaling life-long off-policy learning.
Pareto Curves for Probabilistic Model Checking
Venue: arXiv cs.LO 2012
Year: 2012

Multi-objective probabilistic model checking provides a way to verify several, possibly conflicting, quantitative properties of a stochastic system. It has useful applications in controller synthesis and compositional probabilistic verification. However, existing methods are based on linear programming, which limits the scale of systems that can be analysed and makes verification of time-bounded properties very difficult. We present a novel approach that addresses both of these shortcomings, based on the generation of successive approximations of the Pareto curve for a multi-objective model checking problem. We illustrate dramatic improvements in efficiency on a large set of benchmarks and show how the ability to visualise Pareto curves significantly enhances the quality of results obtained from current probabilistic verification tools.
An algebraic approach to symmetric extended formulations
Venue: arXiv cs.CC 2012
Year: 2012

Extended formulations are an important tool to obtain small (even compact) formulations of polytopes by representing them as projections of higher dimensional ones. It is an important question whether a polytope admits a small extended formulation, i.e., one involving only a polynomial number of inequalities in its dimension. For the case of symmetric extended formulations (i.e., preserving the symmetries of the polytope) Yannakakis established a powerful technique to derive lower bounds and rule out small formulations. We rephrase the technique of Yannakakis in a group-theoretic framework. This provides a different perspective on symmetric extensions and considerably simplifies several lower bound constructions.
The observational roots of reference of the semantic web
Venue: arXiv cs.AI 2012
Year: 2012

Shared reference is an essential aspect of meaning. It is also indispensable for the semantic web, since it enables to weave the global graph, i.e., it allows different users to contribute to an identical referent. For example, an essential kind of referent is a geographic place, to which users may contribute observations. We argue for a human-centric, operational approach towards reference, based on respective human competences. These competences encompass perceptual, cognitive as well as technical ones, and together they allow humans to inter-subjectively refer to a phenomenon in their environment. The technology stack of the semantic web should be extended by such operations. This would allow establishing new kinds of observation-based reference systems that help constrain and integrate the semantic web bottom-up.
Investigation of Color Constancy for Ubiquitous Wireless LAN/Camera Positioning: An Initial Outcome
Venue: arXiv cs.CV 2012
Year: 2012

This paper present our color constancy investigation in the hybridization of Wireless LAN and Camera positioning in the mobile phone. Five typical color constancy schemes are analyzed in different location environment. The results can be used to combine with RF signals from Wireless LAN positioning by using model fitting approach in order to establish absolute positioning output. There is no conventional searching algorithm required, thus it is expected to reduce the complexity of computation. Finally we present our preliminary results to illustrate the indoor positioning algorithm performance evaluation for an indoor environment set-up.
TexComp - A Text Complexity Analyzer for Student Texts
Venue: arXiv cs.CY 2012
Year: 2012

This paper describes a method for providing feedback about the degree of complexity that is present in particular texts. Both the method and the software tool called TexComp are designed for use during the assessment of student compositions (such as essays and theses). The method is based on a cautious approach to the application of readability and lexical diversity formulas for reasons that are analyzed in detail in this paper. We evaluated the tool by using USE and BAWE, two corpora of texts that originate from students who use English as a medium of instruction.
Piecewise Linear Topology, Evolutionary Algorithms, and Optimization Problems
Venue: arXiv cs.NE 2012
Year: 2012

Schemata theory, Markov chains, and statistical mechanics have been used to explain how evolutionary algorithms (EAs) work. Incremental success has been achieved with all of these methods, but each has been stymied by limitations related to its less-than-global view. We show that moving the investigation into topological space improves our understanding of why EAs work.
Discriminative Learning via Semidefinite Probabilistic Models
Venue: arXiv cs.LG 2012
Year: 2012

Discriminative linear models are a popular tool in machine learning. These can be generally divided into two types: The first is linear classifiers, such as support vector machines, which are well studied and provide state-of-the-art results. One shortcoming of these models is that their output (known as the 'margin') is not calibrated, and cannot be translated naturally into a distribution over the labels. Thus, it is difficult to incorporate such models as components of larger systems, unlike probabilistic based approaches. The second type of approach constructs class conditional distributions using a nonlinearity (e.g. log-linear models), but is occasionally worse in terms of classification error. We propose a supervised learning method which combines the best of both approaches. Specifically, our method provides a distribution over the labels, which is a linear function of the model parameters. As a consequence, differences between probabilities are linear functions, a property which most probabilistic models (e.g. log-linear) do not have. Our model assumes that classes correspond to linear subspaces (rather than to half spaces). Using a relaxed projection operator, we construct a measure which evaluates the degree to which a given vector 'belongs' to a subspace, resulting in a distribution over labels. Interestingly, this view is closely related to similar concepts in quantum detection theory. The resulting models can be trained either to maximize the margin or to optimize average likelihood measures. The corresponding optimization problems are semidefinite programs which can be solved efficiently. We illustrate the performance of our algorithm on real world datasets, and show that it outperforms 2nd order kernel methods.
MAIES: A Tool for DNA Mixture Analysis
Venue: arXiv cs.AI 2012
Year: 2012

We describe an expert system, MAIES, developed for analysing forensic identification problems involving DNA mixture traces using quantitative peak area information. Peak area information is represented by conditional Gaussian distributions, and inference based on exact junction tree propagation ascertains whether individuals, whose profiles have been measured, have contributed to the mixture. The system can also be used to predict DNA profiles of unknown contributors by separating the mixture into its individual components. The use of the system is illustrated with an application to a real world example. The system implements a novel MAP (maximum a posteriori) search algorithm that is described in an appendix.
Gene Expression Time Course Clustering with Countably Infinite Hidden Markov Models
Venue: arXiv cs.LG 2012
Year: 2012

Most existing approaches to clustering gene expression time course data treat the different time points as independent dimensions and are invariant to permutations, such as reversal, of the experimental time course. Approaches utilizing HMMs have been shown to be helpful in this regard, but are hampered by having to choose model architectures with appropriate complexities. Here we propose for a clustering application an HMM with a countably infinite state space; inference in this model is possible by recasting it in the hierarchical Dirichlet process (HDP) framework (Teh et al. 2006), and hence we call it the HDP-HMM. We show that the infinite model outperforms model selection methods over finite models, and traditional time-independent methods, as measured by a variety of external and internal indices for clustering on two large publicly available data sets. Moreover, we show that the infinite models utilize more hidden states and employ richer architectures (e.g. state-to-state transitions) without the damaging effects of overfitting.
Linear Algebra Approach to Separable Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

Separable Bayesian Networks, or the Influence Model, are dynamic Bayesian Networks in which the conditional probability distribution can be separated into a function of only the marginal distribution of a node's neighbors, instead of the joint distributions. In terms of modeling, separable networks has rendered possible siginificant reduction in complexity, as the state space is only linear in the number of variables on the network, in contrast to a typical state space which is exponential. In this work, We describe the connection between an arbitrary Conditional Probability Table (CPT) and separable systems using linear algebra. We give an alternate proof on the equivalence of sufficiency and separability. We present a computational method for testing whether a given CPT is separable.