OpenRaiser/Intern-Atlas huggingface dataset:
Friends or Foes: Distributed and Randomized Algorithms to Determine Dishonest Recommenders in Online Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

Viral marketing is becoming important due to the popularity of online social networks (OSNs). Companies may provide incentives (e.g., via free samples of a product) to a small group of users in an OSN, and these users provide recommendations to their friends, which eventually increases the overall sales of a given product. Nevertheless, this also opens a door for "malicious behaviors": dishonest users may intentionally give misleading recommendations to their friends so as to distort the normal sales distribution. In this paper, we propose a detection framework to identify dishonest users in OSNs. In particular, we present a set of fully distributed and randomized algorithms, and also quantify the performance of the algorithms by deriving probability of false positive, probability of false negative, and the distribution of number of detection rounds. Extensive simulations are also carried out to illustrate the impact of misleading recommendations and the effectiveness of our detection algorithms. The methodology we present here will enhance the security level of viral marketing in OSNs.
Deep Metric Learning for Practical Person Re-Identification
Venue: arXiv cs.CV 2014
Year: 2014

Various hand-crafted features and metric learning methods prevail in the field of person re-identification. Compared to these methods, this paper proposes a more general way that can learn a similarity metric from image pixels directly. By using a "siamese" deep neural network, the proposed method can jointly learn the color feature, texture feature and metric in a unified framework. The network has a symmetry structure with two sub-networks which are connected by Cosine function. To deal with the big variations of person images, binomial deviance is used to evaluate the cost between similarities and labels, which is proved to be robust to outliers. Compared to existing researches, a more practical setting is studied in the experiments that is training and test on different datasets (cross dataset person re-identification). Both in "intra dataset" and "cross dataset" settings, the superiorities of the proposed method are illustrated on VIPeR and PRID.
Solving Large Imperfect Information Games Using CFR+
Venue: arXiv cs.GT 2014
Year: 2014

Counterfactual Regret Minimization and variants (e.g. Public Chance Sampling CFR and Pure CFR) have been known as the best approaches for creating approximate Nash equilibrium solutions for imperfect information games such as poker. This paper introduces CFR$^+$, a new algorithm that typically outperforms the previously known algorithms by an order of magnitude or more in terms of computation time while also potentially requiring less memory.
Supporting Read/Write Applications in Embedded Real-time Systems via Suspension-aware Analysis
Venue: arXiv cs.OH 2014
Year: 2014

In many embedded real-time systems, applications often interact with I/O devices via read/write operations, which may incur considerable suspension delays. Unfortunately, prior analysis methods for validating timing correctness in embedded systems become quite pessimistic when suspension delays are present. In this paper, we consider the problem of supporting two common types of I/O applications in a multiprocessor system, that is, write-only applications and read-write applications. For the write-only application model, we present a much improved analysis technique that results in only O(m) suspension-related utilization loss, where m is the number of processors. For the second application model, we present a flexible I/O placement strategy and a corresponding new scheduling algorithm, which can completely circumvent the negative impact due to read- and write-induced suspension delays. We illustrate the feasibility of the proposed I/O-placement-based schedule via a case study implementation. Furthermore, experiments presented herein show that the improvement with respect to system utilization over prior methods is often significant.
Channel Estimation and Optimal Training Design for Correlated MIMO Two-Way Relay Systems in Colored Environment
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, while considering the impact of antenna correlation and the interference from neighboring users, we analyze channel estimation and training sequence design for multi-input multi-output (MIMO) two-way relay (TWR) systems. To this end, we propose to decompose the bidirectional transmission links into two phases, i.e., the multiple access (MAC) phase and the broadcasting (BC) phase. By considering the Kronecker-structured channel model, we derive the optimal linear minimum mean-square-error (LMMSE) channel estimators. The corresponding training designs for the MAC and BC phases are then formulated and solved to improve channel estimation accuracy. For the general scenario of training sequence design for both phases, two iterative training design algorithms are proposed that are verified to produce training sequences that result in near optimal channel estimation performance. Furthermore, for specific practical scenarios, where the covariance matrices of the channel or disturbances are of particular structures, the optimal training sequence design guidelines are derived. In order to reduce training overhead, the minimum required training length for channel estimation in both the MAC and BC phases are also derived. Comprehensive simulations are carried out to demonstrate the effectiveness of the proposed training designs.
Towards Feature Engineering at Scale for Data from Massive Open Online Courses
Venue: arXiv cs.CY 2014
Year: 2014

We examine the process of engineering features for developing models that improve our understanding of learners' online behavior in MOOCs. Because feature engineering relies so heavily on human insight, we argue that extra effort should be made to engage the crowd for feature proposals and even their operationalization. We show two approaches where we have started to engage the crowd. We also show how features can be evaluated for their relevance in predictive accuracy. When we examined crowd-sourced features in the context of predicting stopout, not only were they nuanced, but they also considered more than one interaction mode between the learner and platform and how the learner was relatively performing. We were able to identify different influential features for stop out prediction that depended on whether a learner was in 1 of 4 cohorts defined by their level of engagement with the course discussion forum or wiki. This report is part of a compendium which considers different aspects of MOOC data science and stop out prediction.
Object Proposal Generation using Two-Stage Cascade SVMs
Venue: arXiv cs.CV 2014
Year: 2014

Object proposal algorithms have shown great promise as a first step for object recognition and detection. Good object proposal generation algorithms require high object recall rate as well as low computational cost, because generating object proposals is usually utilized as a preprocessing step. The problem of how to accelerate the object proposal generation and evaluation process without decreasing recall is thus of great interest. In this paper, we propose a new object proposal generation method using two-stage cascade SVMs, where in the first stage linear filters are learned for predefined quantized scales/aspect-ratios independently, and in the second stage a global linear classifier is learned across all the quantized scales/aspect-ratios for calibration, so that all the proposals can be compared properly. The proposals with highest scores are our final output. Specifically, we explain our scale/aspect-ratio quantization scheme, and investigate the effects of combinations of $\ell_1$ and $\ell_2$ regularizers in cascade SVMs with/without ranking constraints in learning. Comprehensive experiments on VOC2007 dataset are conducted, and our results achieve the state-of-the-art performance with high object recall rate and high computational efficiency. Besides, our method has been demonstrated to be suitable for not only class-specific but also generic object proposal generation.
Privacy-Preserving Important Passage Retrieval
Venue: arXiv cs.IR 2014
Year: 2014

State-of-the-art important passage retrieval methods obtain very good results, but do not take into account privacy issues. In this paper, we present a privacy preserving method that relies on creating secure representations of documents. Our approach allows for third parties to retrieve important passages from documents without learning anything regarding their content. We use a hashing scheme known as Secure Binary Embeddings to convert a key phrase and bag-of-words representation to bit strings in a way that allows the computation of approximate distances, instead of exact ones. Experiments show that our secure system yield similar results to its non-private counterpart on both clean text and noisy speech recognized text.
Code Review For and By Scientists
Venue: arXiv cs.SE 2014
Year: 2014

We describe two pilot studies of code review by and for scientists. Our principal findings are that scientists are enthusiastic, but need to be shown code review in action, and that just-in-time review of small code changes is more likely to succeed than large-scale end-of-work reviews.
PGMHD: A Scalable Probabilistic Graphical Model for Massive Hierarchical Data Problems
Venue: arXiv cs.AI 2014
Year: 2014

In the big data era, scalability has become a crucial requirement for any useful computational model. Probabilistic graphical models are very useful for mining and discovering data insights, but they are not scalable enough to be suitable for big data problems. Bayesian Networks particularly demonstrate this limitation when their data is represented using few random variables while each random variable has a massive set of values. With hierarchical data - data that is arranged in a treelike structure with several levels - one would expect to see hundreds of thousands or millions of values distributed over even just a small number of levels. When modeling this kind of hierarchical data across large data sets, Bayesian networks become infeasible for representing the probability distributions for the following reasons: i) Each level represents a single random variable with hundreds of thousands of values, ii) The number of levels is usually small, so there are also few random variables, and iii) The structure of the network is predefined since the dependency is modeled top-down from each parent to each of its child nodes, so the network would contain a single linear path for the random variables from each parent to each child node. In this paper we present a scalable probabilistic graphical model to overcome these limitations for massive hierarchical data. We believe the proposed model will lead to an easily-scalable, more readable, and expressive implementation for problems that require probabilistic-based solutions for massive amounts of hierarchical data. We successfully applied this model to solve two different challenging probabilistic-based problems on massive hierarchical data sets for different domains, namely, bioinformatics and latent semantic discovery over search logs.
Multilevel Diversity Coding Systems: Rate Regions, Codes, Computation, & Forbidden Minors
Venue: arXiv cs.IT 2014
Year: 2014

The rate regions of multilevel diversity coding systems (MDCS), a sub-class of the broader family of multi-source multi-sink networks with special structure, are investigated. After showing how to enumerate all non-isomorphic MDCS instances of a given size, the Shannon outer bound and several achievable inner bounds based on linear codes are given for the rate region of each non-isomorphic instance. For thousands of MDCS instances, the bounds match, and hence exact rate regions are proven. Results gained from these computations are summarized in key statistics involving aspects such as the sufficiency of scalar binary codes, the necessary size of vector binary codes, etc. Also, it is shown how to generate computer aided human readable converse proofs, as well as how to construct the codes for an achievability proof. Based on this large repository of rate regions, a series of results about general MDCS cases that they inspired are introduced and proved. In particular, a series of embedding operations that preserve the property of sufficiency of scalar or vector codes are presented. The utility of these operations is demonstrated by boiling the thousands of MDCS instances for which binary scalar codes are insufficient down to 12 forbidden smallest embedded MDCS instances.
A Constant-Factor Approximation for Multi-Covering with Disks
Venue: arXiv cs.CG 2014
Year: 2014

We consider variants of the following multi-covering problem with disks. We are given two point sets $Y$ (servers) and $X$ (clients) in the plane, a coverage function $κ:X \rightarrow \mathcal{N}$, and a constant $α\geq 1$. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client $x \in X$ be covered by at least $κ(x)$ of the server disks. The objective function we wish to minimize is the sum of the $α$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.
Sustainable Software Ecosystems: Software Engineers, Domain Scientists, and Engineers Collaborating for Science
Venue: arXiv cs.SE 2014
Year: 2014

The development of scientific software is often a partnership between domain scientists and scientific software engineers. It is especially important to embrace these collaborations when developing advanced scientific software, where sustainability, reproducibility, and extensibility are important. In the ideal case, as discussed in this manuscript, this brings together teams composed of the world's foremost scientific experts in a given field with seasoned software developers experienced in forming highly collaborative teams working on software to further scientific research.
Assessing the Performance of Question-and-Answer Communities Using Survival Analysis
Venue: arXiv cs.HC 2014
Year: 2014

Question-&-Answer (QA) websites have emerged as efficient platforms for knowledge sharing and problem solving. In particular, the Stack Exchange platform includes some of the most popular QA communities to date, such as Stack Overflow. Initial metrics used to assess the performance of these communities include summative statistics like the percentage of resolved questions or the average time to receive and validate correct answers. However, more advanced methods for longitudinal data analysis can provide further insights on the QA process, by enabling identification of key predictive factors and systematic comparison of performance across different QA communities. In this paper, we apply survival analysis to a selection of communities from the Stack Exchange platform. We illustrate the advantages of using the proposed methodology to characterize and evaluate the performance of QA communities, and then point to some implications for the design and management of QA platforms.
"Can I Implement Your Algorithm?": A Model for Reproducible Research Software
Venue: arXiv cs.SE 2014
Year: 2014

The reproduction and replication of novel results has become a major issue for a number of scientific disciplines. In computer science and related computational disciplines such as systems biology, the issues closely revolve around the ability to implement novel algorithms and approaches. Taking an approach from the literature and applying it to a new codebase frequently requires local knowledge missing from the published manuscripts and project websites. Alongside this issue, benchmarking, and the development of fair --- and widely available --- benchmark sets present another barrier. In this paper, we outline several suggestions to address these issues, driven by specific examples from a range of scientific domains. Finally, based on these suggestions, we propose a new open platform for scientific software development which effectively isolates specific dependencies from the individual researcher and their workstation and allows faster, more powerful sharing of the results of scientific software engineering.
Data Dissemination Performance in Large-Scale Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

As the use of wireless sensor networks increases, the need for (energy-)efficient and reliable broadcasting algorithms grows. Ideally, a broadcasting algorithm should have the ability to quickly disseminate data, while keeping the number of transmissions low. In this paper we develop a model describing the message count in large-scale wireless sensor networks. We focus our attention on the popular Trickle algorithm, which has been proposed as a suitable communication protocol for code maintenance and propagation in wireless sensor networks. Besides providing a mathematical analysis of the algorithm, we propose a generalized version of Trickle, with an additional parameter defining the length of a listen-only period. This generalization proves to be useful for optimizing the design and usage of the algorithm. For single-cell networks we show how the message count increases with the size of the network and how this depends on the Trickle parameters. Furthermore, we derive distributions of inter-broadcasting times and investigate their asymptotic behavior. Our results prove conjectures made in the literature concerning the effect of a listen-only period. Additionally, we develop an approximation for the expected number of transmissions in multi-cell networks. All results are validated by simulations.
SMaRtLight: A Practical Fault-Tolerant SDN Controller
Venue: arXiv cs.NI 2014
Year: 2014

The increase in the number of SDN-based deployments in production networks is triggering the need to consider fault-tolerant designs of controller architectures. Commercial SDN controller solutions incorporate fault tolerance, but there has been little discussion in the SDN literature on the design of such systems and the tradeoffs involved. To fill this gap, we present a by-construction design of a fault-tolerant controller, and materialize it by proposing and formalizing a practical architecture for small to medium-sized scale networks. A central component of our particular design is a replicated shared database that stores all network state. Contrary to the more common primary-backup approaches, the proposed design guarantees a smooth transition in case of failures and avoids the need of an additional coordination service. Our preliminary results show that the performance of our solution fulfills the demands of the target networks. We hope this paper to be a first step in what we consider a necessary discussion on how to build robust SDNs.
An automatic architecture reconstruction and refactoring framework
Venue: arXiv cs.SE 2014
Year: 2014

A variety of sources have noted that a substantial proportion of non trivial software systems fail due to unhindered architectural erosion. This design deterioration leads to low maintainability, poor testability and reduced development speed. The erosion of software systems is often caused by inadequate understanding, documentation and maintenance of the desired implementation architecture. If the desired architecture is lost or the deterioration is advanced, the reconstruction of the desired architecture and the realignment of this desired architecture with the physical architecture both require substantial manual analysis and implementation effort. This paper describes the initial development of a framework for automatic software architecture reconstruction and source code migration. This framework offers the potential to reconstruct the conceptual architecture of software systems and to automatically migrate the physical architecture of a software system toward a conceptual architecture model. The approach is implemented within a proof of concept prototype which is able to analyze java system and reconstruct a conceptual architecture for these systems as well as to refactor the system towards a conceptual architecture.
Automating Proofs of Data-Structure Properties in Imperative Programs
Venue: arXiv cs.PL 2014
Year: 2014

We consider the problem of automated reasoning about dynamically manipulated data structures. The state-of-the-art methods are limited to the unfold-and-match (U+M) paradigm, where predicates are transformed via (un)folding operations induced from their definitions before being treated as uninterpreted. However, proof obligations from verifying programs with iterative loops and multiple function calls often do not succumb to this paradigm. Our contribution is a proof method which -- beyond U+M -- performs automatic formula re-writing by treating previously encountered obligations in each proof path as possible induction hypotheses. This enables us, for the first time, to systematically reason about a wide range of obligations, arising from practical program verification. We demonstrate the power of our proof rules on commonly used lemmas, thereby close the remaining gaps in existing state-of-the-art systems. Another impact, probably more important, is that our method regains the power of compositional reasoning, and shows that the usage of user-provided lemmas is no longer needed for the existing set of benchmarks. This not only removes the burden of coming up with the appropriate lemmas, but also significantly boosts up the verification process, since lemma applications, coupled with unfolding, often induce very large search space.
scikit-image: Image processing in Python
Venue: arXiv cs.MS 2014
Year: 2014

scikit-image is an image processing library that implements algorithms and utilities for use in research, education and industry applications. It is released under the liberal "Modified BSD" open source license, provides a well-documented API in the Python programming language, and is developed by an active, international team of collaborators. In this paper we highlight the advantages of open source to achieve the goals of the scikit-image library, and we showcase several real-world image processing applications that use scikit-image.
Adaptive Fault Diagnosis using Self-Referential Reasoning
Venue: arXiv cs.OH 2014
Year: 2014

The problem is to determine which processors are reliable in a remote location by asking "Yes or No" questions. The processors are of three types: those that always tell the truth, those that always lie, and those the sometimes tell the truth and sometimes lie. Using self-referential reasoning, along with earlier techniques, we can regard both the truth-tellers and liars as reliable and thus the tackle situations when fewer than half the processors are truth-tellers.
Symmetric Disclosure: a Fresh Look at k-Anonymity
Venue: arXiv cs.CR 2014
Year: 2014

We analyze how the sparsity of a typical aggregate social relation impacts the network overhead of online communication systems designed to provide k-anonymity. Once users are grouped in anonymity sets there will likely be few related pairs of users between any two particular sets, and so the sets need to be large in order to provide cover traffic between them. We can reduce the associated overhead by having both parties in a communication specify both the origin and the target sets of the communication. We propose to call this communication primitive "symmetric disclosure." If in order to retrieve messages a user specifies a group from which he expects to receive them, the negative impact of the sparsity is offset.
On the distance preserving trees in graphs
Venue: arXiv cs.DM 2014
Year: 2014

For a vertex $v$ of a graph $G$, a spanning tree $T$ of $G$ is distance-preserving from $v$ if, for any vertex $w$, the distance from $v$ to $w$ on $T$ is the same as the distance from $v$ to $w$ on $G$. If two vertices $u$ and $v$ are distinct, then two distance-preserving spanning trees $T_{u}$ from $u$ and $T_{v}$ from $v$ are distinct in general. A purpose of this paper is to give a characterization for a given weighted graph $G$ to have a spanning tree $T$ such that $T$ is a distance-preserving spanning tree from distinct two vertices.