Robust Redundancy Scheme for the Repair Process: Hierarchical Codes in the Bandwidth-Limited Systems

High performance computing can be well supported by the Grid or cloud computing systems. However, these systems have to overcome the failure risks, where data is stored in the “unreliable” storage nodes that can leave the system at any moment and the nodes’ network bandwidth is limited. In this case, the basic way to assure data reliability is to add redundancy using either replication or erasure codes. As compared to replication, erasure codes are more space efficient. Erasure codes break data into blocks, encode these blocks and distribute them into different storage nodes. When storage nodes permanently or temporarily abandon the system, new redundant blocks must be created to guarantee the data reliability, which is referred to as repair. Later when the churn nodes rejoin the system, the blocks stored in these nodes can reintegrate the data group to enhance the data reliability. For “classical” erasure codes, generating a new block requires to transmit a number of k blocks over the network, which brings lots of repair traffic, high computation complexity and high failure probability for the repair process. Then a near-optimal erasure code named Hierarchical Codes, has been proposed that can significantly reduce the repair traffic by reducing the number of nodes participating in the repair process, which is referred to as the repair degree d. To overcome the complexity of reintegration and provide an adaptive reliability for Hierarchical Codes, we refine two concepts called location and relocation, and then propose an integrated maintenance scheme for the repair process. Our experiments show that Hierarchical Code is the most robust redundancy scheme for the repair process as compared to other famous coding schemes.     

Recognition of word collocation habits using frequency rank ratio and inter-term intimacy

An effective algorithm for extracting two useful features from text documents for analyzing word collocation habits, “Frequency Rank Ratio” (FRR) and “Intimacy”, is proposed. FRR is derived from a ranking index of a word according to its word frequency. Intimacy, computed by a compact language model called Influence Language Model (ILM), measures how close a word is to others within the same sentence. Using the proposed features, a visualization framework is developed for word collocation analysis. To evaluate our proposed framework, two corpora are designed and collected from the real-life data covering diverse topics and genres. Extensive simulations are conducted to illustrate the feasibility and effectiveness of our visualization framework. Our results demonstrate that the proposed features and algorithm are able to conduct reliable text analysis efficiently.     

Security adoption and influence of cyber-insurance markets in heterogeneous networks

Hosts (or nodes) in the Internet often face epidemic risks such as virus and worm attack. Despite the awareness of these risks and the importance of network/system security, investment in security protection is still scare, and hence epidemic risk is still prevalent. Deciding whether to invest in security protection is an interdependent process: security investment decision made by one node can affect the security risk of others, and therefore affect their decisions also. The first contribution of this paper is to provide a fundamental understanding on how “network externality” with “node heterogeneity” may affect security adoption. Nodes make decisions on security investment by evaluating the epidemic risk and the expected loss. We characterize it as a Bayesian network game in which nodes only have the local information, e.g., the number of neighbors, and minimum common information, e.g., degree distribution of the network. Our second goal is to study a new form of risk management, called cyber-insurance. We investigate how the presence of a competitive insurance market can affect the security adoption and show that if the insurance provider can observe the protection level of nodes, the insurance market is a positive incentive for security adoption if the protection quality is not very high. We also find that cyber-insurance is more likely to be a good incentive for nodes with higher degree. Conversely, if the insurance provider cannot observe the protection level of nodes, we verify that partial insurance can be a non-negative incentive, improving node’s utility though not being an incentive.     

Building actions from classification rules

Rule induction has attracted a great deal of attention in Machine Learning and Data Mining. However, generating rules is not an end in itself because their applicability is not straightforward especially when their number is large. Ideally, the ultimate user would like to use these rules to decide which actions to undertake. In the literature, this notion is usually referred to as actionability. We propose a new framework to address actionability. Our goal is to lighten the burden of analyzing a large set of classification rules when the user is confronted to an “unsatisfactory situation” and needs help to decide about the appropriate actions to remedy to this situation. The method consists in comparing the situation to a set of classification rules. For this purpose, we propose   a new framework for learning action recommendations dealing with complex notions of feasibility and quality of actions. Our approach has been motivated by an environmental application aiming at building a tool to help specialists in charge of the management of a catchment to preserve stream-water quality. The results show the utility of this methodology with regard to enhancing the actionability of a set of classification rules in a real-world application.     

Lightweight Bytecode Verification

In this paper, we provide a theoretical foundation for and improvements to the existing bytecode verification technology, a critical component of the Java security model, for mobile code used with the Java “micro edition” (J2ME), which is intended for embedded computing devices. In Java, remotely loaded “bytecode” class files are required to be bytecode verified before execution, that is, to undergo a static type analysis that protects the platform's Java run-time system from so-called type confusion attacks such as pointer manipulation. The data flow analysis that performs the verification, however, is beyond the capacity of most embedded devices because of the memory requirements that the typical algorithm will need. We propose to take a proof-carrying code approach to data flow analysis in defining an alternative technique called “lightweight analysis” that uses the notion of a “certificate” to reanalyze a previously analyzed data flow problem, even on poorly resourced platforms. We formally prove that the technique provides the same guarantees as standard bytecode safety verification analysis, in particular that it is “tamper proof” in the sense that the guarantees provided by the analysis cannot be broken by crafting a “false” certificate or by altering the analyzed code. We show how the Java bytecode verifier fits into this framework for an important subset of the Java Virtual Machine; we also show how the resulting “lightweight bytecode verification” technique generalizes and simulates the J2ME verifier (to be expected as Sun's J2ME “K-Virtual machine” verifier was directly based on an early version of this work), as well as Leroy's “on-card bytecode verifier,” which is specifically targeted for Java Cards.     

基于Q学习的受灾路网抢修队调度问题建模与求解

受损路网的修复是灾害应急响应中的一个重要环节, 主要研究如何规划道路抢修队的修复活动, 为灾后救援快速打通生命通道.本文首先构建了抢修队修复和路线规划的数学模型, 然后引入马尔科夫决策过程来模拟抢修队的修复活动, 并基于Q学习算法求解抢修队的最优调度策略.对比实验结果表明, 本文方法能够让抢修队从全局和长远角度实施受损路段的修复活动, 在一定程度上提高了运输效率和修复效率, 可以为政府实施应急救援和快速安全疏散灾民提供有益的参考.     

基于SVM多分类决策树的研究综述

支持向量机(Support Vector Machine,SVM)是一种基于统计学习理论的机器学习方法,由于其出色的学习性能,早已成为当前机器学习界的研究热点;而决策树是一种功能强大且相当受欢迎的分类和预测工具。本文重点介绍支持向量机与决策树结合解决多分类问题的算法,并对其进行评析和总结。     

一种面向严重受损路网的抢修队调度算法

受损路网抢修是灾害应急响应中的一个非常重要的基础环节,主要研究如何对道路抢修队进行有效调度,以快速恢复受灾路网的交通能力,为后续顺利展开应急救援工作提供有效的保证.已有方法在路网受损严重的情形下往往难以给出有效的调度策略.为此,在已有工作的基础上,简化路网模型和决策模型,并基于动作集裁减和Q学习设计一种面向严重受损路网的抢修队调度算法.在该算法中,抢修队只能从当前可达的未修复受损路段集合中选择下一个动作,以确保Q学习的连续性.仿真实验结果表明,在节点数和受损率都较大的严重受损路网环境中,所提算法可以保证所有需求节点均可达,具有更高的稳定性和可靠性,且能够在更小的时间和修复代价内给出更优的调度方案.     

Towards a theory of local and global in computation

We formulate the rudiments of a method for assessing the difficulty of dividing a computational problem into “independent simpler parts”. This work illustrates measures of complexity which attempt to capture the distinction between “local” and “global” computational problems. One such measure is the covering multiplicity, or average number of partial computations which take account of a given piece of data. Another measure reflects the intuitive notion of a “highly interconnected” computational problem, for which subsets of the data cannot be processed “in isolation”. These ideas are applied in the setting of computational geometry to show that the connectivity predicate has unbounded covering multiplicity and is highly interconnected; and in the setting of numerical computations to measure the complexity of evaluating polynomials and solving systems of linear equations.     

Machine learning for science and society

The special issue on “Machine Learning for Science and Society” showcases machine learning work with influence on our current and future society. These papers address several key problems such as how we perform repairs on critical infrastructure, how we predict severe weather and aviation turbulence, how we conduct tax audits, whether we can detect privacy breaches in access to healthcare data, and how we link individuals across census data sets for new insights into population changes. In this introduction, we discuss the need for such a special issue within the context of our field and its relationship to the broader world. In the era of “big data,” there is a need for machine learning to address important large-scale applied problems, yet it is difficult to find top venues in machine learning where such work is encouraged. We discuss the ramifications of this contradictory situation and encourage further discussion on the best strategy that we as a field may adopt. We also summarize key lessons learned from individual papers in the special issue so that the community as a whole can benefit.     

基于移动节点的无线传感器网络覆盖空洞修复方法

无线传感器网络（ WSNs）一旦产生覆盖空洞,则会严重影响网络性能,针对此问题,提出了一种基于移动节点的覆盖空洞修复算法——联合补丁法,该算法按照预先制定的缝制方案把所需的移动节点“缝制”成一块大的“布”,然后对空洞进行直接修复。首先,在理论上证明了该算法的性能;其次,用Matlab进行仿真实验,并与基于移动节点的三角形逐个贴片修复算法（ PATT）在所需节点数和冗余度两方面进行对比;最后,对算法的稳定性进行了分析。最终表明：该算法具有较高的覆盖率和较低的冗余度。     

Applying incremental Deep Neural Networks-based posture recognition model for ergonomics risk assessment in construction

Monitoring and assessing awkward postures is a proactive approach for Musculoskeletal Disorders (MSDs) prevention in construction. Machine Learning models have shown promising results when used in recognition of workers’ posture from Wearable Sensors. However, there is a need to further investigate: i) how to enable Incremental Learning, where trained recognition models continuously learn new postures from incoming subjects while controlling the forgetting of learned postures; ii) the validity of ergonomics risk assessment with recognized postures. The research discussed in this paper seeks to address this need through an adaptive posture recognition model– the incremental Convolutional Long Short-Term Memory (CLN) model. The paper discusses the methodology used to develop and validate this model’s use as an effective Incremental Learning strategy. The evaluation was based on real construction workers’ natural postures during their daily tasks. The CLN model with “shallow” (up to two) convolutional layers achieved high recognition performance (Macro F1 Score) under personalized (0.87) and generalized (0.84) modeling. Generalized CLN model, with one convolutional layer, using the “Many-to-One” Incremental Learning scheme can potentially balance the performance of adaptation and controlling forgetting. Applying the ergonomics rules on recognized and ground truth postures yielded comparable risk assessment results. These findings support that the proposed incremental Deep Neural Networks model has a high potential for adaptive posture recognition. They can be deployed alongside ergonomics rules for effective MSDs risk assessment.     

A machine discovery from amino acid sequences by decision trees over regular patterns

This paper describes a machine learning system that discovered a “negative motif”, in transmembrane domain identification from amino acid sequences, and reports its experiments on protein data using PIR database. We introduce a decision tree whose nodes are labeled with regular patterns. As a hypothesis, the system produces such a decision tree for a small number of randomly chosen positive and negative examples from PIR. Experiments show that our system finds reasonable hypotheses very successfully. As a theoretical foundation, we show that the class of languages defined by decesion trees of depth at mostd overk-variable regular patterns is polynomial-time learnable in the sense of probably approximately correct (PAC) learning for any fixedd, k≥0.     

Efficient trigger-broadcasting in heterogeneous clusters

Broadcasts in parallel computing environments are often used to trigger “personal” computations at the processors (or, nodes) that comprise the system. (The qualifier “personal” means that the triggered computations may differ in type and complexity at each node.) We present an algorithm for trigger-broadcasting in a node-heterogeneous cluster of workstations, which comes predictably close to minimizing the time for completing both the broadcast and the computations it triggers. The algorithm orchestrates its broadcast taking account of: the speeds of the cluster's constituent workstations, the speed of the cluster's network, and the complexities of the computations that the broadcast triggers. The algorithm is within a constant factor of optimal when the speeds of the cluster's workstations and of its network are independent of the number of workstations. The algorithm is exactly optimal when the cluster is homogeneous—no matter how diverse the “personal” computations are.     

Linear Bayes policy for learning in contextual-bandits

Machine and Statistical Learning techniques are used in almost all online advertisement systems. The problem of discovering which content is more demanded (e.g. receive more clicks) can be modeled as a multi-armed bandit problem. Contextual bandits (i.e., bandits with covariates, side information or associative reinforcement learning) associate, to each specific content, several features that define the “context” in which it appears (e.g. user, web page, time, region). This problem can be studied in the stochastic/statistical setting by means of the conditional probability paradigm using the Bayes’ theorem. However, for very large contextual information and/or real-time constraints, the exact calculation of the Bayes’ rule is computationally infeasible. In this article, we present a method that is able to handle large contextual information for learning in contextual-bandits problems. This method was tested in the Challenge on Yahoo! dataset at ICML2012’s Workshop “new Challenges for Exploration & Exploitation 3”, obtaining the second place. Its basic exploration policy is deterministic in the sense that for the same input data (as a time-series) the same results are obtained. We address the deterministic exploration vs. exploitation issue, explaining the way in which the proposed method deterministically finds an effective dynamic trade-off based solely in the input-data, in contrast to other methods that use a random number generator.     

Logical form generation as abduction: Part II. A dual-route parsimonious covering approach

Abductive inferences are commonplace during natural language processing. Having identified some limitations of an existing parsimonious covering model of abductive diagnostic inference, we developed an extended, dual-route version to address issues in word sense disambiguation and logical form generation. the details of representing knowledge in this framework and the syntactic route of covering are described in a companion article [V. Dasigi, Int. J. Intell. Syst., 9 , 571-608 (1994)]. Here, we describe the semantic covering process in detail. A dual-route algorithm that integrates syntactic and semantic covering is given. Taking advantage of the “transitivity” of irredundant syntactic covering, plausible semantic covers are searched for, based on some heuristics, in the space of irredundant syntactic covers. Syntactic covering identifies all possible candidates for semantic covering, which in turn, helps focus syntactic covering. Attributing both syntactic and semantic facets to “open-class” linguistic concepts makes this integration possible. an experimental prototype has been developed to provide a proof-of-concept for these ideas in the context of expert system interfaces. the prototype has at least some ability to handle ungrammatical sentences, to perform some nonmonotonic inferences, etc. We believe this work provides a starting point for a nondeductive inference method for logical form generation, exploiting the associative linguistic knowledge. © 1994 John Wiley & Sons, Inc.     

Toward an efficient and scalable feature selection approach for internet traffic classification

There is significant interest in the network management and industrial security community about the need to identify the “best” and most relevant features for network traffic in order to properly characterize user behaviour and predict future traffic. The ability to eliminate redundant features is an important Machine Learning (ML) task because it helps to identify the best features in order to improve the classification accuracy as well as to reduce the computational complexity related to the construction of the classifier. In practice, feature selection (FS) techniques can be used as a preprocessing step to eliminate irrelevant features and as a knowledge discovery tool to reveal the “best” features in many soft computing applications. In this paper, we investigate the advantages and disadvantages of such FS techniques with new proposed metrics (namely goodness, stability and similarity). We continue our efforts toward developing an integrated FS technique that is built on the key strengths of existing FS techniques. A novel way is proposed to identify efficiently and accurately the “best” features by first combining the results of some well-known FS techniques to find consistent features, and then use the proposed concept of support to select a smallest set of features and cover data optimality. The empirical study over ten high-dimensional network traffic data sets demonstrates significant gain in accuracy and improved run-time performance of a classifier compared to individual results produced by some well-known FS techniques.     

大量需求点下基于深度Q学习的受损路网抢修队调度

受损路网抢修是重特大自然灾害发生后开展应急处置和救援的一个基本前提,主要研究如何对道路抢修队进行合理的调度以快速恢复路网畅通、保障救援队伍和应急物资从出救点及时输送到各需求点.鉴于已有研究在面向大量需求点时往往很难给出有效的调度策略,首先基于路网模型和马尔科夫决策过程分析抢修队修复受损路网的关键因素,并设计一种双反馈回报函数;然后基于深度Q学习求解抢修队的最优调度策略;最后通过对比实验结果表明,在大量需求点环境下,所提出方法具有较好的稳定性和可靠性,兼顾受损路网的修复效率和运输效率,能够以更少的修复代价令所有需求点可达,为灾后复杂应急场景下的受损路网抢修提供有益的尝试.