Parameterized complexity of basic decision problems for tree automata

There are many decision problems in automata theory (including membership, emptiness, inclusion and universality problems) that are NP-hard for some classes of tree automata (TA). The study of their parameterized complexity allows us to find new bounds of their nonpolynomial time algorithmic behaviours. We present results of such a study for classical TA, rigid tree automata, TA with global equality and disequality and t-DAG automata. As parameters we consider the number of states, the cardinality of the signature, the size of the term or the t-dag and the size of the automaton.     

A coalgebraic introduction to CSP

The paper presents a first step of a coalgebraic analysis of the concept of communicating sequential processes as introduced by Hoare in [3]. We make apparent the strong relationship between CSP and partial automata, i.e., special coalgebras. Thereby it turns out that [3] is only dealt with very special automata, namely, with final automata, i.e., automata where the difference between the concepts of state and of process, respectively, disappears. The coalgebraic approach will allow us to develop a proper model theory for process calculi. As first steps in this direction we outline firstly how operations on processes can be generalized in a compatible way to constructions on automata. Secondly, we present a new method for solving recursive process equations. Finally, we discuss that the nondeterminism in CSP can not be modeled based on nondeterministic transition systems usually considered in the coalgebraic literature [5].     

User support: revealing structure instead of surface

The development of different help systems and the application of numerous approaches to user support have shown (a) that end-users may encounter insuperably complex use situations, and (b) that it is possible to assist users significantly by implementing computerized help systems. There are many approaches to the realization of user support, varying from the use of natural language to user modelling. However, the current help systems seem to focus on relatively technical data processing issues, ignoring the organizational context in which the use takes place. It is asserted in this paper that it is relevant for users to perceive the organizational context and that it is possible to reflect the context in a support system. Representing the context in a support system is made possible by introducing a context database. A context database is parallel to the actual database and contains information about task flows, task-connected information objects and the like. Therefore the analysis of work and information systems has to be based on related areas. The areas of inquiry are (a) tasks, (b) job design, (c) organization of work, (d) computer applications and (e) information media. The following kinds of mappings can be incorporated within the context database: [organizational unit Ol]-T_person PI in job]-[job task Tl]-[task-connected information Il]-[task-connected information 12]-[job task T2]-[person in job P2]-[organizational unit O2], This type of chain (or parts of it) can then be visualized as context support.     

The dilemma between arc and bounds consistency

Consistency enforcement is used to prune the search tree of a constraint satisfaction problem (CSP). Arc consistency (AC) is a well-studied consistency level, with many implementations. Bounds consistency (BC), a looser consistency level, is known to have equal time complexity to AC. To solve a CSP, we have to implement an algorithm of our own or employ an existing solver. In any case, at some point, we have to decide between enforcing either AC or BC. As the choice between AC or BC is more or less predefined and currently made without considering the individualities of each CSP, this study attempts to make this decision deterministic and efficient, without the need of trial and error. We find that BC fits better while solving a CSP with its maximum domains' size being greater than its constrained variables number. We study the behavior of maintaining arc or bounds consistency during search, and we show how the overall search methods complexity is affected by the employed consistency level.     

The configuration and detection strategies for information security systems

Intrusion Detection Systems (IDSs) have become an important element of the Information Technology (IT) security architecture by identifying intrusions from both insiders and outsiders. However, security experts questioned the effectiveness of IDSs recently. The criticism known as Base Rate fallacy states that when IDS raises an alarm, the event is more likely to be benign rather than intrusive since the proportion of benign activity is significantly larger than that of intrusive activity in the user population. In response to too many false alarms, system security officers (SSO) either ignore alarm signals or turn off the IDS as the information provided by IDS is very skeptical. To alleviate this problem of IDSs, Ogut et al. (2008) [6] suggest that the firm may choose to wait to get additional signal and to make better decision about user type. One of the limitations of their model is that configuration point at which IDSs operate (the false negative and false positive rates) is exogenously given. However, the firm trying to minimize expected cost should also make a decision regarding the configuration level of IDSs since these probabilities are one of the determinants of future cost. Therefore, we extend Ogut et al. (2008) [6] by considering configuration and waiting time decisions jointly in this paper. We formulate the problem as dynamic programming model and illustrate the solution procedure for waiting time and configuration decision under optimal policy when cost of undetected hacker activity follows step wise function. As it is difficult to obtain waiting time and configuration decision under optimal policy, we illustrate the solution procedures for under myopic policy and focus on the characteristics of configuration decision under myopic policy. Our numerical analysis suggested that configuration decision is as important as waiting time decision to decrease the cost of operating IDS.     

微小卫星集群协同观测构形调整规划

以微小卫星集群实现小行星探测为背景,研究局部信息交互的空间目标观测任务构形调整.针对难以直接求取集群构形调整的全局最优解问题,利用通信协调图,将全局协调决策分解成多个局部求解问题,并引入强化学习机制实现求解.针对集群全局协调决策问题,通过设计基于Max-plus算法的全局协调决策算法来实现全局协作;针对单星局部优化问题,设计基于神经网络的局部Q学习算法来实现单星动作调整规划.仿真结果表明,本文所提的协作规划算法能自主有效地将集群调整至期望构形,实现协同观测任务.     

On user-centric memetic algorithms

Memetic algorithms (MAs) constitute a metaheuristic optimization paradigm [usually based on the synergistic combination of an evolutionary algorithm (EA) and trajectory-based optimization techniques] that systematically exploits the knowledge about the problem being solved and that has shown its efficacy to solve many combinatorial optimization problems. However, when the search depends heavily on human-expert’s intuition, the task of managing the problem knowledge might be really difficult or even indefinable/impossible; the so-called interactive evolutionary computation (IEC) helps to mitigate this problem by enabling the human user to interact with an EA during the optimization process. Interactive MAs can be constructed as reactive models in which the MA continuously demands the intervention of the human user; this approach has the drawback that provokes fatigue to the user. This paper considers user-centric MAs, a more global perspective of interactive MAs since it hints possibilities for the system to be proactive rather than merely interactive, i.e., to anticipate some of the user behavior and/or exhibit some degree of creativity, and provides some guidelines for the design of two different models for user-centric MAs, namely reactive and proactive search-based schema. An experimental study over two complex NP-hard problems, namely the Traveling Salesman problem and a Gene Ordering Problem, shows that user-centric MAs are in general effective optimization methods although the proactive approach provides additional advantages.     

Multi-variable distributed backtracking with sessions

The Constraint Satisfaction Problem (CSP) formalism is used to represent many combinatorial decision problems instances simply and efficiently. However, many such problems cannot be solved on a single, centralized computer for various reasons (e.g., their excessive size or privacy). The Distributed CSP (DisCSP) extends the CSP model to allow such combinatorial decision problems to be modelled and handled. In this paper, we propose a complete DisCSP-solving algorithm, called Distributed Backtracking with Sessions (DBS), which can solve DisCSP so that each agent encapsulates a whole “complex” problem with many variables and constraints. We prove that the algorithm is sound and complete, and generates promising experimental results.     

User support: revealing structure instead of surface

Abstract

The development of different help systems and the application of numerous approaches to user support have shown (a) that end-users may encounter insuperably complex use situations, and (b) that it is possible to assist users significantly by implementing computerized help systems. There are many approaches to the realization of user support, varying from the use of natural language to user modelling. However, the current help systems seem to focus on relatively technical data processing issues, ignoring the organizational context in which the use takes place. It is asserted in this paper that it is relevant for users to perceive the organizational context and that it is possible to reflect the context in a support system. Representing the context in a support system is made possible by introducing a context database. A context database is parallel to the actual database and contains information about task flows, task-connected information objects and the like. Therefore the analysis of work and information systems has to be based on related areas. The areas of inquiry are (a) tasks, (b) job design, (c) organization of work, (d) computer applications and (e) information media. The following kinds of mappings can be incorporated within the context database: [organizational unit Ol]-T_person PI in job]-[job task Tl]-[task-connected information Il]-[task-connected information 12]-[job task T2]-[person in job P2]-[organizational unit O2], This type of chain (or parts of it) can then be visualized as context support.     

基于欧氏距离的支持向量机决策树构造方法

SVM决策树是解决多分类问题的有效方法之一,由于分类器组合策略不同,构成的决策树构型以及分类精确度也各有差异。提出基于欧氏距离的SVM决策树构造方法,通过两种欧氏距离组合策略,生成不同构型的SVM决策树。实验结果表明,采用组合策略二的SVM决策树分类器相比组合策略一,具有更高的分类精度和更短的训练及测试时间。     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

A polynomial relational class of binary CSP

Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-hard task. Considerable effort has been spent on identifying tractable classes of CSP, in other words, classes of constraint satisfaction problems for which there are polynomial time recognition and resolution algorithms. In this article, we present a relational tractable class of binary CSP. Our key contribution is a new ternary operation that we name mjx. We first characterize mjx-closed relations which leads to an optimal algorithm to recognize such relations. To reduce space and time complexity, we define a new storage technique for these relations which reduces the complexity of establishing a form of strong directional path consistency, the consistency level that solves all instances of the proposed class (and, indeed, of all relational classes closed under a majority polymorphism).     

无人机辅助的双层深度强化学习任务卸载算法

为了解决无人机轨迹优化、用户功率分配和任务卸载策略问题,提出了一种双层深度强化学习任务卸载算法。上层采用多智能体深度强化学习来优化无人机的轨迹,并动态分配用户的传输功率以提高网络传输速率;下层采用多个并行的深度神经网络来求解最优卸载决策以最小化网络的时延和能耗。仿真结果表明,该算法使得无人机能够跟踪用户的移动,显著降低系统的时延和能耗,能够给用户提供更优质的任务卸载服务。     

Solution Generation with Qualitative Models of Preferences

We consider automated decision aids that help users select the best solution from a large set of options. For such tools to successfully accomplish their task, eliciting and representing users' decision preferences is a crucial task. It is usually too complex to get a complete and accurate model of their preferences, especially regarding the trade-offs between different criteria.We consider decision aid tools where users specify their preferences qualitatively : they are only able to state the criteria they consider, but not the precise numerical utility functions. For each criterion, the tool provides a standardized numerical function that is fixed and identical for all users and used to compare solutions. To compensate for the imprecision of this qualitative model, we let the user choose among a displayed set of possibilities rather than a single optimal solution. We consider the probability of finding the most preferred solution as a function of the number of displayed possibilities and the number of preferences. We present a probabilistic analysis, empirical validation on randomly generated configuration problems and a commercial application. We provide mathematical principles for the design of the selection mechanism, guaranteeing that users are able to find the target solution.     

基于改进的代价敏感决策树的网络贷款分类

在网络贷款用户数据集中，贷款成功和贷款失败的用户数量存在着严重的不平衡，传统的机器学习算法在解决该类问题时注重整体分类正确率，导致贷款成功用户的预测精度较低。针对此问题，在代价敏感决策树敏感函数的计算中加入类分布，以减弱正负样本数量对误分类代价的影响，构建改进的代价敏感决策树；以该决策树作为基分类器并以分类准确度作为衡量标准选择表现较好的基分类器，将它们与最后阶段生成的分类器集成得到最终的分类器。实验结果表明，与已有的常用于解决此类问题的算法（如MetaCost算法、代价敏感决策树、AdaCost算法等）相比，改进的代价敏感决策树对网络贷款用户分类可以降低总体的误分类错误率，具有更强的泛化能力。     

基于相似度衡量的决策树自适应迁移

如何解决迁移学习中的负迁移问题并合理把握迁移的时机与方法,是影响迁移学习广泛应用的关键点. 针对这个问题,提出一种基于相似度衡量机制的决策树自适应迁移方法（Self-adaptive transfer for decision trees based on a similarity metric,STDT）. 首先,根据源任务数据集是否允许访问,自适应地采用成分预测概率或路径预测概率对决策树间的相似性进行判定,其亲和系数作为量化衡量关联任务相似程度的依据. 然后,根据多源判定条件确定是否采用多源集成迁移,并将相似度归一化后依次分配给待迁移源决策树作为迁移权值. 最后,对源决策树进行集成迁移以辅助目标任务实现决策. 基于UCI 机器学习库的仿真结果说明,与多源迁移加权求和算法（Weighted sum rule,WSR）和MS-TrAdaBoost 相比,STDT 能够在保证决策精度的前提下实现更为快速的迁移.     

一种基于Schema的XML索引结构

XML Schema作为一种描述XML文档模式信息即结构信息的标准，对于XML索引的建立及查询效率的提高有着重要的作用。现有的大部分XML索引结构着重研究XML文档的结构查询，而对于XML文档的更新支持却不多，对无效查询也不能作出快速的判断。该文基于已有的XML文档的编码方式，提出了一种基于Schema的XML索引结构，不仅能支持基于有效性验证的动态更新，使得XML文档和XML Schema保持一致，而且对用户提出的无效的路径查询也能在较短时间内作出判断。     

弱可逆线性有限自动机的一种分解

讨论有限自动机的分解有助于分析弱可逆有限自动机的结构和求解弱逆.首先证明了弱同构的弱可逆有限自动机具有相似的分解形式;接着考虑了一类特殊的弱可逆线性有限自动机的分解,从状态输出权的角度刻画了该分解存在的一个充分条件;然后把这种分解形式推广到了一般的弱可逆线性有限自动机上,即:延迟τ步弱可逆线性有限自动机分解成延迟0步弱可逆有限自动机和一种特殊的有限自动机MD,并得到了分解存在的充要条件;最后,用输出序列的代数性质来刻画其中的充分条件,并把它转化成了一个矩阵的秩的计算.这种分解形式并不局限于n元弱可逆有限自动机,而且分解条件也比较简单,仅与输出序列的性质有关.     

User Behavior Model Based on Affordances and Emotions: A New Approach for an Optimal Use Method in Product–User Interactions

This study proposes a new approach to developing a user behavior model to explain how a user finds the optimal use. This is achieved by considering user concerns, task significances, affordances, and emotional responses as the interaction components and by exploring behavior sequences for a goal in using a product the first time. The tasks in the same group at each level in the user concern structure are therefore in a competing relationship in going up to a higher task. The task tree with the significances and the affordance probabilities can be analyzed. The order of a user’s exploring behavior sequences can be determined through comparisons of the expected significances, which can be obtained by the modified subjective expected utility theory. A user’s emotional responses for the tasks that a behavior sequence is composed of can be calculated by the modified decision affect theory. Here, the emotional response refers to a user’s internal reactions for the degree to which a product’s affordance features can meet his or her mental model in use. The average emotional response for a behavior sequence can be a user’s decisional factor for the optimal use method in using a product with a goal. Also, the design problems of a product can be checked from users’ point of view, and the emotional losses/changes by usage failures can be discussed. For an illustrative purpose, the proposed model is applied to a numerical example with some assumptions.     

面向本体的SDO数据交换蚁群优化策略

在使用服务数据对象SDO（Service Data Objects）过程中,针对SDO连接异构数据源存在的效率和一致性问题,提出一种面向文法和自动机的推理方法,同时,引入本体进行语义描述数据交换,增强SDO语义识别,并通过数据中介服务（DMS）建立一种异构数据源访问数据图的图结构,根据数据图的需求变更以及数据访问服务（DAS）实现行图裁剪成一棵棵数据对象最优树,建立相应的优化数学模型,并通过蚁群算法优化寻优该模型。最后通过在开源件SDO API中引入策略应用表示：提高了不同的数据源访问效率,增强了数据交换的一致性和语义性。