OpenRaiser/Intern-Atlas huggingface dataset:
Bounded Cycle Synthesis
Venue: arXiv cs.LO 2016
Year: 2016

We introduce a new approach for the synthesis of Mealy machines from specifications in linear-time temporal logic (LTL), where the number of cycles in the state graph of the implementation is limited by a given bound. Bounding the number of cycles leads to implementations that are structurally simpler and easier to understand. We solve the synthesis problem via an extension of SAT-based bounded synthesis, where we additionally construct a witness structure that limits the number of cycles. We also establish a triple-exponential upper and lower bound for the potential blow-up between the length of the LTL formula and the number of cycles in the state graph.
Fitness-based Adaptive Control of Parameters in Genetic Programming: Adaptive Value Setting of Mutation Rate and Flood Mechanisms
Venue: arXiv cs.NE 2016
Year: 2016

This paper concerns applications of genetic algorithms and genetic programming to tasks for which it is difficult to find a representation that does not map to a highly complex and discontinuous fitness landscape. In such cases the standard algorithm is prone to getting trapped in local extremes. The paper proposes several adaptive mechanisms that are useful in preventing the search from getting trapped.
Classification of Human Whole-Body Motion using Hidden Markov Models
Venue: arXiv cs.LG 2016
Year: 2016

Human motion plays an important role in many fields. Large databases exist that store and make available recordings of human motions. However, annotating each motion with multiple labels is a cumbersome and error-prone process. This bachelor's thesis presents different approaches to solve the multi-label classification problem using Hidden Markov Models (HMMs). First, different features that can be directly obtained from the raw data are introduced. Next, additional features are derived to improve classification performance. These features are then used to perform the multi-label classification using two different approaches. The first approach simply transforms the multi-label problem into a multi-class problem. The second, novel approach solves the same problem without the need to construct a transformation by predicting the labels directly from the likelihood scores. The second approach scales linearly with the number of labels whereas the first approach is subject to combinatorial explosion. All aspects of the classification process are evaluated on a data set that consists of 454 motions. System 1 achieves an accuracy of 98.02% and system 2 an accuracy of 93.39% on the test set.
Patch-based Texture Synthesis for Image Inpainting
Venue: arXiv cs.CV 2016
Year: 2016

Image inpaiting is an important task in image processing and vision. In this paper, we develop a general method for patch-based image inpainting by synthesizing new textures from existing one. A novel framework is introduced to find several optimal candidate patches and generate a new texture patch in the process. We form it as an optimization problem that identifies the potential patches for synthesis from an coarse-to-fine manner. We use the texture descriptor as a clue in searching for matching patches from the known region. To ensure the structure faithful to the original image, a geometric constraint metric is formally defined that is applied directly to the patch synthesis procedure. We extensively conducted our experiments on a wide range of testing images on various scenarios and contents by arbitrarily specifying the target the regions for inference followed by using existing evaluation metrics to verify its texture coherency and structural consistency. Our results demonstrate the high accuracy and desirable output that can be potentially used for numerous applications: object removal, background subtraction, and image retrieval.
Stance and Sentiment in Tweets
Venue: arXiv cs.CL 2016
Year: 2016

We can often detect from a person's utterances whether he/she is in favor of or against a given target entity -- their stance towards the target. However, a person may express the same stance towards a target by using negative or positive language. Here for the first time we present a dataset of tweet--target pairs annotated for both stance and sentiment. The targets may or may not be referred to in the tweets, and they may or may not be the target of opinion in the tweets. Partitions of this dataset were used as training and test sets in a SemEval-2016 shared task competition. We propose a simple stance detection system that outperforms submissions from all 19 teams that participated in the shared task. Additionally, access to both stance and sentiment annotations allows us to explore several research questions. We show that while knowing the sentiment expressed by a tweet is beneficial for stance classification, it alone is not sufficient. Finally, we use additional unlabeled data through distant supervision techniques and word embeddings to further improve stance classification.
A note on adjusting $R^2$ for using with cross-validation
Venue: arXiv cs.LG 2016
Year: 2016

We show how to adjust the coefficient of determination ($R^2$) when used for measuring predictive accuracy via leave-one-out cross-validation.
Privacy and Twitter in Qatar: Traditional Values in the Digital World
Venue: arXiv cs.SI 2016
Year: 2016

We explore the meaning of privacy from the perspective of Qatari nationals as it manifests in digital environments. Although privacy is an essential and widely respected value in many cultures, the way in which it is understood and enacted depends on context. It is especially vital to understand user behaviors regarding privacy in the digital sphere, where individuals increasingly publish personal information. Our mixed-methods analysis of 18K Twitter posts that mention privacy focuses on the face to face and digital contexts in which privacy is mentioned, and how those contexts lead to varied ideologies regarding privacy. We find that in the Arab Gulf, the need for privacy is often supported by Quranic text, advice on how to protect privacy is frequently discussed, and the use of paternalistic language by men when discussing women related privacy is common. Above all, privacy is framed as a communal attribute, including not only the individual, but the behavior of those around them; it even extends beyond the individual lifespan. We contribute an analysis and description of these previously unexplored interpretations of privacy, which play a role in how users navigate social media.
Improving Automated Patent Claim Parsing: Dataset, System, and Experiments
Venue: arXiv cs.CL 2016
Year: 2016

Off-the-shelf natural language processing software performs poorly when parsing patent claims owing to their use of irregular language relative to the corpora built from news articles and the web typically utilized to train this software. Stopping short of the extensive and expensive process of accumulating a large enough dataset to completely retrain parsers for patent claims, a method of adapting existing natural language processing software towards patent claims via forced part of speech tag correction is proposed. An Amazon Mechanical Turk collection campaign organized to generate a public corpus to train such an improved claim parsing system is discussed, identifying lessons learned during the campaign that can be of use in future NLP dataset collection campaigns with AMT. Experiments utilizing this corpus and other patent claim sets measure the parsing performance improvement garnered via the claim parsing system. Finally, the utility of the improved claim parsing system within other patent processing applications is demonstrated via experiments showing improved automated patent subject classification when the new claim parsing system is utilized to generate the features.
Access Control Synthesis for Physical Spaces
Venue: arXiv cs.CR 2016
Year: 2016

Access-control requirements for physical spaces, like office buildings and airports, are best formulated from a global viewpoint in terms of system-wide requirements. For example, "there is an authorized path to exit the building from every room." In contrast, individual access-control components, such as doors and turnstiles, can only enforce local policies, specifying when the component may open. In practice, the gap between the system-wide, global requirements and the many local policies is bridged manually, which is tedious, error-prone, and scales poorly. We propose a framework to automatically synthesize local access control policies from a set of global requirements for physical spaces. Our framework consists of an expressive language to specify both global requirements and physical spaces, and an algorithm for synthesizing local, attribute-based policies from the global specification. We empirically demonstrate the framework's effectiveness on three substantial case studies. The studies demonstrate that access control synthesis is practical even for complex physical spaces, such as airports, with many interrelated security requirements.
Robust SAR STAP via Kronecker Decomposition
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a spatio-temporal decomposition for the detection of moving targets in multiantenna SAR. As a high resolution radar imaging modality, SAR detects and localizes non-moving targets accurately, giving it an advantage over lower resolution GMTI radars. Moving target detection is more challenging due to target smearing and masking by clutter. Space-time adaptive processing (STAP) is often used to remove the stationary clutter and enhance the moving targets. In this work, it is shown that the performance of STAP can be improved by modeling the clutter covariance as a space vs. time Kronecker product with low rank factors. Based on this model, a low-rank Kronecker product covariance estimation algorithm is proposed, and a novel separable clutter cancelation filter based on the Kronecker covariance estimate is introduced. The proposed method provides orders of magnitude reduction in the required number of training samples, as well as improved robustness to corruption of the training data. Simulation results and experiments using the Gotcha SAR GMTI challenge dataset are presented that confirm the advantages of our approach relative to existing techniques.
Schützenberger Products in a Category
Venue: arXiv cs.FL 2016
Year: 2016

The Schützenberger product of monoids is a key tool for the algebraic treatment of language concatenation. In this paper we generalize the Schützenberger product to the level of monoids in an algebraic category $\mathscr{D}$, leading to a uniform view of the corresponding constructions for monoids (Schützenberger), ordered monoids (Pin), idempotent semirings (Klíma and Polák) and algebras over a field (Reutenauer). In addition, assuming that $\mathscr{D}$ is part of a Stone-type duality, we derive a characterization of the languages recognized by Schützenberger products.
Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles
Venue: arXiv cs.GR 2016
Year: 2016

Given a simple graph $G=(V,E)$, a subset of $E$ is called a triangle cover if it intersects each triangle of $G$. Let $ν_t(G)$ and $τ_t(G)$ denote the maximum number of pairwise edge-disjoint triangles in $G$ and the minimum cardinality of a triangle cover of $G$, respectively. Tuza conjectured in 1981 that $τ_t(G)/ν_t(G)\le2$ holds for every graph $G$. In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding small triangle covers. These algorithms imply new sufficient conditions for Tuza's conjecture on covering and packing triangles. More precisely, suppose that the set $\mathscr T_G$ of triangles covers all edges in $G$. We show that a triangle cover of $G$ with cardinality at most $2ν_t(G)$ can be found in polynomial time if one of the following conditions is satisfied: (i) $ν_t(G)/|\mathscr T_G|\ge\frac13$, (ii) $ν_t(G)/|E|\ge\frac14$, (iii) $|E|/|\mathscr T_G|\ge2$. Keywords: Triangle cover, Triangle packing, Linear 3-uniform hypergraphs, Combinatorial algorithms
Downlink Transmission of Short Packets: Framing and Control Information Revisited
Venue: arXiv cs.IT 2016
Year: 2016

Cellular wireless systems rely on frame-based transmissions. The frame design is conventionally based on heuristics, consisting of a frame header and a data part. The frame header contains control information that provides pointers to the messages within the data part. In this paper, we revisit the principles of frame design and show the impact of the new design in scenarios that feature short data packets which are central to various 5G and Internet of Things applications. We treat framing for downlink transmission in an AWGN broadcast channel with K users, where the sizes of the messages to the users are random variables. Using approximations from finite blocklength information theory, we establish a framework in which a message to a given user is not necessarily encoded as a single packet, but may be grouped with the messages to other users and benefit from the improved efficiency of longer codes. This requires changes in the way control information is sent, and it requires that the users need to spend power decoding other messages, thereby increasing the average power consumption. We show that the common heuristic design is only one point on a curve that represents the trade-off between latency and power consumption.
Detecting Context Dependence in Exercise Item Candidates Selected from Corpora
Venue: arXiv cs.CL 2016
Year: 2016

We explore the factors influencing the dependence of single sentences on their larger textual context in order to automatically identify candidate sentences for language learning exercises from corpora which are presentable in isolation. An in-depth investigation of this question has not been previously carried out. Understanding this aspect can contribute to a more efficient selection of candidate sentences which, besides reducing the time required for item writing, can also ensure a higher degree of variability and authenticity. We present a set of relevant aspects collected based on the qualitative analysis of a smaller set of context-dependent corpus example sentences. Furthermore, we implemented a rule-based algorithm using these criteria which achieved an average precision of 0.76 for the identification of different issues related to context dependence. The method has also been evaluated empirically where 80% of the sentences in which our system did not detect context-dependent elements were also considered context-independent by human raters.
A computational intuition pump to examine group creativity: building on the ideas of others
Venue: arXiv cs.MA 2016
Year: 2016

This paper presents a computational approach to modelling group creativity. It presents an analysis of two studies of group creativity selected from different research cultures and identifies a common theme ("idea build-up") that is then used in the formalisation of an agent-based model used to support reasoning about the complex dynamics of building on the ideas of others.
Privacy-Constrained Remote Source Coding
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of revealing/sharing data in an efficient and secure way via a compact representation. The representation should ensure reliable reconstruction of the desired features/attributes while still preserve privacy of the secret parts of the data. The problem is formulated as a remote lossy source coding with a privacy constraint where the remote source consists of public and secret parts. Inner and outer bounds for the optimal tradeoff region of compression rate, distortion, and privacy leakage rate are given and shown to coincide for some special cases. When specializing the distortion measure to a logarithmic loss function, the resulting rate-distortion-leakage tradeoff for the case of identical side information forms an optimization problem which corresponds to the "secure" version of the so-called information bottleneck.
SDNsec: Forwarding Accountability for the SDN Data Plane
Venue: arXiv cs.NI 2016
Year: 2016

SDN promises to make networks more flexible, programmable, and easier to manage. Inherent security problems in SDN today, however, pose a threat to the promised benefits. First, the network operator lacks tools to proactively ensure that policies will be followed or to reactively inspect the behavior of the network. Second, the distributed nature of state updates at the data plane leads to inconsistent network behavior during reconfigurations. Third, the large flow space makes the data plane susceptible to state exhaustion attacks. This paper presents SDNsec, an SDN security extension that provides forwarding accountability for the SDN data plane. Forwarding rules are encoded in the packet, ensuring consistent network behavior during reconfigurations and limiting state exhaustion attacks due to table lookups. Symmetric-key cryptography is used to protect the integrity of the forwarding rules and enforce them at each switch. A complementary path validation mechanism allows the controller to reactively examine the actual path taken by the packets. Furthermore, we present mechanisms for secure link-failure recovery and multicast/broadcast forwarding.
Transformation of Communication Processes: Data Journalism
Venue: arXiv cs.CY 2016
Year: 2016

This article gives a brief review of the history of data journalism, as well as the prerequisites for its appearance. The authors describe the advantages of employing data-journalism skills in the newsrooms. Finally, the article provides a review of data-driven journalism projects all over the world, state of art 2014.
TCPTuner: Congestion Control Your Way
Venue: arXiv cs.NI 2016
Year: 2016

TCPTuner is a TCP (transmission control protocol) congestion control kernel module and GUI (graphical user interface) for Linux that allows real-time modification of the congestion control parameters of TCP CUBIC, the current default algorithm in Linux. Specifically, the tool provides access to alpha, the rate at which a sender's congestion window grows; beta, the multiplicative factor to decrease the congestion window on a loss event; as well as CUBIC's fast convergence and tcp friendliness parameters. Additionally, the interface provides access to ip-route parameters for the minimum retransmission time and initial congestion window size. In this paper, we describe the implementation of TCPTuner and show experimental data of the effects of adjusting congestion control parameters.
Beyond knowing that: a new generation of epistemic logics
Venue: arXiv cs.AI 2016
Year: 2016

Epistemic logic has become a major field of philosophical logic ever since the groundbreaking work by Hintikka (1962). Despite its various successful applications in theoretical computer science, AI, and game theory, the technical development of the field has been mainly focusing on the propositional part, i.e., the propositional modal logics of "knowing that". However, knowledge is expressed in everyday life by using various other locutions such as "knowing whether", "knowing what", "knowing how" and so on (knowing-wh hereafter). Such knowledge expressions are better captured in quantified epistemic logic, as was already discussed by Hintikka (1962) and his sequel works at length. This paper aims to draw the attention back again to such a fascinating but largely neglected topic. We first survey what Hintikka and others did in the literature of quantified epistemic logic, and then advocate a new quantifier-free approach to study the epistemic logics of knowing-wh, which we believe can balance expressivity and complexity, and capture the essential reasoning patterns about knowing-wh. We survey our recent line of work on the epistemic logics of "knowing whether", "knowing what" and "knowing how" to demonstrate the use of this new approach.
Software Assumptions Failure Tolerance: Role, Strategies, and Visions
Venue: arXiv cs.SE 2016
Year: 2016

At our behest or otherwise, while our software is being executed, a huge variety of design assumptions is continuously matched with the truth of the current condition. While standards and tools exist to express and verify some of these assumptions, in practice most of them end up being either sifted off or hidden between the lines of our codes. Across the system layers, a complex and at times obscure web of assumptions determines the quality of the match of our software with its deployment platforms and run-time environments. Our position is that it becomes increasingly important being able to design software systems with architectural and structuring techniques that allow software to be decomposed to reduce its complexity, but without hiding in the process vital hypotheses and assumptions. In this paper we discuss this problem, introduce three potentially dangerous consequences of its denial, and propose three strategies to facilitate their treatment. Finally we propose our vision towards a new holistic approach to software development to overcome the shortcomings offered by fragmented views to the problem of assumption failures.
Mapping knowledge translation and innovation processes in Cancer Drug Development: the case of liposomal doxorubicin
Venue: arXiv cs.DL 2016
Year: 2016

We explored how the knowledge translation and innovation processes are structured when they result in innovations, as in the case of liposomal doxorubicin research. In order to map the processes, a literature network analysis was made through Cytoscape and semantic analysis was performed by GOPubmed which is based in the controlled vocabularies MeSH (Medical Subject Headings) and GO (Gene Ontology). We found clusters related to different stages of the technological development (invention, innovation and imitation) and the knowledge translation process (preclinical, translational and clinical research), and we were able to map the historic emergence of Doxil as a paradigmatic nanodrug. This research could be a powerful methodological tool for decision-making and innovation management in drug delivery research.
Fast Compatibility Testing for Phylogenies with Nested Taxa
Venue: arXiv cs.DS 2016
Year: 2016

Semi-labeled trees are phylogenies whose internal nodes may be labeled by higher-order taxa. Thus, a leaf labeled Mus musculus could nest within a subtree whose root node is labeled Rodentia, which itself could nest within a subtree whose root is labeled Mammalia. Suppose we are given collection $\mathcal P$ of semi-labeled trees over various subsets of a set of taxa. The ancestral compatibility problem asks whether there is a semi-labeled tree $\mathcal T$ that respects the clusterings and the ancestor/descendant relationships implied by the trees in $\mathcal P$. We give a $\tilde{O}(M_{\mathcal{P}})$ algorithm for the ancestral compatibility problem, where $M_{\mathcal{P}}$ is the total number of nodes and edges in the trees in $\mathcal P$. Unlike the best previous algorithm, the running time of our method does not depend on the degrees of the nodes in the input trees.