OpenRaiser/Intern-Atlas huggingface dataset:
Applicability of Educational Data Mining in Afghanistan: Opportunities and Challenges
Venue: arXiv cs.CY 2017
Year: 2017

The author's own experience as a student and later as a lecturer in Afghanistan has shown that the methods used in the educational system are not only flawed, but also do not provide the minimum guidance to students to select proper course of study before they enter the national university entrance (Kankor) exam. Thus, it often results in high attrition rates and poor performance in higher education. Based on the studies done in other countries, and by the author of this paper through online questionnaires distributed to university students in Afghanistan - it was found that proper procedures and specialized studies in high schools can help students in selecting their major field of study more systematically. Additionally, it has come to be known that there are large amounts of data available for mining purposes, but the methods that the Ministry of Education and Ministry of Higher Education use to store and produce their data, only enable them to achieve simple facts and figures. Furthermore, from the results it can be concluded that there are potential opportunities for educational data mining application in the domain of Afghanistan's education systems. Finally, this study will provide the readers with approaches for using Educational Data Mining to improve the educational business processes. For instance, predict proper field of study for high school graduates, or, identify first year university students who are at high risk of attrition.
An Optimized Analogy-Based Project Effort Estimation
Venue: arXiv cs.SE 2017
Year: 2017

Despite the predictive performance of Analogy-Based Estimation (ABE) in generating better effort estimates, there is no consensus on how to predict the best number of analogies, and which adjustment technique produces better estimates. This paper proposes a new adjusted ABE model based on optimizing and approximating complex relationships between features and reflects that approximation on the final estimate. The results show that the predictive performance of ABE has noticeably been improved, and the number of analogies was remarkably variable for each test project.
Learning best K analogies from data distribution for case-based software effort estimation
Venue: arXiv cs.SE 2017
Year: 2017

Case-Based Reasoning (CBR) has been widely used to generate good software effort estimates. The predictive performance of CBR is a dataset dependent and subject to extremely large space of configuration possibilities. Regardless of the type of adaptation technique, deciding on the optimal number of similar cases to be used before applying CBR is a key challenge. In this paper we propose a new technique based on Bisecting k-medoids clustering algorithm to better understanding the structure of a dataset and discovering the the optimal cases for each individual project by excluding irrelevant cases. Results obtained showed that understanding of the data characteristic prior prediction stage can help in automatically finding the best number of cases for each test project. Performance figures of the proposed estimation method are better than those of other regular K-based CBR methods.
Causes of discomfort in stereoscopic content: a review
Venue: arXiv cs.HC 2017
Year: 2017

This paper reviews the causes of discomfort in viewing stereoscopic content. These include objective factors, such as misaligned images, as well as subjective factors, such as excessive disparity. Different approaches to the measurement of visual discomfort are also reviewed, in relation to the underlying physiological and psychophysical processes. The importance of understanding these issues, in the context of new display technologies, is emphasized.
Verification in Staged Tile Self-Assembly
Venue: arXiv cs.CC 2017
Year: 2017

We prove the unique assembly and unique shape verification problems, benchmark measures of self-assembly model power, are $\mathrm{coNP}^{\mathrm{NP}}$-hard and contained in $\mathrm{PSPACE}$ (and in $\mathrmΠ^\mathrm{P}_{2s}$ for staged systems with $s$ stages). En route, we prove that unique shape verification problem in the 2HAM is $\mathrm{coNP}^{\mathrm{NP}}$-complete.
A Framework for Dynamic Image Sampling Based on Supervised Learning (SLADS)
Venue: arXiv cs.CV 2017
Year: 2017

Sparse sampling schemes have the potential to dramatically reduce image acquisition time while simultaneously reducing radiation damage to samples. However, for a sparse sampling scheme to be useful it is important that we are able to reconstruct the underlying object with sufficient clarity using the sparse measurements. In dynamic sampling, each new measurement location is selected based on information obtained from previous measurements. Therefore, dynamic sampling schemes have the potential to dramatically reduce the number of measurements needed for high fidelity reconstructions. However, most existing dynamic sampling methods for point-wise measurement acquisition tend to be computationally expensive and are therefore too slow for practical applications. In this paper, we present a framework for dynamic sampling based on machine learning techniques, which we call a supervised learning approach for dynamic sampling (SLADS). In each step of SLADS, the objective is to find the pixel that maximizes the expected reduction in distortion (ERD) given previous measurements. SLADS is fast because we use a simple regression function to compute the ERD, and it is accurate because the regression function is trained using data sets that are representative of the specific application. In addition, we introduce a method to terminate dynamic sampling at a desired level of distortion, and we extended the SLADS methodology to sample groups of pixels at each step. Finally, we present results on computationally-generated synthetic data and experimentally-collected data to demonstrate a dramatic improvement over state-of-the-art static sampling methods.
Geometry-Based Region Proposals for Real-Time Robot Detection of Tabletop Objects
Venue: arXiv cs.RO 2017
Year: 2017

We present a novel object detection pipeline for localization and recognition in three dimensional environments. Our approach makes use of an RGB-D sensor and combines state-of-the-art techniques from the robotics and computer vision communities to create a robust, real-time detection system. We focus specifically on solving the object detection problem for tabletop scenes, a common environment for assistive manipulators. Our detection pipeline locates objects in a point cloud representation of the scene. These clusters are subsequently used to compute a bounding box around each object in the RGB space. Each defined patch is then fed into a Convolutional Neural Network (CNN) for object recognition. We also demonstrate that our region proposal method can be used to develop novel datasets that are both large and diverse enough to train deep learning models, and easy enough to collect that end-users can develop their own datasets. Lastly, we validate the resulting system through an extensive analysis of the accuracy and run-time of the full pipeline.
Some connections between universal algebra and logics for trees
Venue: arXiv cs.FL 2017
Year: 2017

One of the major open problems in automata and logic is the following: is there an algorithm which inputs a regular tree language and decides if the language can be defined in first-order logic? The goal of this paper is to present this problem and similar ones using the language of universal algebra, highlighting potential connections to the structural theory of finite algebras, including Tame Congruence Theory.
Towards Moral Autonomous Systems
Venue: arXiv cs.AI 2017
Year: 2017

Both the ethics of autonomous systems and the problems of their technical implementation have by now been studied in some detail. Less attention has been given to the areas in which these two separate concerns meet. This paper, written by both philosophers and engineers of autonomous systems, addresses a number of issues in machine ethics that are located at precisely the intersection between ethics and engineering. We first discuss the main challenges which, in our view, machine ethics posses to moral philosophy. We them consider different approaches towards the conceptual design of autonomous systems and their implications on the ethics implementation in such systems. Then we examine problematic areas regarding the specification and verification of ethical behavior in autonomous systems, particularly with a view towards the requirements of future legislation. We discuss transparency and accountability issues that will be crucial for any future wide deployment of autonomous systems in society. Finally we consider the, often overlooked, possibility of intentional misuse of AI systems and the possible dangers arising out of deliberately unethical design, implementation, and use of autonomous robots.
Near-Optimal Compression for the Planar Graph Metric
Venue: arXiv cs.DS 2017
Year: 2017

The Planar Graph Metric Compression Problem is to compactly encode the distances among $k$ nodes in a planar graph of size $n$. Two naïve solutions are to store the graph using $O(n)$ bits, or to explicitly store the distance matrix with $O(k^2 \log{n})$ bits. The only lower bounds are from the seminal work of Gavoille, Peleg, Prennes, and Raz [SODA'01], who rule out compressions into a polynomially smaller number of bits, for {\em weighted} planar graphs, but leave a large gap for unweighted planar graphs. For example, when $k=\sqrt{n}$, the upper bound is $O(n)$ and their constructions imply an $Ω(n^{3/4})$ lower bound. This gap is directly related to other major open questions in labelling schemes, dynamic algorithms, and compact routing. Our main result is a new compression of the planar graph metric into $\tilde{O}(\min (k^2 , \sqrt{k\cdot n}))$ bits, which is optimal up to log factors. Our data structure breaks an $Ω(k^2)$ lower bound of Krauthgamer, Nguyen, and Zondiner [SICOMP'14] for compression using minors, and the lower bound of Gavoille et al. for compression of weighted planar graphs. This is an unexpected and decisive proof that weights can make planar graphs inherently more complex. Moreover, we design a new {\em Subset Distance Oracle} for planar graphs with $\tilde O(\sqrt{k\cdot n})$ space, and $\tilde O(n^{3/4})$ query time. Our work carries strong messages to related fields. In particular, the famous $O(n^{1/2})$ vs. $Ω(n^{1/3})$ gap for distance labelling schemes in planar graphs {\em cannot} be resolved with the current lower bound techniques.
SNE: Signed Network Embedding
Venue: arXiv cs.SI 2017
Year: 2017

Several network embedding models have been developed for unsigned networks. However, these models based on skip-gram cannot be applied to signed networks because they can only deal with one type of link. In this paper, we present our signed network embedding model called SNE. Our SNE adopts the log-bilinear model, uses node representations of all nodes along a given path, and further incorporates two signed-type vectors to capture the positive or negative relationship of each edge along the path. We conduct two experiments, node classification and link prediction, on both directed and undirected signed networks and compare with four baselines including a matrix factorization method and three state-of-the-art unsigned network embedding models. The experimental results demonstrate the effectiveness of our signed network embedding.
Low-complexity Location-aware Multi-user Massive MIMO Beamforming for High Speed Train Communications
Venue: arXiv cs.IT 2017
Year: 2017

Massive Multiple-input Multiple-output (MIMO) adaption is one of the primary evolving objectives for the next generation high speed train (HST) communication system. In this paper, we consider how to design an efficient low-complexity location-aware beamforming for the multi-user (MU) massive MIMO system in HST scenario. We first put forward a low-complexity beamforming based on location information, where multiple users are considered. Then, without considering inter-beam interference, a closed-form solution to maximize the total service competence of base station (BS) is proposed in this MU HST scenario. Finally, we present a location-aid searching-based suboptimal solution to eliminate the inter-beam interference and maximize the BS service competence. Various simulations are given to exhibit the advantages of our proposed massive MIMO beamforming method.
Quantification of De-anonymization Risks in Social Networks
Venue: arXiv cs.SI 2017
Year: 2017

The risks of publishing privacy-sensitive data have received considerable attention recently. Several de-anonymization attacks have been proposed to re-identify individuals even if data anonymization techniques were applied. However, there is no theoretical quantification for relating the data utility that is preserved by the anonymization techniques and the data vulnerability against de-anonymization attacks. In this paper, we theoretically analyze the de-anonymization attacks and provide conditions on the utility of the anonymized data (denoted by anonymized utility) to achieve successful de-anonymization. To the best of our knowledge, this is the first work on quantifying the relationships between anonymized utility and de-anonymization capability. Unlike previous work, our quantification analysis requires no assumptions about the graph model, thus providing a general theoretical guide for developing practical de-anonymization/anonymization techniques. Furthermore, we evaluate state-of-the-art de-anonymization attacks on a real-world Facebook dataset to show the limitations of previous work. By comparing these experimental results and the theoretically achievable de-anonymization capability derived in our analysis, we further demonstrate the ineffectiveness of previous de-anonymization attacks and the potential of more powerful de-anonymization attacks in the future.
Superposition as memory: unlocking quantum automatic complexity
Venue: arXiv cs.CR 2017
Year: 2017

Imagine a lock with two states, "locked" and "unlocked", which may be manipulated using two operations, called 0 and 1. Moreover, the only way to (with certainty) unlock using four operations is to do them in the sequence 0011, i.e., $0^n1^n$ where $n=2$. In this scenario one might think that the lock needs to be in certain further states after each operation, so that there is some memory of what has been done so far. Here we show that this memory can be entirely encoded in superpositions of the two basic states "locked" and "unlocked", where, as dictated by quantum mechanics, the operations are given by unitary matrices. Moreover, we show using the Jordan--Schur lemma that a similar lock is not possible for $n=60$. We define the semi-classical quantum automatic complexity $Q_{s}(x)$ of a word $x$ as the infimum in lexicographic order of those pairs of nonnegative integers $(n,q)$ such that there is a subgroup $G$ of the projective unitary group PU$(n)$ with $|G|\le q$ and with $U_0,U_1\in G$ such that, in terms of a standard basis $\{e_k\}$ and with $U_z=\prod_k U_{z(k)}$, we have $U_x e_1=e_2$ and $U_y e_1 \ne e_2$ for all $y\ne x$ with $|y|=|x|$. We show that $Q_s$ is unbounded and not constant for strings of a given length. In particular, \[ Q_{s}(0^21^2)\le (2,12) < (3,1) \le Q_{s}(0^{60}1^{60}) \] and $Q_s(0^{120})\le (2,121)$.
On the Analysis of the DeGroot-Friedkin Model with Dynamic Relative Interaction Matrices
Venue: arXiv cs.SI 2017
Year: 2017

This paper analyses the DeGroot-Friedkin model for evolution of the individuals' social powers in a social network when the network topology varies dynamically (described by dynamic relative interaction matrices). The DeGroot-Friedkin model describes how individual social power (self-appraisal, self-weight) evolves as a network of individuals discuss a sequence of issues. We seek to study dynamically changing relative interactions because interactions may change depending on the issue being discussed. In order to explore the problem in detail, two different cases of issue-dependent network topologies are studied. First, if the topology varies between issues in a periodic manner, it is shown that the individuals' self-appraisals admit a periodic solution. Second, if the topology changes arbitrarily, under the assumption that each relative interaction matrix is doubly stochastic and irreducible, the individuals' self-appraisals asymptotically converge to a unique non-trivial equilibrium.
Optimal Localization of Diffusion Sources in Complex Networks
Venue: arXiv cs.SI 2017
Year: 2017

Locating sources of diffusion and spreading from minimum data is a significant problem in network science with great applied values to the society. However, a general theoretical framework dealing with optimal source localization is lacking. Combining the controllability theory for complex networks and compressive sensing, we develop a framework with high efficiency and robustness for optimal source localization in arbitrary weighted networks with arbitrary distribution of sources. We offer a minimum output analysis to quantify the source locatability through a minimal number of messenger nodes that produce sufficient measurement for fully locating the sources. When the minimum messenger nodes are discerned, the problem of optimal source localization becomes one of sparse signal reconstruction, which can be solved using compressive sensing. Application of our framework to model and empirical networks demonstrates that sources in homogeneous and denser networks are more readily to be located. A surprising finding is that, for a connected undirected network with random link weights and weak noise, a single messenger node is sufficient for locating any number of sources. The framework deepens our understanding of the network source localization problem and offers efficient tools with broad applications.
Label Stability in Multiple Instance Learning
Venue: arXiv cs.CV 2017
Year: 2017

We address the problem of \emph{instance label stability} in multiple instance learning (MIL) classifiers. These classifiers are trained only on globally annotated images (bags), but often can provide fine-grained annotations for image pixels or patches (instances). This is interesting for computer aided diagnosis (CAD) and other medical image analysis tasks for which only a coarse labeling is provided. Unfortunately, the instance labels may be unstable. This means that a slight change in training data could potentially lead to abnormalities being detected in different parts of the image, which is undesirable from a CAD point of view. Despite MIL gaining popularity in the CAD literature, this issue has not yet been addressed. We investigate the stability of instance labels provided by several MIL classifiers on 5 different datasets, of which 3 are medical image datasets (breast histopathology, diabetic retinopathy and computed tomography lung images). We propose an unsupervised measure to evaluate instance stability, and demonstrate that a performance-stability trade-off can be made when comparing MIL classifiers.
Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
Venue: arXiv cs.CC 2017
Year: 2017

We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The "memoryless" term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. % As an application of communication complexity results, we consider Quantum Ordered Read-$k$-times Branching Programs ($k$-QOBDD). Our communication complexity result allows us to get lower bound for $k$-QOBDD and to prove hierarchies for sublinear width bounded error $k$-QOBDDs, where $k=o(\sqrt{n})$. Furthermore, we prove a hierarchy for polynomial size bounded error $k$-QOBDDs for constant $k$. This result differs from the situation with an unbounded error where it is known that an increase of $k$ does not give any advantage.
Finding a Feasible Initial Solution for Flatness-Based Multi-Link Manipulator Motion Planning under State and Control Constraints
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we present a method to initialize at a feasible point and unfailingly solve a non-convex optimization problem in which a set-point motion is planned for a multi-link manipulator under state and control constraints. We construct an initial feasible solution by analyzing the final time effect for feasibility problems of flatness based motion planning problems. More specifically, we first find a feasible time-optimal trajectory under state constraints without a control constraint by solving a linear programming problem. Then, we find a feasible trajectory under control constraints by scaling the trajectory. To evaluate the practical applicability of the proposed method, we did numerical experiments to solve a multi-link manipulator motion planning problem by combining the method with recursive inverse dynamics algorithms.
Auxiliary Variables in TLA+
Venue: arXiv cs.LO 2017
Year: 2017

Auxiliary variables are often needed for verifying that an implementation is correct with respect to a higher-level specification. They augment the formal description of the implementation without changing its semantics--that is, the set of behaviors that it describes. This paper explains rules for adding history, prophecy, and stuttering variables to TLA+ specifications, ensuring that the augmented specification is equivalent to the original one. The rules are explained with toy examples, and they are used to verify the correctness of a simplified version of a snapshot algorithm due to Afek et al.
Is this word borrowed? An automatic approach to quantify the likeliness of borrowing in social media
Venue: arXiv cs.CL 2017
Year: 2017

Code-mixing or code-switching are the effortless phenomena of natural switching between two or more languages in a single conversation. Use of a foreign word in a language; however, does not necessarily mean that the speaker is code-switching because often languages borrow lexical items from other languages. If a word is borrowed, it becomes a part of the lexicon of a language; whereas, during code-switching, the speaker is aware that the conversation involves foreign words or phrases. Identifying whether a foreign word used by a bilingual speaker is due to borrowing or code-switching is a fundamental importance to theories of multilingualism, and an essential prerequisite towards the development of language and speech technologies for multilingual communities. In this paper, we present a series of novel computational methods to identify the borrowed likeliness of a word, based on the social media signals. We first propose context based clustering method to sample a set of candidate words from the social media data.Next, we propose three novel and similar metrics based on the usage of these words by the users in different tweets; these metrics were used to score and rank the candidate words indicating their borrowed likeliness. We compare these rankings with a ground truth ranking constructed through a human judgment experiment. The Spearman's rank correlation between the two rankings (nearly 0.62 for all the three metric variants) is more than double the value (0.26) of the most competitive existing baseline reported in the literature. Some other striking observations are, (i) the correlation is higher for the ground truth data elicited from the younger participants (age less than 30) than that from the older participants, and (ii )those participants who use mixed-language for tweeting the least, provide the best signals of borrowing.