OpenRaiser/Intern-Atlas huggingface dataset:
Deep Transductive Semi-supervised Maximum Margin Clustering
Venue: arXiv cs.LG 2015
Year: 2015

Semi-supervised clustering is an very important topic in machine learning and computer vision. The key challenge of this problem is how to learn a metric, such that the instances sharing the same label are more likely close to each other on the embedded space. However, little attention has been paid to learn better representations when the data lie on non-linear manifold. Fortunately, deep learning has led to great success on feature learning recently. Inspired by the advances of deep learning, we propose a deep transductive semi-supervised maximum margin clustering approach. More specifically, given pairwise constraints, we exploit both labeled and unlabeled data to learn a non-linear mapping under maximum margin framework for clustering analysis. Thus, our model unifies transductive learning, feature learning and maximum margin techniques in the semi-supervised clustering framework. We pretrain the deep network structure with restricted Boltzmann machines (RBMs) layer by layer greedily, and optimize our objective function with gradient descent. By checking the most violated constraints, our approach updates the model parameters through error backpropagation, in which deep features are learned automatically. The experimental results shows that our model is significantly better than the state of the art on semi-supervised clustering.
Reciprocal Recommendation System for Online Dating
Venue: arXiv cs.SI 2015
Year: 2015

Online dating sites have become popular platforms for people to look for potential romantic partners. Different from traditional user-item recommendations where the goal is to match items (e.g., books, videos, etc) with a user's interests, a recommendation system for online dating aims to match people who are mutually interested in and likely to communicate with each other. We introduce similarity measures that capture the unique features and characteristics of the online dating network, for example, the interest similarity between two users if they send messages to same users, and attractiveness similarity if they receive messages from same users. A reciprocal score that measures the compatibility between a user and each potential dating candidate is computed and the recommendation list is generated to include users with top scores. The performance of our proposed recommendation system is evaluated on a real-world dataset from a major online dating site in China. The results show that our recommendation algorithms significantly outperform previously proposed approaches, and the collaborative filtering-based algorithms achieve much better performance than content-based algorithms in both precision and recall. Our results also reveal interesting behavioral difference between male and female users when it comes to looking for potential dates. In particular, males tend to be focused on their own interest and oblivious towards their attractiveness to potential dates, while females are more conscientious to their own attractiveness to the other side of the line.
Replica Symmetric Bound for Restricted Isometry Constant
Venue: arXiv cs.IT 2015
Year: 2015

We develop a method for evaluating restricted isometry constants (RICs). This evaluation is reduced to the identification of the zero-points of entropy, which is defined for submatrices that are composed of columns selected from a given measurement matrix. Using the replica method developed in statistical mechanics, we assess RICs for Gaussian random matrices under the replica symmetric (RS) assumption. In order to numerically validate the adequacy of our analysis, we employ the exchange Monte Carlo (EMC) method, which has been empirically demonstrated to achieve much higher numerical accuracy than naive Monte Carlo methods. The EMC method suggests that our theoretical estimation of an RIC corresponds to an upper bound that is tighter than in preceding studies. Physical consideration indicates that our assessment of the RIC could be improved by taking into account the replica symmetry breaking.
It's a Man's Wikipedia? Assessing Gender Inequality in an Online Encyclopedia
Venue: arXiv cs.CY 2015
Year: 2015

Wikipedia is a community-created encyclopedia that contains information about notable people from different countries, epochs and disciplines and aims to document the world's knowledge from a neutral point of view. However, the narrow diversity of the Wikipedia editor community has the potential to introduce systemic biases such as gender biases into the content of Wikipedia. In this paper we aim to tackle a sub problem of this larger challenge by presenting and applying a computational method for assessing gender bias on Wikipedia along multiple dimensions. We find that while women on Wikipedia are covered and featured well in many Wikipedia language editions, the way women are portrayed starkly differs from the way men are portrayed. We hope our work contributes to increasing awareness about gender biases online, and in particular to raising attention to the different levels in which gender biases can manifest themselves on the web.
Simultaneous diagonalization: the asymmetric, low-rank, and noisy settings
Venue: arXiv cs.NA 2015
Year: 2015

Simultaneous matrix diagonalization is used as a subroutine in many machine learning problems, including blind source separation and paramater estimation in latent variable models. Here, we extend algorithms for performing joint diagonalization to low-rank and asymmetric matrices, and we also provide extensions to the perturbation analysis of these methods. Our results allow joint diagonalization to be applied in several new settings.
The GPU vs Phi Debate: Risk Analytics Using Many-Core Computing
Venue: arXiv cs.DC 2015
Year: 2015

The risk of reinsurance portfolios covering globally occurring natural catastrophes, such as earthquakes and hurricanes, is quantified by employing simulations. These simulations are computationally intensive and require large amounts of data to be processed. The use of many-core hardware accelerators, such as the Intel Xeon Phi and the NVIDIA Graphics Processing Unit (GPU), are desirable for achieving high-performance risk analytics. In this paper, we set out to investigate how accelerators can be employed in risk analytics, focusing on developing parallel algorithms for Aggregate Risk Analysis, a simulation which computes the Probable Maximum Loss of a portfolio taking both primary and secondary uncertainties into account. The key result is that both hardware accelerators are useful in different contexts; without taking data transfer times into account the Phi had lowest execution times when used independently and the GPU along with a host in a hybrid platform yielded best performance.
GPU Programming - Speeding Up the 3D Surface Generator VESTA
Venue: arXiv cs.GR 2015
Year: 2015

The novel "Volume-Enclosing Surface exTraction Algorithm" (VESTA) generates triangular isosurfaces from computed tomography volumetric images and/or three-dimensional (3D) simulation data. Here, we present various benchmarks for GPU-based code implementations of both VESTA and the current state-of-the-art Marching Cubes Algorithm (MCA). One major result of this study is that VESTA runs significantly faster than the MCA.
Exploring the genetic patterns of complex diseases via the integrative genome-wide approach
Venue: arXiv cs.CE 2015
Year: 2015

Motivation: Genome-wide association studies (GWASs), which assay more than a million single nucleotide polymorphisms (SNPs) in thousands of individuals, have been widely used to identify genetic risk variants for complex diseases. However, most of the variants that have been identified contribute relatively small increments of risk and only explain a small portion of the genetic variation in complex diseases. This is the so-called missing heritability problem. Evidence has indicated that many complex diseases are genetically related, meaning these diseases share common genetic risk variants. Therefore, exploring the genetic correlations across multiple related studies could be a promising strategy for removing spurious associations and identifying underlying genetic risk variants, and thereby uncovering the mystery of missing heritability in complex diseases. Results: We present a general and robust method to identify genetic patterns from multiple large-scale genomic datasets. We treat the summary statistics as a matrix and demonstrate that genetic patterns will form a low-rank matrix plus a sparse component. Hence, we formulate the problem as a matrix recovering problem, where we aim to discover risk variants shared by multiple diseases/traits and those for each individual disease/trait. We propose a convex formulation for matrix recovery and an efficient algorithm to solve the problem. We demonstrate the advantages of our method using both synthesized datasets and real datasets. The experimental results show that our method can successfully reconstruct both the shared and the individual genetic patterns from summary statistics and achieve better performance compared with alternative methods under a wide range of scenarios.
Index Policies for Optimal Mean-Variance Trade-Off of Inter-delivery Times in Real-Time Sensor Networks
Venue: arXiv cs.NI 2015
Year: 2015

A problem of much current practical interest is the replacement of the wiring infrastructure connecting approximately 200 sensor and actuator nodes in automobiles by an access point. This is motivated by the considerable savings in automobile weight, simplification of manufacturability, and future upgradability. A key issue is how to schedule the nodes on the shared access point so as to provide regular packet delivery. In this and other similar applications, the mean of the inter-delivery times of packets, i.e., throughput, is not sufficient to guarantee service-regularity. The time-averaged variance of the inter-delivery times of packets is also an important metric. So motivated, we consider a wireless network where an Access Point schedules real-time generated packets to nodes over a fading wireless channel. We are interested in designing simple policies which achieve optimal mean-variance tradeoff in interdelivery times of packets by minimizing the sum of time-averaged means and variances over all clients. Our goal is to explore the full range of the Pareto frontier of all weighted linear combinations of mean and variance so that one can fully exploit the design possibilities. We transform this problem into a Markov decision process and show that the problem of choosing which node's packet to transmit in each slot can be formulated as a bandit problem. We establish that this problem is indexable and explicitly derive the Whittle indices. The resulting Index policy is optimal in certain cases. We also provide upper and lower bounds on the cost for any policy. Extensive simulations show that Index policies perform better than previously proposed policies.
Deduction modulo theory
Venue: arXiv cs.LO 2015
Year: 2015

This paper is a survey on Deduction modulo theory
Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread
Venue: arXiv cs.SI 2015
Year: 2015

The largest eigenvalue of the adjacency matrix of a network (referred to as the spectral radius) is an important metric in its own right. Further, for several models of epidemic spread on networks (e.g., the `flu-like' SIS model), it has been shown that an epidemic dies out quickly if the spectral radius of the graph is below a certain threshold that depends on the model parameters. This motivates a strategy to control epidemic spread by reducing the spectral radius of the underlying network. In this paper, we develop a suite of provable approximation algorithms for reducing the spectral radius by removing the minimum cost set of edges (modeling quarantining) or nodes (modeling vaccinations), with different time and quality tradeoffs. Our main algorithm, \textsc{GreedyWalk}, is based on the idea of hitting closed walks of a given length, and gives an $O(\log^2{n})$-approximation, where $n$ denotes the number of nodes; it also performs much better in practice compared to all prior heuristics proposed for this problem. We further present a novel sparsification method to improve its running time. In addition, we give a new primal-dual based algorithm with an even better approximation guarantee ($O(\log n)$), albeit with slower running time. We also give lower bounds on the worst-case performance of some of the popular heuristics. Finally we demonstrate the applicability of our algorithms and the properties of our solutions via extensive experiments on multiple synthetic and real networks.
The Gaussian Channel with Noisy Feedback: Improving Reliability via Interaction
Venue: arXiv cs.IT 2015
Year: 2015

Consider a pair of terminals connected by two independent (feedforward and feedback) Additive White Gaussian Noise (AWGN) channels, and limited by individual power constraints. The first terminal would like to reliably send information to the second terminal at a given rate. While the reliability in the cases of no feedback and of noiseless feedback is well studied, not much is known about the case of noisy feedback. In this work, we present an interactive scheme that significantly improves the reliability relative to the no-feedback setting, whenever the feedback Signal to Noise Ratio (SNR) is sufficiently larger than the feedforward SNR. The scheme combines Schalkwijk-Kailath (S-K) coding and modulo--lattice analog transmission.
General-Purpose Join Algorithms for Listing Triangles in Large Graphs
Venue: arXiv cs.DB 2015
Year: 2015

We investigate applying general-purpose join algorithms to the triangle listing problem in an out-of-core context. In particular, we focus on Leapfrog Triejoin (LFTJ) by Veldhuizen 2014, a recently proposed, worst-case optimal algorithm. We present "boxing": a novel, yet conceptually simple, approach for feeding input data to LFTJ. Our extensive analysis shows that this approach is I/O efficient, being worst-case optimal (in a certain sense). Furthermore, if input data is only a constant factor larger than the available memory, then a boxed LFTJ essentially maintains the CPU data-complexity of the vanilla LFTJ. Next, focusing on LFTJ applied to the triangle query, we show that for many graphs boxed LFTJ matches the I/O complexity of the recently by Hu, Tao and Yufei proposed specialized algorithm MGT for listing tiangles in an out-of-core setting. We also strengthen the analysis of LFTJ's computational complexity for the triangle query by considering families of input graphs that are characterized not only by the number of edges but also by a measure of their density. E.g., we show that LFTJ achieves a CPU complexity of O(|E|log|E|) for planar graphs, while on general graphs, no algorithm can be faster than O(|E|^{1.5}). Finally, we perform an experimental evaluation for the triangle listing problem confirming our theoretical results and showing the overall effectiveness of our approach. On all our real-world and synthetic data sets (some of which containing more than 1.2 billion edges) LFTJ in single-threaded mode is within a factor of 3 of the specialized MGT; a penalty that---as we demonstrate---can be alleviated by parallelization.
Assignment of Different-Sized Inputs in MapReduce
Venue: arXiv cs.DB 2015
Year: 2015

A MapReduce algorithm can be described by a mapping schema, which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all the inputs that participate in the computation of this output. Reducers have a capacity, which limits the sets of inputs that they can be assigned. However, individual inputs may vary in terms of size. We consider, for the first time, mapping schemas where input sizes are part of the considerations and restrictions. One of the significant parameters to optimize in any MapReduce job is communication cost between the map and reduce phases. The communication cost can be optimized by minimizing the number of copies of inputs sent to the reducers. The communication cost is closely related to the number of reducers of constrained capacity that are used to accommodate appropriately the inputs, so that the requirement of how the inputs must meet in a reducer is satisfied. In this work, we consider a family of problems where it is required that each input meets with each other input in at least one reducer. We also consider a slightly different family of problems in which, each input of a set, X, is required to meet each input of another set, Y, in at least one reducer. We prove that finding an optimal mapping schema for these families of problem is NP-hard, and present several approximation algorithms for finding a near optimal mapping schema.
Truss Analysis Discussion and Interpretation Using Linear Systems of Equalities and Inequalities
Venue: arXiv cs.CE 2015
Year: 2015

This paper shows the complementary roles of mathematical and engineering points of view when dealing with truss analysis problems involving systems of linear equations and inequalities. After the compatibility condition and the mathematical structure of the general solution of a system of linear equations is discussed, the truss analysis problem is used to illustrate its mathematical and engineering multiple aspects, including an analysis of the compatibility conditions and a physical interpretation of the general solution, and the generators of the resulting affine space. Next, the compatibility and the mathematical structure of the general solution of linear systems of inequalities are analyzed and the truss analysis problem revisited adding some inequality constraints, and discussing how they affect the resulting general solution and many other aspects of it. Finally, some conclusions are drawn.
Stability Analysis of Slotted Aloha with Opportunistic RF Energy Harvesting
Venue: arXiv cs.NI 2015
Year: 2015

Energy harvesting (EH) is a promising technology for realizing energy efficient wireless networks. In this paper, we utilize the ambient RF energy, particularly interference from neighboring transmissions, to replenish the batteries of the EH enabled nodes. However, RF energy harvesting imposes new challenges into the analysis of wireless networks. Our objective in this work is to investigate the performance of a slotted Aloha random access wireless network consisting of two types of nodes, namely Type I which has unlimited energy supply and Type II which is solely powered by an RF energy harvesting circuit. The transmissions of a Type I node are recycled by a Type II node to replenish its battery. We characterize an inner bound on the stable throughput region under half-duplex and full-duplex energy harvesting paradigms as well as for the finite capacity battery case. We present numerical results that validate our analytical results, and demonstrate their utility for the analysis of the exact system.
Learning Analytics: A Survey
Venue: arXiv cs.DB 2015
Year: 2015

Learning analytics is a research topic that is gaining increasing popularity in recent time. It analyzes the learning data available in order to make aware or improvise the process itself and/or the outcome such as student performance. In this survey paper, we look at the recent research work that has been conducted around learning analytics, framework and integrated models, and application of various models and data mining techniques to identify students at risk and to predict student performance.
A Distance-Based Decision in the Credal Level
Venue: arXiv cs.AI 2015
Year: 2015

Belief function theory provides a flexible way to combine information provided by different sources. This combination is usually followed by a decision making which can be handled by a range of decision rules. Some rules help to choose the most likely hypothesis. Others allow that a decision is made on a set of hypotheses. In [6], we proposed a decision rule based on a distance measure. First, in this paper, we aim to demonstrate that our proposed decision rule is a particular case of the rule proposed in [4]. Second, we give experiments showing that our rule is able to decide on a set of hypotheses. Some experiments are handled on a set of mass functions generated randomly, others on real databases.
k2U: A General Framework from k-Point Effective Schedulability Analysis to Utilization-Based Tests
Venue: arXiv cs.OS 2015
Year: 2015

To deal with a large variety of workloads in different application domains in real-time embedded systems, a number of expressive task models have been developed. For each individual task model, researchers tend to develop different types of techniques for deriving schedulability tests with different computation complexity and performance. In this paper, we present a general schedulability analysis framework, namely the k2U framework, that can be potentially applied to analyze a large set of real-time task models under any fixed-priority scheduling algorithm, on both uniprocessor and multiprocessor scheduling. The key to k2U is a k-point effective schedulability test, which can be viewed as a "blackbox" interface. For any task model, if a corresponding k-point effective schedulability test can be constructed, then a sufficient utilization-based test can be automatically derived. We show the generality of k2U by applying it to different task models, which results in new and improved tests compared to the state-of-the-art. Analogously, a similar concept by testing only k points with a different formulation has been studied by us in another framework, called k2Q, which provides quadratic bounds or utilization bounds based on a different formulation of schedulability test. With the quadratic and hyperbolic forms, k2Q and k2U frameworks can be used to provide many quantitive features to be measured, like the total utilization bounds, speed-up factors, etc., not only for uniprocessor scheduling but also for multiprocessor scheduling. These frameworks can be viewed as a "blackbox" interface for schedulability tests and response-time analysis.
Planarity of Streamed Graphs
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A $\textit{streamed graph}$ is a stream of edges $e_1,e_2,...,e_m$ on a vertex set $V$. A streamed graph is $ω$-$\textit{stream planar}$ with respect to a positive integer window size $ω$ if there exists a sequence of planar topological drawings $Γ_i$ of the graphs $G_i=(V,\{e_j \mid i\leq j < i+ω\})$ such that the common graph $G^{i}_\cap=G_i\cap G_{i+1}$ is drawn the same in $Γ_i$ and in $Γ_{i+1}$, for $1\leq i < m-ω$. The $\textit{Stream Planarity}$ Problem with window size $ω$ asks whether a given streamed graph is $ω$-stream planar. We also consider a generalization, where there is an additional $\textit{backbone graph}$ whose edges have to be present during each time step. These problems are related to several well-studied planarity problems. We show that the $\textit{Stream Planarity}$ Problem is NP-complete even when the window size is a constant and that the variant with a backbone graph is NP-complete for all $ω\ge 2$. On the positive side, we provide $O(n+ωm)$-time algorithms for (i) the case $ω= 1$ and (ii) all values of $ω$ provided the backbone graph consists of one $2$-connected component plus isolated vertices and no stream edge connects two isolated vertices. Our results improve on the Hanani-Tutte-style $O((nm)^3)$-time algorithm proposed by Schaefer [GD'14] for $ω=1$.