OpenRaiser/Intern-Atlas huggingface dataset:
The Role of Pragmatics in Legal Norm Representation
Venue: arXiv cs.CL 2015
Year: 2015

Despite the 'apparent clarity' of a given legal provision, its application may result in an outcome that does not exactly conform to the semantic level of a statute. The vagueness within a legal text is induced intentionally to accommodate all possible scenarios under which such norms should be applied, thus making the role of pragmatics an important aspect also in the representation of a legal norm and reasoning on top of it. The notion of pragmatics considered in this paper does not focus on the aspects associated with judicial decision making. The paper aims to shed light on the aspects of pragmatics in legal linguistics, mainly focusing on the domain of patent law, only from a knowledge representation perspective. The philosophical discussions presented in this paper are grounded based on the legal theories from Grice and Marmor.
Learning to Mine Chinese Coordinate Terms Using the Web
Venue: arXiv cs.CL 2015
Year: 2015

Coordinate relation refers to the relation between instances of a concept and the relation between the directly hyponyms of a concept. In this paper, we focus on the task of extracting terms which are coordinate with a user given seed term in Chinese, and grouping the terms which belong to different concepts if the seed term has several meanings. We propose a semi-supervised method that integrates manually defined linguistic patterns and automatically learned semi-structural patterns to extract coordinate terms in Chinese from web search results. In addition, terms are grouped into different concepts based on their co-occurring terms and contexts. We further calculate the saliency scores of extracted terms and rank them accordingly. Experimental results demonstrate that our proposed method generates results with high quality and wide coverage.
Towards Good Practices for Very Deep Two-Stream ConvNets
Venue: arXiv cs.CV 2015
Year: 2015

Deep convolutional networks have achieved great success for object recognition in still images. However, for action recognition in videos, the improvement of deep convolutional networks is not so evident. We argue that there are two reasons that could probably explain this result. First the current network architectures (e.g. Two-stream ConvNets) are relatively shallow compared with those very deep models in image domain (e.g. VGGNet, GoogLeNet), and therefore their modeling capacity is constrained by their depth. Second, probably more importantly, the training dataset of action recognition is extremely small compared with the ImageNet dataset, and thus it will be easy to over-fit on the training dataset. To address these issues, this report presents very deep two-stream ConvNets for action recognition, by adapting recent very deep architectures into video domain. However, this extension is not easy as the size of action recognition is quite small. We design several good practices for the training of very deep two-stream ConvNets, namely (i) pre-training for both spatial and temporal nets, (ii) smaller learning rates, (iii) more data augmentation techniques, (iv) high drop out ratio. Meanwhile, we extend the Caffe toolbox into Multi-GPU implementation with high computational efficiency and low memory consumption. We verify the performance of very deep two-stream ConvNets on the dataset of UCF101 and it achieves the recognition accuracy of $91.4\%$.
Independence and Efficient Domination on $P_6$-free Graphs
Venue: arXiv cs.DS 2015
Year: 2015

In the Independent set problem, the input is a graph $G$, every vertex has a non-negative integer weight, and the task is to find a set $S$ of pairwise non-adjacent vertices, maximizing the total weight of the vertices in $S$. We give an $n^{O (\log^2 n)}$ time algorithm for this problem on graphs excluding the path $P_6$ on $6$ vertices as an induced subgraph. Currently, there is no constant $k$ known for which Independent Set on $P_{k}$-free graphs becomes NP-complete, and our result implies that if such a $k$ exists, then $k > 6$ unless all problems in NP can be decided in (quasi)polynomial time. Using the combinatorial tools that we develop for the above algorithm, we also give a polynomial-time algorithm for Efficient Dominating Set on $P_6$-free graphs. In this problem, the input is a graph $G$, every vertex has an integer weight, and the objective is to find a set $S$ of maximum weight such that every vertex in $G$ has exactly one vertex in $S$ in its closed neighborhood, or to determine that no such set exists. Prior to our work, the class of $P_6$-free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of Efficient Dominating Set was unknown.
A New Understanding of Friendships in Space: Complex Networks Meet Twitter
Venue: arXiv cs.SI 2015
Year: 2015

Studies on friendships in online social networks involving geographic distance have so far relied on the city location provided in users' profiles. Consequently, most of the research on friendships have provided accuracy at the city level, at best, to designate a user's location. This study analyzes a Twitter dataset because it provides the exact geographic distance between corresponding users. We start by introducing a strong definition of "friend" on Twitter (i.e., a definition of bidirectional friendship), requiring bidirectional communication. Next, we utilize geo-tagged mentions delivered by users to determine their locations, where "@username" is contained anywhere in the body of tweets. To provide analysis results, we first introduce a friend counting algorithm. From the fact that Twitter users are likely to post consecutive tweets in the static mode, we also introduce a two-stage distance estimation algorithm. As the first of our main contributions, we verify that the number of friends of a particular Twitter user follows a well-known power-law distribution (i.e., a Zipf's distribution or a Pareto distribution). Our study also provides the following newly-discovered friendship degree related to the issue of space: The number of friends according to distance follows a double power-law (i.e., a double Pareto law) distribution, indicating that the probability of befriending a particular Twitter user is significantly reduced beyond a certain geographic distance between users, termed the separation point. Our analysis provides concrete evidence that Twitter can be a useful platform for assigning a more accurate scalar value to the degree of friendship between two users.
Equivalence Checking and Simulation By Computing Range Reduction
Venue: arXiv cs.LO 2015
Year: 2015

We introduce new methods of equivalence checking and simulation based on Computing Range Reduction (CRR). Given a combinational circuit $N$, the CRR problem is to compute the set of outputs that disappear from the range of $N$ if a set of inputs of $N$ is excluded from consideration. Importantly, in many cases, range reduction can be efficiently found even if computing the entire range of $N$ is infeasible. Solving equivalence checking by CRR facilitates generation of proofs of equivalence that mimic a "cut propagation" approach. A limited version of such an approach has been successfully used by commercial tools. Functional verification of a circuit $N$ by simulation can be viewed as a way to reduce the complexity of computing the range of $N$. Instead of finding the entire range of $N$ and checking if it contains a bad output, such a range is computed only for one input. Simulation by CRR offers an alternative way of coping with the complexity of range computation. The idea is to exclude a subset of inputs of $N$ and compute the range reduction caused by such an exclusion. If the set of disappeared outputs contains a bad one, then $N$ is buggy.
Multisection in the Stochastic Block Model using Semidefinite Programming
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of identifying underlying community-like structures in graphs. Towards this end we study the Stochastic Block Model (SBM) on $k$-clusters: a random model on $n=km$ vertices, partitioned in $k$ equal sized clusters, with edges sampled independently across clusters with probability $q$ and within clusters with probability $p$, $p>q$. The goal is to recover the initial "hidden" partition of $[n]$. We study semidefinite programming (SDP) based algorithms in this context. In the regime $p = \frac{α\log(m)}{m}$ and $q = \frac{β\log(m)}{m}$ we show that a certain natural SDP based algorithm solves the problem of {\em exact recovery} in the $k$-community SBM, with high probability, whenever $\sqrtα - \sqrtβ > \sqrt{1}$, as long as $k=o(\log n)$. This threshold is known to be the information theoretically optimal. We also study the case when $k=θ(\log(n))$. In this case however we achieve recovery guarantees that no longer match the optimal condition $\sqrtα - \sqrtβ > \sqrt{1}$, thus leaving achieving optimality for this range an open question.
Understanding Intra-Class Knowledge Inside CNN
Venue: arXiv cs.CV 2015
Year: 2015

Convolutional Neural Network (CNN) has been successful in image recognition tasks, and recent works shed lights on how CNN separates different classes with the learned inter-class knowledge through visualization. In this work, we instead visualize the intra-class knowledge inside CNN to better understand how an object class is represented in the fully-connected layers. To invert the intra-class knowledge into more interpretable images, we propose a non-parametric patch prior upon previous CNN visualization models. With it, we show how different "styles" of templates for an object class are organized by CNN in terms of location and content, and represented in a hierarchical and ensemble way. Moreover, such intra-class knowledge can be used in many interesting applications, e.g. style-based image retrieval and style-based object completion.
Quantum Inspired Training for Boltzmann Machines
Venue: arXiv cs.LG 2015
Year: 2015

We present an efficient classical algorithm for training deep Boltzmann machines (DBMs) that uses rejection sampling in concert with variational approximations to estimate the gradients of the training objective function. Our algorithm is inspired by a recent quantum algorithm for training DBMs. We obtain rigorous bounds on the errors in the approximate gradients; in turn, we find that choosing the instrumental distribution to minimize the alpha=2 divergence with the Gibbs state minimizes the asymptotic algorithmic complexity. Our rejection sampling approach can yield more accurate gradients than low-order contrastive divergence training and the costs incurred in finding increasingly accurate gradients can be easily parallelized. Finally our algorithm can train full Boltzmann machines and scales more favorably with the number of layers in a DBM than greedy contrastive divergence training.
Robust Performance-driven 3D Face Tracking in Long Range Depth Scenes
Venue: arXiv cs.CV 2015
Year: 2015

We introduce a novel robust hybrid 3D face tracking framework from RGBD video streams, which is capable of tracking head pose and facial actions without pre-calibration or intervention from a user. In particular, we emphasize on improving the tracking performance in instances where the tracked subject is at a large distance from the cameras, and the quality of point cloud deteriorates severely. This is accomplished by the combination of a flexible 3D shape regressor and the joint 2D+3D optimization on shape parameters. Our approach fits facial blendshapes to the point cloud of the human head, while being driven by an efficient and rapid 3D shape regressor trained on generic RGB datasets. As an on-line tracking system, the identity of the unknown user is adapted on-the-fly resulting in improved 3D model reconstruction and consequently better tracking performance. The result is a robust RGBD face tracker, capable of handling a wide range of target scene depths, beyond those that can be afforded by traditional depth or RGB face trackers. Lastly, since the blendshape is not able to accurately recover the real facial shape, we use the tracked 3D face model as a prior in a novel filtering process to further refine the depth map for use in other tasks, such as 3D reconstruction.
Locally Repairable Codes with Functional Repair and Multiple Erasure Tolerance
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of designing [n; k] linear codes for distributed storage systems (DSS) that satisfy the (r, t)-Local Repair Property, where any t'(<=t) simultaneously failed nodes can be locally repaired, each with locality r. The parameters n, k, r, t are positive integers such that r<k<n and t <= n-k. We consider the functional repair model and the sequential approach for repairing multiple failed nodes. By functional repair, we mean that the packet stored in each newcomer is not necessarily an exact copy of the lost data but a symbol that keep the (r, t)-local repair property. By the sequential approach, we mean that the t' newcomers are ordered in a proper sequence such that each newcomer can be repaired from the live nodes and the newcomers that are ordered before it. Such codes, which we refer to as (n, k, r, t)-functional locally repairable codes (FLRC), are the most general class of LRCs and contain several subclasses of LRCs reported in the literature. In this paper, we aim to optimize the storage overhead (equivalently, the code rate) of FLRCs. We derive a lower bound on the code length n given t belongs to {2,3} and any possible k, r. For t=2, our bound generalizes the rate bound proved in [14]. For t=3, our bound improves the rate bound proved in [10]. We also give some onstructions of exact LRCs for t belongs to {2,3} whose length n achieves the bound of (n, k, r, t)-FLRC, which proves the tightness of our bounds and also implies that there is no gap between the optimal code length of functional LRCs and exact LRCs for certain sets of parameters. Moreover, our constructions are over the binary field, hence are of interest in practice.
Logic and Branching Automata
Venue: arXiv cs.FL 2015
Year: 2015

In this paper we study the logical aspects of branching automata, as defined by Lodaya and Weil. We first prove that the class of languages of finite N-free posets recognized by branching automata is closed under complementation. Then we define a logic, named P-MSO as it is a extension of monadic second-order logic with Presburger arithmetic, and show that it is precisely as expressive as branching automata. As a consequence of the effectiveness of the construction of one formalism from the other, the P-MSO theory of the class of all finite N-free posets is decidable.
Secure Scrum: Development of Secure Software with Scrum
Venue: arXiv cs.CR 2015
Year: 2015

Nowadays, the use of agile software development methods like Scrum is common in industry and academia. Considering the current attacking landscape, it is clear that developing secure software should be a main concern in all software development projects. In traditional software projects, security issues require detailed planning in an initial planning phase, typically resulting in a detailed security analysis (e.g., threat and risk analysis), a security architecture, and instructions for security implementation (e.g., specification of key sizes and cryptographic algorithms to use). Agile software development methods like Scrum are known for reducing the initial planning phases (e.g., sprint 0 in Scrum) and for focusing more on producing running code. Scrum is also known for allowing fast adaption of the emerging software to changes of customer wishes. For security, this means that it is likely that there are no detailed security architecture or security implementation instructions from the start of the project. It also means that a lot of design decisions will be made during the runtime of the project. Hence, to address security in Scrum, it is necessary to consider security issues throughout the whole software development process. Secure Scrum is a variation of the Scrum framework with special focus on the development of secure software throughout the whole software development process. It puts emphasis on implementation of security related issues without the need of changing the underlying Scrum process or influencing team dynamics. Secure Scrum allows even non- security experts to spot security issues, to implement security features, and to verify implementations. A field test of Secure Scrum shows that the security level of software developed using Secure Scrum is higher then the security level of software developed using standard Scrum.
A $1.75$ LP approximation for the Tree Augmentation Problem
Venue: arXiv cs.DS 2015
Year: 2015

In the Tree Augmentation Problem (TAP) the goal is to augment a tree $T$ by a minimum size edge set $F$ from a given edge set $E$ such that $T \cup F$ is $2$-edge-connected. The best approximation ratio known for TAP is $1.5$. In the more general Weighted TAP problem, $F$ should be of minimum weight. Weighted TAP admits several $2$-approximation algorithms w.r.t. to the standard cut LP-relaxation, but for all of them the performance ratio of $2$ is tight even for TAP. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than $2$ is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than $2$, which is a long time open problem even for TAP. In this paper we introduce such an LP-relaxation and give an algorithm that computes a feasible solution for TAP of size at most $1.75$ times the optimal LP value. This gives some hope to break the ratio $2$ for the weighted case. Our algorithm computes some initial edge set by solving a partial system of constraints that form the integral edge-cover polytope, and then applies local search on $3$-leaf subtrees to exchange some of the edges and to add additional edges. Thus we do not need to solve the LP, and the algorithm runs roughly in time required to find a minimum weight edge-cover in a general graph.
Classifier-Based Text Simplification for Improved Machine Translation
Venue: arXiv cs.CL 2015
Year: 2015

Machine Translation is one of the research fields of Computational Linguistics. The objective of many MT Researchers is to develop an MT System that produce good quality and high accuracy output translations and which also covers maximum language pairs. As internet and Globalization is increasing day by day, we need a way that improves the quality of translation. For this reason, we have developed a Classifier based Text Simplification Model for English-Hindi Machine Translation Systems. We have used support vector machines and Naïve Bayes Classifier to develop this model. We have also evaluated the performance of these classifiers.
Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we propose the amphibious influence maximization (AIM) model that combines traditional marketing via content providers and viral marketing to consumers in social networks in a single framework. In AIM, a set of content providers and consumers form a bipartite network while consumers also form their social network, and influence propagates from the content providers to consumers and among consumers in the social network following the independent cascade model. An advertiser needs to select a subset of seed content providers and a subset of seed consumers, such that the influence from the seed providers passing through the seed consumers could reach a large number of consumers in the social network in expectation. We prove that the AIM problem is NP-hard to approximate to within any constant factor via a reduction from Feige's k-prover proof system for 3-SAT5. We also give evidence that even when the social network graph is trivial (i.e. has no edges), a polynomial time constant factor approximation for AIM is unlikely. However, when we assume that the weighted bi-adjacency matrix that describes the influence of content providers on consumers is of constant rank, a common assumption often used in recommender systems, we provide a polynomial-time algorithm that achieves approximation ratio of $(1-1/e-ε)^3$ for any (polynomially small) $ε> 0$. Our algorithmic results still hold for a more general model where cascades in social network follow a general monotone and submodular function.
On Smooth 3D Frame Field Design
Venue: arXiv cs.GR 2015
Year: 2015

We analyze actual methods that generate smooth frame fields both in 2D and in 3D. We formalize the 2D problem by representing frames as functions (as it was done in 3D), and show that the derived optimization problem is the one that previous work obtain via "representation vectors." We show (in 2D) why this non linear optimization problem is easier to solve than directly minimizing the rotation angle of the field, and observe that the 2D algorithm is able to find good fields. Now, the 2D and the 3D optimization problems are derived from the same formulation (based on representing frames by functions). Their energies share some similarities from an optimization point of view (smoothness, local minima, bounds of partial derivatives, etc.), so we applied the 2D resolution mechanism to the 3D problem. Our evaluation of all existing 3D methods suggests to initialize the field by this new algorithm, but possibly use another method for further smoothing.
Sparsity assisted solution to the twin image problem in phase retrieval
Venue: arXiv cs.CV 2015
Year: 2015

The iterative phase retrieval problem for complex-valued objects from Fourier transform magnitude data is known to suffer from the twin image problem. In particular, when the object support is centro-symmetric, the iterative solution often stagnates such that the resultant complex image contains the features of both the desired solution and its inverted and complex-conjugated replica. The conventional approach to address the twin image problem is to modify the object support during initial iterations which can possibly lead to elimination of one of the twin images. However, at present there seems to be no deterministic procedure to make sure that the twin image will always be very weak or absent. In this work we make an important observation that the ideal solution without the twin image is typically more sparse (in some suitable transform domain) as compared to the stagnated solution containing the twin image. We further show that introducing a sparsity enhancing step in the iterative algorithm can address the twin image problem without the need to change the object support throughout the iterative process even when the object support is centro-symmetric. In a simulation study, we use binary and gray-scale pure phase objects and illustrate the effectiveness of the sparsity assisted phase recovery in the context of the twin image problem. The results have important implications for a wide range of topics in Physics where the phase retrieval problem plays a central role.