OpenRaiser/Intern-Atlas huggingface dataset:
Towards a Benchmark and a Comparison Framework for Combinatorial Interaction Testing of Software Product Lines
Venue: arXiv cs.SE 2014
Year: 2014

As Software Product Lines (SPLs) are becoming a more pervasive development practice, their effective testing is becoming a more important concern. In the past few years many SPL testing approaches have been proposed, among them, are those that support Combinatorial Interaction Testing (CIT) whose premise is to select a group of products where faults, due to feature interactions, are more likely to occur. Many CIT techniques for SPL testing have been put forward; however, no systematic and comprehensive comparison among them has been performed. To achieve such goal two items are important: a common benchmark of feature models, and an adequate comparison framework. In this research-in-progress paper, we propose 19 feature models as the base of a benchmark, which we apply to three different techniques in order to analyze the comparison framework proposed by Perrouin et al. We identify the shortcomings of this framework and elaborate alternatives for further study.
0-1 Integer Linear Programming with a Linear Number of Constraints
Venue: arXiv cs.CC 2014
Year: 2014

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where n is the number of variables and cn is the number of constraints. The key idea for the algorithm is a reduction to the Vector Domination problem and a new algorithm for that subproblem.
Algebraic Methods of Classifying Directed Graphical Models
Venue: arXiv cs.IT 2014
Year: 2014

Directed acyclic graphical models (DAGs) are often used to describe common structural properties in a family of probability distributions. This paper addresses the question of classifying DAGs up to an isomorphism. By considering Gaussian densities, the question reduces to verifying equality of certain algebraic varieties. A question of computing equations for these varieties has been previously raised in the literature. Here it is shown that the most natural method adds spurious components with singular principal minors, proving a conjecture of Sullivant. This characterization is used to establish an algebraic criterion for isomorphism, and to provide a randomized algorithm for checking that criterion. Results are applied to produce a list of the isomorphism classes of tree models on 4,5, and 6 nodes. Finally, some evidence is provided to show that projectivized DAG varieties contain useful information in the sense that their relative embedding is closely related to efficient inference.
Peer Ratings in Massive Online Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

Instant quality feedback in the form of online peer ratings is a prominent feature of modern massive online social networks (MOSNs). It allows network members to indicate their appreciation of a post, comment, photograph, etc. Some MOSNs support both positive and negative (signed) ratings. In this study, we rated 11 thousand MOSN member profiles and collected user responses to the ratings. MOSN users are very sensitive to peer ratings: 33% of the subjects visited the researcher's profile in response to rating, 21% also rated the researcher's profile picture, and 5% left a text comment. The grades left by the subjects are highly polarized: out of the six available grades, the most negative and the most positive are also the most popular. The grades fall into three almost equally sized categories: reciprocal, generous, and stingy. We proposed quantitative measures for generosity, reciprocity, and benevolence, and analyzed them with respect to the subjects' demographics.
A Study of Various Steganographic Techniques Used for Information Hiding
Venue: arXiv cs.MM 2014
Year: 2014

Steganography derives from the Greek word steganos, meaning covered or secret, and graphy (writing or drawing). Steganography is a technology where modern data compression, information theory, spread spectrum, and cryptography technologies are brought together to satisfy the need for privacy on the Internet. This paper is an attempt to analyse the various techniques used in steganography and to identify areas in which this technique can be applied, so that the human race can be benefited at large.
Improved Online Square-into-Square Packing
Venue: arXiv cs.CG 2014
Year: 2014

In this paper, we show an improved bound and new algorithm for the online square-into-square packing problem. This two-dimensional packing problem involves packing an online sequence of squares into a unit square container without any two squares overlapping. The goal is to find the largest area $α$ such that any set of squares with total area $α$ can be packed. We show an algorithm that can pack any set of squares with total area $α\leq 3/8$ into a unit square in an online setting, improving the previous bound of $11/32$.
On the Complexity of Computing with Planar Algebraic Curves
Venue: arXiv cs.SC 2014
Year: 2014

In this paper, we give improved bounds for the computational complexity of computing with planar algebraic curves. More specifically, for arbitrary coprime polynomials $f$, $g \in \mathbb{Z}[x,y]$ and an arbitrary polynomial $h \in \mathbb{Z}[x,y]$, each of total degree less than $n$ and with integer coefficients of absolute value less than $2^τ$, we show that each of the following problems can be solved in a deterministic way with a number of bit operations bounded by $\tilde{O}(n^6+n^5τ)$, where we ignore polylogarithmic factors in $n$ and $τ$: (1) The computation of isolating regions in $\mathbb{C}^2$ for all complex solutions of the system $f = g = 0$, (2) the computation of a separating form for the solutions of $f = g = 0$, (3) the computation of the sign of $h$ at all real valued solutions of $f = g = 0$, and (4) the computation of the topology of the planar algebraic curve $\mathcal{C}$ defined as the real valued vanishing set of the polynomial $f$. Our bound improves upon the best currently known bounds for the first three problems by a factor of $n^2$ or more and closes the gap to the state-of-the-art randomized complexity for the last problem.
A refined analysis of the Poisson channel in the high-photon-efficiency regime
Venue: arXiv cs.IT 2014
Year: 2014

We study the discrete-time Poisson channel under the constraint that its average input power (in photons per channel use) must not exceed some constant E. We consider the wideband, high-photon-efficiency extreme where E approaches zero, and where the channel's "dark current" approaches zero proportionally with E. Improving over a previously obtained first-order capacity approximation, we derive a refined approximation, which includes the exact characterization of the second-order term, as well as an asymptotic characterization of the third-order term with respect to the dark current. We also show that pulse-position modulation is nearly optimal in this regime.
Reaserchnig the Development of the Electrical Power System Using Systemically Evolutionary Algorithm
Venue: arXiv cs.NE 2014
Year: 2014

The paper contains the concept and the results of research concerning the evolutionary algorithm, identified based on the systems control theory, which was called the Systemically of Evolutionary Algorithm (SAE). Special attention was paid to two elements of evolutionary algorithms, which have not been fully solved yet, i.e. to the methods used to create the initial population and the method of creating the robustness (fitness) function. Other elements of the SEA algorithm, i.a. cross-over, mutation, selection, etc. were also defined from a systemic point of view. Computational experiments were conducted using a selected subsystem of the Polish Electrical Power System and three programming languages: Java, C++ and Matlab. Selected comparative results for the SAE algorithm in different implementations were also presented.
Applications of Information Nonanticipative Rate Distortion Function
Venue: arXiv cs.IT 2014
Year: 2014

The objective of this paper is to further investigate various applications of information Nonanticipative Rate Distortion Function (NRDF) by discussing two working examples, the Binary Symmetric Markov Source with parameter $p$ (BSMS($p$)) with Hamming distance distortion, and the multidimensional partially observed Gaussian-Markov source. For the BSMS($p$), we give the solution to the NRDF, and we use it to compute the Rate Loss (RL) of causal codes with respect to noncausal codes. For the multidimensional Gaussian-Markov source, we give the solution to the NRDF, we show its operational meaning via joint source-channel matching over a vector of parallel Gaussian channels, and we compute the RL of causal and zero-delay codes with respect to noncausal codes.
A New Look at BDDs for Pseudo-Boolean Constraints
Venue: arXiv cs.AI 2014
Year: 2014

Pseudo-Boolean constraints are omnipresent in practical applications, and thus a significant effort has been devoted to the development of good SAT encoding techniques for them. Some of these encodings first construct a Binary Decision Diagram (BDD) for the constraint, and then encode the BDD into a propositional formula. These BDD-based approaches have some important advantages, such as not being dependent on the size of the coefficients, or being able to share the same BDD for representing many constraints. We first focus on the size of the resulting BDDs, which was considered to be an open problem in our research community. We report on previous work where it was proved that there are Pseudo-Boolean constraints for which no polynomial BDD exists. We also give an alternative and simpler proof assuming that NP is different from Co-NP. More interestingly, here we also show how to overcome the possible exponential blowup of BDDs by phcoefficient decomposition. This allows us to give the first polynomial generalized arc-consistent ROBDD-based encoding for Pseudo-Boolean constraints. Finally, we focus on practical issues: we show how to efficiently construct such ROBDDs, how to encode them into SAT with only 2 clauses per node, and present experimental results that confirm that our approach is competitive with other encodings and state-of-the-art Pseudo-Boolean solvers.
Complexity of Judgment Aggregation
Venue: arXiv cs.MA 2014
Year: 2014

We analyse the computational complexity of three problems in judgment aggregation: (1) computing a collective judgment from a profile of individual judgments (the winner determination problem); (2) deciding whether a given agent can influence the outcome of a judgment aggregation procedure in her favour by reporting insincere judgments (the strategic manipulation problem); and (3) deciding whether a given judgment aggregation scenario is guaranteed to result in a logically consistent outcome, independently from what the judgments supplied by the individuals are (the problem of the safety of the agenda). We provide results both for specific aggregation procedures (the quota rules, the premise-based procedure, and a distance-based procedure) and for classes of aggregation procedures characterised in terms of fundamental axioms.
State of the Practice in Software Effort Estimation: A Survey and Literature Review
Venue: arXiv cs.SE 2014
Year: 2014

Effort estimation is a key factor for software project success, defined as delivering software of agreed quality and functionality within schedule and budget. Traditionally, effort estimation has been used for planning and tracking project resources. Effort estimation methods founded on those goals typically focus on providing exact estimates and usually do not support objectives that have recently become important within the software industry, such as systematic and reliable analysis of causal effort dependencies. This article presents the results of a study of software effort estimation from an industrial perspective. The study surveys industrial objectives, the abilities of software organizations to apply certain estimation methods, and actually applied practices of software effort estimation. Finally, requirements for effort estimation methods identified in the survey are compared against existing estimation methods.
Hierarchical pixel clustering for image segmentation
Venue: arXiv cs.CV 2014
Year: 2014

In the paper a piecewise constant image approximations of sequential number of pixel clusters or segments are treated. A majorizing of optimal approximation sequence by hierarchical sequence of image approximations is studied. Transition from pixel clustering to image segmentation by reducing of segment numbers in clusters is provided. Algorithms are proved by elementary formulas.
On computing the $2$-vertex-connected components of directed graphs
Venue: arXiv cs.DS 2014
Year: 2014

In this paper we consider the problem of computing the $2$-vertex-connected components ($2$-vccs) of directed graphs. We present two new algorithms for solving this problem. The first algorithm runs in $O(mn^{2})$ time, the second in $O(nm)$ time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in $O(nm^{2})$ time. In this paper, we investigate the relationship between $2$-vccs and dominator trees. We also present an algorithm for computing the $3$-vertex-connected components ($3$-vccs) of a directed graph in $O(n^{3}m)$ time, and we show that the $k$-vertex-connected components ($k$-vccs) of a directed graph can be computed in $O(mn^{2k-3})$ time. Finally, we consider three applications of our new algorithms, which are approximation algorithms for problems that are generalization of the problem of approximating the smallest $2$-vertex-connected spanning subgraph of $2$-vertex-connected directed graph.
New Approaches to Website Fingerprinting Defenses
Venue: arXiv cs.CR 2014
Year: 2014

Website fingerprinting attacks enable an adversary to infer which website a victim is visiting, even if the victim uses an encrypting proxy, such as Tor. Previous work has shown that all proposed defenses against website fingerprinting attacks are ineffective. This paper advances the study of website fingerprinting attacks and defenses in two ways. First, we develop bounds on the trade-off between security and bandwidth overhead that any fingerprinting defense scheme can achieve. This enables us to compare schemes with different security/overhead trade-offs by comparing how close they are to the lower bound. We then refine, implement, and evaluate the Congestion Sensitive BuFLO scheme outlined by Cai, et al. CS-BuFLO, which is based on the provably-secure BuFLO defense proposed by Dyer, et al., was not fully-specified by Cai, et al, but has nonetheless attracted the attention of the Tor developers. Our experiments find that CS-BuFLO has high overhead (around 2.3-2.8x) but can get 6x closer to the bandwidth/security trade-off lower bound than Tor or plain SSH.
The Readability of Tweets and their Geographic Correlation with Education
Venue: arXiv cs.SI 2014
Year: 2014

Twitter has rapidly emerged as one of the largest worldwide venues for written communication. Thanks to the ease with which vast quantities of tweets can be mined, Twitter has also become a source for studying modern linguistic style. The readability of text has long provided a simple method to characterize the complexity of language and ease that documents may be understood by readers. In this note we use a modified version of the Flesch Reading Ease formula, applied to a corpus of 17.4 million tweets. We find tweets have characteristically more difficult readability scores compared to other short format communication, such as SMS or chat. This linguistic difference is insensitive to the presence of "hashtags" within tweets. By utilizing geographic data provided by 2% of users, joined with "ZIP Code Tabulation Area" (ZCTA) level education data from the U.S. Census, we find an intriguing correlation between the average readability and the college graduation rate within a ZCTA. This points towards a difference in either the underlying language, or a change in the type of content being tweeted in these areas
A Motivation Model of Peer Assessment in Programming Language Learning
Venue: arXiv cs.CY 2014
Year: 2014

Peer assessment is an efficient and effective learning assessment method that has been used widely in diverse fields in higher education. Despite its many benefits, a fundamental problem in peer assessment is that participants lack the motivation to assess others' work faithfully and fairly. Non-consensus is a common challenge that makes the reliability of peer assessment a primary concern in practices. This research proposes a motivation model that uses review deviation and radicalization to identify non-consensus in peer assessment. The proposed model is implemented as a software module in a peer code review system called EduPCR4. EduPCR4 is able to monitor this measure and trigger teacher's arbitration when it detects possible non-consensus. An empirical study conducted in a university-level C programming course showed that the proposed model and its implementation helped to improve the peer assessment practices in many aspects.
Controlling Complexity in Part-of-Speech Induction
Venue: arXiv cs.CL 2014
Year: 2014

We consider the problem of fully unsupervised learning of grammatical (part-of-speech) categories from unlabeled text. The standard maximum-likelihood hidden Markov model for this task performs poorly, because of its weak inductive bias and large model capacity. We address this problem by refining the model and modifying the learning objective to control its capacity via para- metric and non-parametric constraints. Our approach enforces word-category association sparsity, adds morphological and orthographic features, and eliminates hard-to-estimate parameters for rare words. We develop an efficient learning algorithm that is not much more computationally intensive than standard training. We also provide an open-source implementation of the algorithm. Our experiments on five diverse languages (Bulgarian, Danish, English, Portuguese, Spanish) achieve significant improvements compared with previous methods for the same task.
Capacity Bounds for a Class of Diamond Networks
Venue: arXiv cs.IT 2014
Year: 2014

A class of diamond networks are studied where the broadcast component is modelled by two independent bit-pipes. New upper and low bounds are derived on the capacity which improve previous bounds. The upper bound is in the form of a max-min problem, where the maximization is over a coding distribution and the minimization is over an auxiliary channel. The proof technique generalizes bounding techniques of Ozarow for the Gaussian multiple description problem (1981), and Kang and Liu for the Gaussian diamond network (2011). The bounds are evaluated for a Gaussian multiple access channel (MAC) and the binary adder MAC, and the capacity is found for interesting ranges of the bit-pipe capacities.
Distributed Remote Vector Gaussian Source Coding with Covariance Distortion Constraints
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider a distributed remote source coding problem, where a sequence of observations of source vectors is available at the encoder. The problem is to specify the optimal rate for encoding the observations subject to a covariance matrix distortion constraint and in the presence of side information at the decoder. For this problem, we derive lower and upper bounds on the rate-distortion function (RDF) for the Gaussian case, which in general do not coincide. We then provide some cases, where the RDF can be derived exactly. We also show that previous results on specific instances of this problem can be generalized using our results. We finally show that if the distortion measure is the mean squared error, or if it is replaced by a certain mutual information constraint, the optimal rate can be derived from our main result.
Is Extreme Learning Machine Feasible? A Theoretical Assessment (Part II)
Venue: arXiv cs.LG 2014
Year: 2014

An extreme learning machine (ELM) can be regarded as a two stage feed-forward neural network (FNN) learning system which randomly assigns the connections with and within hidden neurons in the first stage and tunes the connections with output neurons in the second stage. Therefore, ELM training is essentially a linear learning problem, which significantly reduces the computational burden. Numerous applications show that such a computation burden reduction does not degrade the generalization capability. It has, however, been open that whether this is true in theory. The aim of our work is to study the theoretical feasibility of ELM by analyzing the pros and cons of ELM. In the previous part on this topic, we pointed out that via appropriate selection of the activation function, ELM does not degrade the generalization capability in the expectation sense. In this paper, we launch the study in a different direction and show that the randomness of ELM also leads to certain negative consequences. On one hand, we find that the randomness causes an additional uncertainty problem of ELM, both in approximation and learning. On the other hand, we theoretically justify that there also exists an activation function such that the corresponding ELM degrades the generalization capability. In particular, we prove that the generalization capability of ELM with Gaussian kernel is essentially worse than that of FNN with Gaussian kernel. To facilitate the use of ELM, we also provide a remedy to such a degradation. We find that the well-developed coefficient regularization technique can essentially improve the generalization capability. The obtained results reveal the essential characteristic of ELM and give theoretical guidance concerning how to use ELM.
On measuring team stability in cooperative learning: An example of consecutive course projects on software engineering
Venue: arXiv cs.CY 2014
Year: 2014

Cooperative learning theory has shown that stable membership is a hallmark of effective work teams. According to relation strength and social network centrality, this paper proposes an approach to measure team stability reasons in consecutive cooperative learning. Taking consecutive course projects of software engineering in a university as examples, we examine the relation between team stability and learning performance in consecutive cooperative learning from two parts: learning score and learning satisfaction. Through empirical analysis, it arrives at the conclusion that learning score is in weak positive correlation with team stability. Through questionnaire and interviews, it finds out 78% of the students did not value the importance of team stability, and 67% of the teachers never recommend the students to keep stable teams. Finally, we put forward an expected correlation model of learning performance as future work and discuss instability as well.
On Combinatorial Generation of Prefix Normal Words
Venue: arXiv cs.DS 2014
Year: 2014

A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present an efficient algorithm for exhaustively listing the prefix normal words with a fixed length. The algorithm is based on the fact that the language of prefix normal words is a bubble language, a class of binary languages with the property that, for any word w in the language, exchanging the first occurrence of 01 by 10 in w results in another word in the language. We prove that each prefix normal word is produced in O(n) amortized time, and conjecture, based on experimental evidence, that the true amortized running time is O(polylog(n)).