OpenRaiser/Intern-Atlas huggingface dataset:
Reducing the Computational Cost in Multi-objective Evolutionary Algorithms by Filtering Worthless Individuals
Venue: arXiv cs.NE 2014
Year: 2014

The large number of exact fitness function evaluations makes evolutionary algorithms to have computational cost. In some real-world problems, reducing number of these evaluations is much more valuable even by increasing computational complexity and spending more time. To fulfill this target, we introduce an effective factor, in spite of applied factor in Adaptive Fuzzy Fitness Granulation with Non-dominated Sorting Genetic Algorithm-II, to filter out worthless individuals more precisely. Our proposed approach is compared with respect to Adaptive Fuzzy Fitness Granulation with Non-dominated Sorting Genetic Algorithm-II, using the Hyper volume and the Inverted Generational Distance performance measures. The proposed method is applied to 1 traditional and 1 state-of-the-art benchmarks with considering 3 different dimensions. From an average performance view, the results indicate that although decreasing the number of fitness evaluations leads to have performance reduction but it is not tangible compared to what we gain.
GGP with Advanced Reasoning and Board Knowledge Discovery
Venue: arXiv cs.AI 2014
Year: 2014

Quality of General Game Playing (GGP) matches suffers from slow state-switching and weak knowledge modules. Instantiation and Propositional Networks offer great performance gains over Prolog-based reasoning, but do not scale well. In this publication mGDL, a variant of GDL stripped of function constants, has been defined as a basis for simple reasoning machines. mGDL allows to easily map rules to C++ functions. 253 out of 270 tested GDL rule sheets conformed to mGDL without any modifications; the rest required minor changes. A revised (m)GDL to C++ translation scheme has been reevaluated; it brought gains ranging from 28% to 7300% over YAP Prolog, managing to compile even demanding rule sheets under few seconds. For strengthening game knowledge, spatial features inspired by similar successful techniques from computer Go have been proposed. For they required an Euclidean metric, a small board extension to GDL has been defined through a set of ground atomic sentences. An SGA-based genetic algorithm has been designed for tweaking game parameters and conducting self-plays, so the features could be mined from meaningful game records. The approach has been tested on a small cluster, giving performance gains up to 20% more wins against the baseline UCT player. Implementations of proposed ideas constitutes the core of GGP Spatium - a small C++/Python GGP framework, created for developing compact GGP Players and problem solvers.
Algorithms for Generating Ordered Solutions for Explicit AND/OR Structures
Venue: arXiv cs.AI 2014
Year: 2014

We present algorithms for generating alternative solutions for explicit acyclic AND/OR structures in non-decreasing order of cost. The proposed algorithms use a best first search technique and report the solutions using an implicit representation ordered by cost. In this paper, we present two versions of the search algorithm -- (a) an initial version of the best first search algorithm, ASG, which may present one solution more than once while generating the ordered solutions, and (b) another version, LASG, which avoids the construction of the duplicate solutions. The actual solutions can be reconstructed quickly from the implicit compact representation used. We have applied the methods on a few test domains, some of them are synthetic while the others are based on well known problems including the search space of the 5-peg Tower of Hanoi problem, the matrix-chain multiplication problem and the problem of finding secondary structure of RNA. Experimental results show the efficacy of the proposed algorithms over the existing approach. Our proposed algorithms have potential use in various domains ranging from knowledge based frameworks to service composition, where the AND/OR structure is widely used for representing problems.
Reasoning over Ontologies with Hidden Content: The Import-by-Query Approach
Venue: arXiv cs.AI 2014
Year: 2014

There is currently a growing interest in techniques for hiding parts of the signature of an ontology Kh that is being reused by another ontology Kv. Towards this goal, in this paper we propose the import-by-query framework, which makes the content of Kh accessible through a limited query interface. If Kv reuses the symbols from Kh in a certain restricted way, one can reason over Kv U Kh by accessing only Kv and the query interface. We map out the landscape of the import-by-query problem. In particular, we outline the limitations of our framework and prove that certain restrictions on the expressivity of Kh and the way in which Kv reuses symbols from Kh are strictly necessary to enable reasoning in our setting. We also identify cases in which reasoning is possible and we present suitable import-by-query reasoning algorithms.
Avoiding and Escaping Depressions in Real-Time Heuristic Search
Venue: arXiv cs.AI 2014
Year: 2014

Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is inaccurate compared to the actual cost to reach a solution. Early real-time search algorithms, like LRTA*, easily become trapped in those regions since the heuristic values of their states may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms, like LSS-LRTA* or LRTA*(k), improve LRTA*s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We propose two ways in which depression avoidance can be implemented: mark-and-avoid and move-to-border. We implement these strategies on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is to find a single solution by running the real-time search algorithm once, we show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by one order of magnitude. Of the four new algorithms, daRTAA* produces the best solutions given a fixed deadline on the average time allowed per planning episode. We prove all our algorithms have good theoretical properties: in finite search spaces, they find a solution if one exists, and converge to an optimal after a number of trials.
Secret Sharing Schemes Based on Min-Entropies
Venue: arXiv cs.CR 2014
Year: 2014

Fundamental results on secret sharing schemes (SSSs) are discussed in the setting where security and share size are measured by (conditional) min-entropies. We first formalize a unified framework of SSSs based on (conditional) Rényi entropies, which includes SSSs based on Shannon and min entropies etc. as special cases. By deriving the lower bound of share sizes in terms of Rényi entropies based on the technique introduced by Iwamoto-Shikata, we obtain the lower bounds of share sizes measured by min entropies as well as by Shannon entropies in a unified manner. As the main contributions of this paper, we show two existential results of non-perfect SSSs based on min-entropies under several important settings. We first show that there exists a non-perfect SSS for arbitrary binary secret information and arbitrary monotone access structure. In addition, for every integers $k$ and $n$ ($k \le n$), we prove that the ideal non-perfect $(k,n)$-threshold scheme exists even if the distribution of the secret is not uniformly distributed.
Reasoning about Meaning in Natural Language with Compact Closed Categories and Frobenius Algebras
Venue: arXiv cs.CL 2014
Year: 2014

Compact closed categories have found applications in modeling quantum information protocols by Abramsky-Coecke. They also provide semantics for Lambek's pregroup algebras, applied to formalizing the grammatical structure of natural language, and are implicit in a distributional model of word meaning based on vector spaces. Specifically, in previous work Coecke-Clark-Sadrzadeh used the product category of pregroups with vector spaces and provided a distributional model of meaning for sentences. We recast this theory in terms of strongly monoidal functors and advance it via Frobenius algebras over vector spaces. The former are used to formalize topological quantum field theories by Atiyah and Baez-Dolan, and the latter are used to model classical data in quantum protocols by Coecke-Pavlovic-Vicary. The Frobenius algebras enable us to work in a single space in which meanings of words, phrases, and sentences of any structure live. Hence we can compare meanings of different language constructs and enhance the applicability of the theory. We report on experimental results on a number of language tasks and verify the theoretical predictions.
Replanning in Domains with Partial Information and Sensing Actions
Venue: arXiv cs.AI 2014
Year: 2014

Replanning via determinization is a recent, popular approach for online planning in MDPs. In this paper we adapt this idea to classical, non-stochastic domains with partial information and sensing actions, presenting a new planner: SDR (Sample, Determinize, Replan). At each step we generate a solution plan to a classical planning problem induced by the original problem. We execute this plan as long as it is safe to do so. When this is no longer the case, we replan. The classical planning problem we generate is based on the translation-based approach for conformant planning introduced by Palacios and Geffner. The state of the classical planning problem generated in this approach captures the belief state of the agent in the original problem. Unfortunately, when this method is applied to planning problems with sensing, it yields a non-deterministic planning problem that is typically very large. Our main contribution is the introduction of state sampling techniques for overcoming these two problems. In addition, we introduce a novel, lazy, regression-based method for querying the agents belief state during run-time. We provide a comprehensive experimental evaluation of the planner, showing that it scales better than the state-of-the-art CLG planner on existing benchmark problems, but also highlighting its weaknesses with new domains. We also discuss its theoretical guarantees.
Integrative Semantic Dependency Parsing via Efficient Large-scale Feature Selection
Venue: arXiv cs.CL 2014
Year: 2014

Semantic parsing, i.e., the automatic derivation of meaning representation such as an instantiated predicate-argument structure for a sentence, plays a critical role in deep processing of natural language. Unlike all other top systems of semantic dependency parsing that have to rely on a pipeline framework to chain up a series of submodels each specialized for a specific subtask, the one presented in this article integrates everything into one model, in hopes of achieving desirable integrity and practicality for real applications while maintaining a competitive performance. This integrative approach tackles semantic parsing as a word pair classification problem using a maximum entropy classifier. We leverage adaptive pruning of argument candidates and large-scale feature selection engineering to allow the largest feature space ever in use so far in this field, it achieves a state-of-the-art performance on the evaluation data set for CoNLL-2008 shared task, on top of all but one top pipeline system, confirming its feasibility and effectiveness.
An adaptive Simulated Annealing-based satellite observation scheduling method combined with a dynamic task clustering strategy
Venue: arXiv cs.AI 2014
Year: 2014

Efficient scheduling is of great significance to rationally make use of scarce satellite resources. Task clustering has been demonstrated to realize an effective strategy to improve the efficiency of satellite scheduling. However, the previous task clustering strategy is static. That is, it is integrated into the scheduling in a two-phase manner rather than in a dynamic fashion, without expressing its full potential in improving the satellite scheduling performance. In this study, we present an adaptive Simulated Annealing based scheduling algorithm aggregated with a dynamic task clustering strategy (or ASA-DTC for short) for satellite observation scheduling problems (SOSPs). First, we develop a formal model for the scheduling of Earth observing satellites. Second, we analyze the related constraints involved in the observation task clustering process. Thirdly, we detail an implementation of the dynamic task clustering strategy and the adaptive Simulated Annealing algorithm. The adaptive Simulated Annealing algorithm is efficient, with the endowment of some sophisticated mechanisms, i.e. adaptive temperature control, tabu-list based revisiting avoidance mechanism, and intelligent combination of neighborhood structures. Finally, we report on experimental simulation studies to demonstrate the competitive performance of ASA-DTC. Moreover, we show that ASA-DTC is especially effective when SOSPs contain a large number of targets or these targets are densely distributed in a certain area.
Analysis and Diversion of Duqu's Driver
Venue: arXiv cs.CR 2014
Year: 2014

The propagation techniques and the payload of Duqu have been closely studied over the past year and it has been said that Duqu shared functionalities with Stuxnet. We focused on the driver used by Duqu during the infection, our contribution consists in reverse-engineering the driver: we rebuilt its source code and analyzed the mechanisms it uses to execute the payload while avoiding detection. Then we diverted the driver into a defensive version capable of detecting injections in Windows binaries, thus preventing further attacks. We specifically show how Duqu's modified driver would have detected Duqu.
Exploiting citation networks for large-scale author name disambiguation
Venue: arXiv cs.DL 2014
Year: 2014

We present a novel algorithm and validation method for disambiguating author names in very large bibliographic data sets and apply it to the full Web of Science (WoS) citation index. Our algorithm relies only upon the author and citation graphs available for the whole period covered by the WoS. A pair-wise publication similarity metric, which is based on common co-authors, self-citations, shared references and citations, is established to perform a two-step agglomerative clustering that first connects individual papers and then merges similar clusters. This parameterized model is optimized using an h-index based recall measure, favoring the correct assignment of well-cited publications, and a name-initials-based precision using WoS metadata and cross-referenced Google Scholar profiles. Despite the use of limited metadata, we reach a recall of 87% and a precision of 88% with a preference for researchers with high h-index values. 47 million articles of WoS can be disambiguated on a single machine in less than a day. We develop an h-index distribution model, confirming that the prediction is in excellent agreement with the empirical data, and yielding insight into the utility of the h-index in real academic ranking scenarios.
Affine extractors over large fields with exponential error
Venue: arXiv cs.CC 2014
Year: 2014

We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.
Maximally persistent connections for the periodic type
Venue: arXiv cs.SY 2014
Year: 2014

This paper considers the optimal control problem of connecting two periodic trajectories with maximal persistence. A maximally persistent trajectory is close to the periodic type in the sense that the norm of the image of this trajectory under the operator defining the periodic type is minimal among all trajectories. A solution is obtained in this paper for the case when the two trajectories have the same period but it turns out to be only piecewise continuous and so an alternate norm is employed to obtain a continuous connection. The case when the two trajectories have different but rational periods is also solved. The problem of connecting periodic trajectories is of interest because of the observation that the operating points of many biological and artificial systems are limit cycles and so there is a need for a unified optimal framework of connections between different operating points. This paper is a first step towards that goal.
Using Neural Network to Propose Solutions to Threats in Attack Patterns
Venue: arXiv cs.CR 2014
Year: 2014

In the last decade, a lot of effort has been put into securing software application during development in the software industry. Software security is a research field in this area which looks at how security can be weaved into software at each phase of software development lifecycle (SDLC). The use of attack patterns is one of the approaches that have been proposed for integrating security during the design phase of SDLC. While this approach help developers in identify security flaws in their software designs, the need to apply the proper security capability that will mitigate the threat identified is very important. To assist in this area, the uses of security patterns have been proposed to help developers to identify solutions to recurring security problems. However due to different types of security patterns and their taxonomy, software developers are faced with the challenge of finding and selecting appropriate security patterns that addresses the security risks in their design. In this paper, we propose a tool based on Neural Network for proposing solutions in form of security patterns to threats in attack patterns matching attacking patterns. From the result of performance of the neural network, we found out that the neural network was able to match attack patterns to security patterns that can mitigate the threat in the attack pattern. With this information developers are better informed in making decision on the solution for securing their application.
From Safety To Termination And Back: SMT-Based Verification For Lazy Languages
Venue: arXiv cs.PL 2014
Year: 2014

SMT-based verifiers have long been an effective means of ensuring safety properties of programs. While these techniques are well understood, we show that they implicitly require eager semantics; directly applying them to a lazy language is unsound due to the presence of divergent sub-computations. We recover soundness by composing the safety analysis with a termination analysis. Of course, termination is itself a challenging problem, but we show how the safety analysis can be used to ensure termination, thereby bootstrapping soundness for the entire system. Thus, while safety invariants have long been required to prove termination, we show how termination proofs can be to soundly establish safety. We have implemented our approach in liquidHaskell, a Refinement Type-based verifier for Haskell. We demonstrate its effectiveness via an experimental evaluation using liquidHaskell to verify safety, functional correctness and termination properties of real-world Haskell libraries, totaling over 10,000 lines of code.
(Un)decidable Problems about Reachability of Quantum Systems
Venue: arXiv cs.LO 2014
Year: 2014

We study the reachability problem of a quantum system modelled by a quantum automaton. The reachable sets are chosen to be boolean combinations of (closed) subspaces of the state space of the quantum system. Four different reachability properties are considered: eventually reachable, globally reachable, ultimately forever reachable, and infinitely often reachable. The main result of this paper is that all of the four reachability properties are undecidable in general; however, the last three become decidable if the reachable sets are boolean combinations without negation.
Information Leakage of Correlated Source Coded Sequences over Channel with an Eavesdropper
Venue: arXiv cs.IT 2014
Year: 2014

A new generalised approach for multiple correlated sources over a wiretap network is investigated. A basic model consisting of two correlated sources where each produce a component of the common information is initially investigated. There are several cases that consider wiretapped syndromes on the transmission links and based on these cases a new quantity, the information leakage at the source/s is determined. An interesting feature of the models described in this paper is the information leakage quantification. Shannon's cipher system with eavesdroppers is incorporated into the two correlated sources model to minimize key lengths. These aspects of quantifying information leakage and reducing key lengths using Shannon's cipher system are also considered for a multiple correlated source network approach. A new scheme that incorporates masking using common information combinations to reduce the key lengths is presented and applied to the generalised model for multiple sources.
Delay-Energy lower bound on Two-Way Relay Wireless Network Coding
Venue: arXiv cs.IT 2014
Year: 2014

Network coding is a novel solution that significantly improve the throughput and energy consumed of wireless networks by mixing traffic flows through algebraic operations. In conventional network coding scheme, a packet has to wait for packets from other sources to be coded before transmitting. The wait-and-code scheme will naturally result in packet loss rate in a finite buffer. We will propose Enhanced Network Coding (ENC), an extension to ONC in continuous time domain. In ENC, the relay transmits both coded and uncoded packets to reduce delay. In exchange, more energy is consumed in transmitting uncoded packets. ENC is a practical algorithm to achieve minimal average delay and zero packet-loss rate under given energy constraint. The system model for ENC on a general renewal process queuing is presented. In particular, we will show that there exists a fundamental trade-off between average delay and energy. We will also present the analytic result of lower bound for this trade-off curve, which can be achieved by ENC.
A Security Plan for Smart Grid Systems Based On AGC4ISR
Venue: arXiv cs.CR 2014
Year: 2014

This paper is proposed a security plan for Smart Grid Systems based on AGC4ISR which is an architecture for Autonomic Grid Computing Systems. Smart Grid incorporates has many benefits of distributed computing and communications to deliver a real-time information and enable the near-instantaneous balance of supply and demand at the device level. AGC4ISR architecture is Organized by Autonomic Grid Computing and C4ISR (Command, Control, Communications, Computers and Intelligence, Surveillance, & Reconnaissance) Architecture. In this paper we will present a solution for as security plan which will be consider encryption, intrusion detection, key management and detail of cyber security in Smart Grids. In this paper we use the cryptography for the packet in the C4ISR and we use a key management for send and receive a packet in the smart grid because it is necessary for intelligent networks to keeping away from packet missing.