OpenRaiser/Intern-Atlas huggingface dataset:
Parallel Pairwise Correlation Computation On Intel Xeon Phi Clusters
Venue: arXiv cs.DC 2016
Year: 2016

Co-expression network is a critical technique for the identification of inter-gene interactions, which usually relies on all-pairs correlation (or similar measure) computation between gene expression profiles across multiple samples. Pearson's correlation coefficient (PCC) is one widely used technique for gene co-expression network construction. However, all-pairs PCC computation is computationally demanding for large numbers of gene expression profiles, thus motivating our acceleration of its execution using high-performance computing. In this paper, we present LightPCC, the first parallel and distributed all-pairs PCC computation on Intel Xeon Phi (Phi) clusters. It achieves high speed by exploring the SIMD-instruction-level and thread-level parallelism within Phis as well as accelerator-level parallelism among multiple Phis. To facilitate balanced workload distribution, we have proposed a general framework for symmetric all-pairs computation by building bijective functions between job identifier and coordinate space for the first time. We have evaluated LightPCC and compared it to two CPU-based counterparts: a sequential C++ implementation in ALGLIB and an implementation based on a parallel general matrix-matrix multiplication routine in Intel Math Kernel Library (MKL) (all use double precision), using a set of gene expression datasets. Performance evaluation revealed that with one 5110P Phi and 16 Phis, LightPCC runs up to $20.6\times$ and $218.2\times$ faster than ALGLIB, and up to $6.8\times$ and $71.4\times$ faster than single-threaded MKL, respectively. In addition, LightPCC demonstrated good parallel scalability in terms of number of Phis. Source code of LightPCC is publicly available at http://lightpcc.sourceforge.net.
Notes on a model for fuzzy computing
Venue: arXiv cs.AI 2016
Year: 2016

In these notes we propose a setting for fuzzy computing in a framework similar to that of well-established theories of computation: boolean, and quantum computing. Our efforts have been directed towards stressing the formal similarities: there is a common pattern underlying these three theories. We tried to conform our approach, as much as possible, to this pattern. This work was part of a project jointly with Professor Vittorio Cafagna. Professor Cafagna passed away unexpectedly in 2007. His intellectual breadth and inspiring passion for mathematics is still very well alive.
On the Convergence of A Family of Robust Losses for Stochastic Gradient Descent
Venue: arXiv cs.LG 2016
Year: 2016

The convergence of Stochastic Gradient Descent (SGD) using convex loss functions has been widely studied. However, vanilla SGD methods using convex losses cannot perform well with noisy labels, which adversely affect the update of the primal variable in SGD methods. Unfortunately, noisy labels are ubiquitous in real world applications such as crowdsourcing. To handle noisy labels, in this paper, we present a family of robust losses for SGD methods. By employing our robust losses, SGD methods successfully reduce negative effects caused by noisy labels on each update of the primal variable. We not only reveal that the convergence rate is O(1/T) for SGD methods using robust losses, but also provide the robustness analysis on two representative robust losses. Comprehensive experimental results on six real-world datasets show that SGD methods using robust losses are obviously more robust than other baseline methods in most situations with fast convergence.
PipeGen: Data Pipe Generator for Hybrid Analytics
Venue: arXiv cs.DB 2016
Year: 2016

We develop a tool called PipeGen for efficient data transfer between database management systems (DBMSs). PipeGen targets data analytics workloads on shared-nothing engines. It supports scenarios where users seek to perform different parts of an analysis in different DBMSs or want to combine and analyze data stored in different systems. The systems may be colocated in the same cluster or may be in different clusters. To achieve high performance, PipeGen leverages the ability of all DBMSs to export, possibly in parallel, data into a common data format, such as CSV or JSON. It automatically extends these import and export functions with efficient binary data transfer capabilities that avoid materializing the transmitted data on the file system. We implement a prototype of PipeGen and evaluate it by automatically generating data pipes between five different DBMSs. Our experiments show that PipeGen delivers speedups up to 3.8x compared with manually exporting and importing data across systems using CSV.
A Many Antenna High Rate Wireless System
Venue: arXiv cs.IT 2016
Year: 2016

We describe a TDD MIMO wireless system designed to operate at high bandwidth and low SNR. Signals are transmitted as a direct sequence. In the uplink (Multiple Access Channel), signal detection is done by a space-time whitening filter followed by a matched filter. In the downlink (Broadcast Channel), precoding is done by the transpose of these filters. We further describe an implementation of this system that uses an array of 32 antennas to communicate with 32 single-antenna clients simultaneously on the same frequencies between 512-608 and 614-698 MHz. At close range, all 32 links achieve the full PHY data rate, both uplink and downlink, with less than 1\% Block Error Rate on each link. The total system rate is 3.8 Gb/s. The system spectral efficiency is 21.7 b/s/Hz for both uplink and downlink. We close with some projections to the not-to-distant future.
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{10/7} \log W)$ Time
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we study a set of combinatorial optimization problems on weighted graphs: the shortest path problem with negative weights, the weighted perfect bipartite matching problem, the unit-capacity minimum-cost maximum flow problem and the weighted perfect bipartite $b$-matching problem under the assumption that $\Vert b\Vert_1=O(m)$. We show that each one of these four problems can be solved in $\tilde{O}(m^{10/7}\log W)$ time, where $W$ is the absolute maximum weight of an edge in the graph, which gives the first in over 25 years polynomial improvement in their sparse-graph time complexity. At a high level, our algorithms build on the interior-point method-based framework developed by Madry (FOCS 2013) for solving unit-capacity maximum flow problem. We develop a refined way to analyze this framework, as well as provide new variants of the underlying preconditioning and perturbation techniques. Consequently, we are able to extend the whole interior-point method-based approach to make it applicable in the weighted graph regime.
Sentiment-enhanced Multidimensional Analysis of Online Social Networks: Perception of the Mediterranean Refugees Crisis
Venue: arXiv cs.SI 2016
Year: 2016

We propose an analytical framework able to investigate discussions about polarized topics in online social networks from many different angles. The framework supports the analysis of social networks along several dimensions: time, space and sentiment. We show that the proposed analytical framework and the methodology can be used to mine knowledge about the perception of complex social phenomena. We selected the refugee crisis discussions over Twitter as the case study. This difficult and controversial topic is an increasingly important issue for the EU. The raw stream of tweets is enriched with space information (user and mentioned locations), and sentiment (positive vs. negative) w.r.t. refugees. Our study shows differences in positive and negative sentiment in EU countries, in particular in UK, and by matching events, locations and perception it underlines opinion dynamics and common prejudices regarding the refugees.
User Reviews and Language: How Language Influences Ratings
Venue: arXiv cs.HC 2016
Year: 2016

The number of user reviews of tourist attractions, restaurants, mobile apps, etc. is increasing for all languages; yet, research is lacking on how reviews in multiple languages should be aggregated and displayed. Speakers of different languages may have consistently different experiences, e.g., different information available in different languages at tourist attractions or different user experiences with software due to internationalization/localization choices. This paper assesses the similarity in the ratings given by speakers of different languages to London tourist attractions on TripAdvisor. The correlations between different languages are generally high, but some language pairs are more correlated than others. The results question the common practice of computing average ratings from reviews in many languages.
UAV-based Autonomous Image Acquisition with Multi-View Stereo Quality Assurance by Confidence Prediction
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we present an autonomous system for acquiring close-range high-resolution images that maximize the quality of a later-on 3D reconstruction with respect to coverage, ground resolution and 3D uncertainty. In contrast to previous work, our system uses the already acquired images to predict the confidence in the output of a dense multi-view stereo approach without executing it. This confidence encodes the likelihood of a successful reconstruction with respect to the observed scene and potential camera constellations. Our prediction module runs in real-time and can be trained without any externally recorded ground truth. We use the confidence prediction for on-site quality assurance and for planning further views that are tailored for a specific multi-view stereo approach with respect to the given scene. We demonstrate the capabilities of our approach with an autonomous Unmanned Aerial Vehicle (UAV) in a challenging outdoor scenario.
Visual Saliency Based on Scale-Space Analysis in the Frequency Domain
Venue: arXiv cs.CV 2016
Year: 2016

We address the issue of visual saliency from three perspectives. First, we consider saliency detection as a frequency domain analysis problem. Second, we achieve this by employing the concept of {\it non-saliency}. Third, we simultaneously consider the detection of salient regions of different size. The paper proposes a new bottom-up paradigm for detecting visual saliency, characterized by a scale-space analysis of the amplitude spectrum of natural images. We show that the convolution of the {\it image amplitude spectrum} with a low-pass Gaussian kernel of an appropriate scale is equivalent to such an image saliency detector. The saliency map is obtained by reconstructing the 2-D signal using the original phase and the amplitude spectrum, filtered at a scale selected by minimizing saliency map entropy. A Hypercomplex Fourier Transform performs the analysis in the frequency domain. Using available databases, we demonstrate experimentally that the proposed model can predict human fixation data. We also introduce a new image database and use it to show that the saliency detector can highlight both small and large salient regions, as well as inhibit repeated distractors in cluttered images. In addition, we show that it is able to predict salient regions on which people focus their attention.
Deterministic MST Sparsification in the Congested Clique
Venue: arXiv cs.DC 2016
Year: 2016

We give a simple deterministic constant-round algorithm in the congested clique model for reducing the number of edges in a graph to $n^{1+\varepsilon}$ while preserving the minimum spanning forest, where $\varepsilon > 0$ is any constant. This implies that in the congested clique model, it is sufficient to improve MST and other connectivity algorithms on graphs with slightly superlinear number of edges to obtain a general improvement. As a byproduct, we also obtain a simple alternative proof showing that MST can be computed deterministically in $O(\log \log n)$ rounds.
Low-Complexity Stochastic Generalized Belief Propagation
Venue: arXiv cs.LG 2016
Year: 2016

The generalized belief propagation (GBP), introduced by Yedidia et al., is an extension of the belief propagation (BP) algorithm, which is widely used in different problems involved in calculating exact or approximate marginals of probability distributions. In many problems, it has been observed that the accuracy of GBP considerably outperforms that of BP. However, because in general the computational complexity of GBP is higher than BP, its application is limited in practice. In this paper, we introduce a stochastic version of GBP called stochastic generalized belief propagation (SGBP) that can be considered as an extension to the stochastic BP (SBP) algorithm introduced by Noorshams et al. They have shown that SBP reduces the complexity per iteration of BP by an order of magnitude in alphabet size. In contrast to SBP, SGBP can reduce the computation complexity if certain topological conditions are met by the region graph associated to a graphical model. However, this reduction can be larger than only one order of magnitude in alphabet size. In this paper, we characterize these conditions and the amount of computation gain that we can obtain by using SGBP. Finally, using similar proof techniques employed by Noorshams et al., for general graphical models satisfy contraction conditions, we prove the asymptotic convergence of SGBP to the unique GBP fixed point, as well as providing non-asymptotic upper bounds on the mean square error and on the high probability error.
A Perspective Study on Content Management in E-Learning and M-Learning
Venue: arXiv cs.CY 2016
Year: 2016

This is the era of Information and Communication Technology (ICT). Nowadays, there is no limit to learn, people can learn anywhere and anytime with the enhancement of technology. Electronic Learning (E-learning) and Mobile Learning (M-learning) are the two vital buzz terms in modern education particularly in Education Enhanced Technology and Technologies Supported Learning. E-learning is defined as the instructional content or learning experience delivered or enabled by electronic technologies whereas, M-learning is defined simply as learning via mobile devices such as cell phones, smart phones, palmtops, and handheld computers. There are many similarities between the two technologies as both are modern learning tools. Moreover, the latter is an extension and a subset of the former. However, there are few limitations or differences still exist in mobile learning tools, especially in the design, development and the technology usability. In this paper we have mainly focused on how the digital content is administrated (Content Management) in these two technologies. Additionally, the content management in E and Mlearning are compared and their similarities and differences are figured out.
Robust Dialog State Tracking for Large Ontologies
Venue: arXiv cs.CL 2016
Year: 2016

The Dialog State Tracking Challenge 4 (DSTC 4) differentiates itself from the previous three editions as follows: the number of slot-value pairs present in the ontology is much larger, no spoken language understanding output is given, and utterances are labeled at the subdialog level. This paper describes a novel dialog state tracking method designed to work robustly under these conditions, using elaborate string matching, coreference resolution tailored for dialogs and a few other improvements. The method can correctly identify many values that are not explicitly present in the utterance. On the final evaluation, our method came in first among 7 competing teams and 24 entries. The F1-score achieved by our method was 9 and 7 percentage points higher than that of the runner-up for the utterance-level evaluation and for the subdialog-level evaluation, respectively.
Solving generalized maximum-weight connected subgraph problem for network enrichment analysis
Venue: arXiv cs.DS 2016
Year: 2016

Network enrichment analysis methods allow to identify active modules without being biased towards a priori defined pathways. One of mathematical formulations of such analysis is a reduction to a maximum-weight connected subgraph problem. In particular, in analysis of metabolic networks a generalized maximum-weight connected subgraph (GMWCS) problem, where both nodes and edges are scored, naturally arises. Here we present the first to our knowledge practical exact GMWCS solver. We have tested it on real-world instances and compared to similar solvers. First, the results show that on node-weighted instances GMWCS solver has a similar performance to the best solver for that problem. Second, GMWCS solver is faster compared to the closest analogue when run on GMWCS instances with edge weights.
Formation of subject area and the co-authors network by sounding of Google Scholar Citations service
Venue: arXiv cs.DL 2016
Year: 2016

The suggested methodic is the way of formatting the subject areas models and co-authors networks by sounding the content networks. The paper represents the notion networks which match tags and authors of Google Scholar Citations service. Models depicted in the work were built for the physical optics area, and it can be applied for other domains. The proposed ways of defining connections between science areas and authors depicts the collaborations opportunities and versatility of interdisciplinary.
On the Capacity of the Beta-Binomial Channel Model for Multi-Level Cell Flash Memories
Venue: arXiv cs.IT 2016
Year: 2016

The beta-binomial (BBM) channel model was recently proposed to model the overdispersed statistics of empirically observed bit errors in multi-level cell (MLC) flash memories. In this paper, we study the capacity of the BBM channel model for MLC flash memories. Using the compound channel approach, we first show that the BBM channel model capacity is zero. However, through empirical observation, this appears to be a very pessimistic estimate of the flash memory channel capacity. We propose a refined channel model called the truncated-support beta-binomial (TS-BBM) channel model and derive its capacity. Using empirical error statistics from 1X-nm and 2Y-nm MLC flash memories, we numerically estimate the TS-BBM channel model capacity as a function of the program/erase (P/E) cycling stress. The capacity of the 2-TS-BBM channel model provides an upper bound on the coding rates for the flash memory chip assuming a single binary error correction code is used.
An institutional approach to computational social creativity
Venue: arXiv cs.CY 2016
Year: 2016

Modelling the creativity that takes place in social settings presents a range of theoretical challenges. Mel Rhodes's classic "4Ps" of creativity, the "Person, Process, Product, and Press," offer an initial typology. Here, Rhodes's ideas are connected with Elinor Ostrom's work on the analysis of economic governance to generate several "creativity design principles." These principles frame a survey of the shared concepts that structure the contexts that support creative work. The concepts are connected to the idea of computational "tests" to foreground the relationship with standard computing practice, and to draw out specific recommendations for the further development of computational creativity culture.
Robust Energy Harvesting Based on a Stackelberg Game
Venue: arXiv cs.IT 2016
Year: 2016

We study a Stackelberg game between a base station and a multi-antenna power beacon for wireless energy harvesting in a multiple sensor node scenario. Assuming imperfect CSI between the sensor nodes and the power beacon, we propose a utility function that is based on throughput non-outage probability at the base station. We provide an analytical solution for the equilibrium in case of a single sensor node. For the general case consisting of multiple sensor nodes, we provide upper and lower bounds on the power and price (players' strategies). We compare the bounds with solutions resulting from an exhaustive search and a relaxed semidefinite program, and find the upper bound to be tight.
Distance verification for LDPC codes
Venue: arXiv cs.IT 2016
Year: 2016

The problem of finding code distance has been long studied for the generic ensembles of linear codes and led to several algorithms that substantially reduce exponential complexity of this task. However, no asymptotic complexity bounds are known for distance verification in other ensembles of linear codes. Our goal is to re-design the existing generic algorithms of distance verification and derive their complexity for LDPC codes. We obtain new complexity bounds with provable performance expressed in terms of the erasure-correcting thresholds of long LDPC codes. These bounds exponentially reduce complexity estimates known for linear codes.
A broker-based framework for integrated SLA-aware SaaS Provisioning
Venue: arXiv cs.DC 2016
Year: 2016

In the service landscape, the issues of service selection, negotiation of Service Level Agreements (SLA), and SLA-compliance monitoring have typically been used in separate and disparate ways, which affect the quality of the services that consumers obtain from their providers. In this work, we propose a broker-based framework to deal with these concerns in an integrated manner for Software as a Service (SaaS) provisioning. The SaaS Broker selects a suitable SaaS provider on behalf of the service consumer by using a utility-driven selection algorithm that ranks the QoS offerings of potential SaaS providers. Then, it negotiates the SLA terms with that provider based on the quality requirements of the service consumer. The monitoring infrastructure observes SLA-compliance during service delivery by using measurements obtained from third-party monitoring services. We also define a utility-based bargaining decision model that allows the service consumer to express her sensitivity for each of the negotiated quality attributes and to evaluate the SaaS provider offer in each round of negotiation. A use-case with few quality attributes and their respective utility functions illustrates the approach.
Machine Learning Techniques with Ontology for Subjective Answer Evaluation
Venue: arXiv cs.AI 2016
Year: 2016

Computerized Evaluation of English Essays is performed using Machine learning techniques like Latent Semantic Analysis (LSA), Generalized LSA, Bilingual Evaluation Understudy and Maximum Entropy. Ontology, a concept map of domain knowledge, can enhance the performance of these techniques. Use of Ontology makes the evaluation process holistic as presence of keywords, synonyms, the right word combination and coverage of concepts can be checked. In this paper, the above mentioned techniques are implemented both with and without Ontology and tested on common input data consisting of technical answers of Computer Science. Domain Ontology of Computer Graphics is designed and developed. The software used for implementation includes Java Programming Language and tools such as MATLAB, Protégé, etc. Ten questions from Computer Graphics with sixty answers for each question are used for testing. The results are analyzed and it is concluded that the results are more accurate with use of Ontology.