Model-based reasoning: a principled approach for software engineering

The software engineering industry suffers from almost unmanageable complexity both in the products it produces and in the processes of production. One of the current shortcomings in the software production process is the weakness of the models used. This paper makes observations on the role of knowledge in engineering and examines the central role of models and simulation. We develop an argument for the application of certain new forms of modelling methods in software engineering in order to impose more discipline and give a principled framework for building models that can support the software life-cycle. The concept of a model is examined in depth and different characteristics and types of model are defined. This introduces the relatively new concept of qualitative models and their use in the field known as model-based reasoning. Unlike previous knowledge-based methods, model-based reasoning has several important advantages. Although very few model-based software projects exist, we illustrate how this approach can be developed by drawing on applications from traditional engineering. It is argued that, because qualitative modelling offers great power for addressing the issue of complexity, such models have considerable potential as high-level abstractions of software products. These could form the core of tools for the management and support of the software development process through the whole product life-cycle.     

Properties of localized oscillatory excitation in a nonlinear oscillatory field

We analyzed the dynamics of a nonlinear oscillatory field composed of radial isochron clocks (RICs) or Stuart-Landau (SL) oscillators, which are the simplest dynamic systems that have one stable limit cycle around one unstable equilibrium. According to our computer simulation results, the nonlinear oscillatory field with two kinds of Mexican-hat-type connection had the function of several peak detections of the external input by localized oscillatory excitation areas. Moreover, the nonlinear oscillatory field could realize in-phase phase locking within each localized oscillatory excitation area, and could maximize the phase difference between the different localized oscillatory excitation areas. As the Amari (1977) model of the nerve field provided a mathematical base for the self-organizing map (SOM) algorithm, this nonlinear oscillatory field is expected to provide a theoretical base for the oscillatory SOM algorithm.     

Hierarchical trajectory refinement for a class of nonlinear systems

Trajectory generation for nonlinear control systems is an important and difficult problem. In this paper, we provide a constructive method for hierarchical trajectory refinement. The approach is based on the recent notion of φ-related control systems. Given a control affine system satisfying certain assumptions, we construct a φ-related control system of smaller dimension. Trajectories designed for the smaller, abstracted system are guaranteed, by construction, to be feasible for the original system. Constructive procedures are provided for refining trajectories from the coarser to the more detailed system.     

Hierarchical management protocol for constructing a QoS communication path in wireless Ad Hoc networks

An Ad Hoc network consists of mobile hosts that can dynamically construct a wireless network without base stations. Due to the limited communication range, a source host usually needs other hosts to relay messages to the destination in a multi-hop manner. Consequently, establishing a routing path from the source to the destination is a basic requirement for providing communication service between any pair of mobile hosts. This study proposes a two-level management approach for efficiently constructing and maintaining a QoS routing path in Ad Hoc wireless networks, significantly reducing the quantity of control packets. In the first phase, the mobile hosts are partitioned into a number of complete graphs, each represented by a Supernode managed by an agent. The Ad Hoc network topology is thus transformed to an Agent-based Graph (AG). In the second phase, some agents of a larger degree than neighboring agents are selected as core nodes. The core nodes then virtually construct a Core Graph (CG). The proposed two-level hierarchical management and bandwidth-looking-ahead technologies can efficiently establish and maintain a QoS communication path at a low control packet cost. Simulation results indicate that the proposed management model significantly reduces the number of control packets in areas with very large numbers of mobile hosts.     

一类非线性系统镇定问题的分层控制方法

通过利用分层控制设计方法,研究了一类仿射非线性系统的镇定问题.为了镇定这类系统,分层方法构建了一个简单的抽象系统,然后根据抽象系统的控制律求得原始系统的控制律.最后,一个四维仿射非线性系统的仿真例子说明了这种方法的有效性.     

Index selection for databases: a hardness study and a principled heuristic solution

We study the index selection problem: Given a workload consisting of SQL statements on a database, and a user-specified storage constraint, recommend a set of indexes that have the maximum benefit for the given workload. We present a formal statement for this problem and show that it is computationally "hard" to solve or even approximate it. We develop a new algorithm for the problem which is based on treating the problem as a knapsack problem. The novelty of our approach lies in an LP (linear programming) based method that assigns benefits to individual indexes. For a slightly modified algorithm, that does more work, we prove that we can give instance specific guarantees about the quality of our solution. We conduct an extensive experimental evaluation of this new heuristic and compare it with previous solutions. Our results demonstrate that our solution is more scalable while achieving comparable quality.     

Hierarchical state estimator: A new way for large power systems estimation

We propose a new concept suitable for performing static state estimation in large scale electric power systems. It consists in decomposing the over-all system into sub-systems and in carrying out a two-level calculation. In a lower hierarchical level, a standard state estimation is at first performed in parallel for all sub-systems and independently from each other. A coordination of these local estimations is then realized at the second (upper) hierarchical level which, by this means, receives and treats only a small number of variables. It may therefore obey various requirements, such as goegraphical, economical, etc. The advantages of this hierarchical procedure over the standard “integrated” one are drawn in the Conclusions.     

一类非线性两层规划问题的递阶优化解法

提出一种求解一类非线性两层规划问题的新方法．通过引入解耦向量将非线性两层规划问题分解为独立且易于求解的子问题，利用两级递阶结构第1级求解若干优化的子问题，而在第2级利用第1级求解的结果调整解耦向量．所提出的方法借助于分解一协调原理并按迭代方式最终求得问题的最优解．对于含整数的规划问题，通过连续化处理后也可按该方法方便地求解．算例表明所提出的算法是简便而有效的．     

Modeling nonlinear waves in a numerical wave tank with localized meshless RBF method

This paper presents the numerical simulation of free surface waves in a 2D domain which represents a wave tank, using a localized approach of the meshless radial basis function (RBF) method. Instead of global collocation, the local approach breaks down the problem domain into subdomains, leading to a sparse global system matrix which is particularly advantageous in tackling the time consuming simulation process. Mixed Eulerian–Lagrangian approach is adopted for free surface tracking and fourth order Adams–Bashforth–Moulton scheme (ABM4) is used for time stepping. Both linear and nonlinear Stokes waves are simulated and compared to analytical solutions.     

A symbolic computation approach to constructing rogue waves with a controllable center in the nonlinear systems

A symbolic computation approach to constructing higher order rogue waves with a controllable center of the nonlinear systems is presented, making use of their Hirota bilinear forms. As some examples, it turns out that some higher order rogue wave solutions of the Kadomtsev–Petviashvili (KP) type equations in $(3+1)$ and $(2+1)$-dimensions are obtained. Some features of controllable center of rogue waves are graphically discussed.     

Learning nonlinear manifolds based on mixtures of localized linear manifolds under a self-organizing framework

This paper presents a neural model which learns low-dimensional nonlinear manifolds embedded in higher-dimensional data space based on mixtures of local linear manifolds under a self-organizing framework. Compared to other similar networks, the local linear manifolds learned by our network have a more localized representation of local data distributions thanks to a new distortion measure, which removes confusion between sub-models that exists in many similar mixture models. Each neuron in the network asymptotically learns a mean vector and a principal subspace of the data in its local region. It is proved that there is no local extremum for each sub-model. Experiments show that the new mixture model is better adapted to nonlinear manifolds of various data distributions than other similar models. The online-learning property of this model is desirable when the data set is very large, when computational efficiency is of paramount importance, or when data are sequentially input. We further show an application of this model to recognition of handwritten digit images based on mixtures of local linear manifolds.     

Hierarchical evolving Dirichlet processes for modeling nonlinear evolutionary traces in temporal data

Clustering analysis aims to group a set of similar data objects into the same cluster. Topic models, which belong to the soft clustering methods, are powerful tools to discover latent clusters/topics behind large data sets. Due to the dynamic nature of temporal data, clusters often exhibit complicated patterns such as birth, branch and death. However, most existing temporal clustering models assume that clusters evolve as a linear chain, and they cannot model and detect branching of clusters. In this paper, we present evolving Dirichlet processes (EDP for short) to model nonlinear evolutionary traces behind temporal data, especially for temporal text collections. In the setting of EDP, temporal collections are divided into epochs. In order to model cluster branching over time, EDP allows each cluster in an epoch to form Dirichlet processes (DP) and uses a combination of the cluster-specific DPs as the prior for cluster distributions in the next epoch. To model hierarchical temporal data, such as online document collections, we propose a new class of evolving hierarchical Dirichlet processes (EHDP for short) which extends the hierarchical Dirichlet processes (HDP) to model evolving temporal data. We design an online learning framework based on Gibbs sampling to infer the evolutionary traces of clusters over time. In experiments, we validate that EDP and EHDP can capture nonlinear evolutionary traces of clusters on both synthetic and real-world text collections and achieve better results than its peers.     

PQAC-WN: constructing a wordnet for Pre-Qin ancient Chinese

The Princeton WordNet^® (PWN) is a widely used lexical knowledge database for semantic information processing. There are now many wordnets under creation for languages worldwide. In this paper, we endeavor to construct a wordnet for Pre-Qin ancient Chinese (PQAC), called PQAC WordNet (PQAC-WN), to process the semantic information of PQAC. In previous work, most recently constructed wordnets have been established either manually by experts or automatically using resources from which translation pairs between English and the target language can be extracted. The former method, however, is time-consuming, and the latter method, owing to a lack of language resources, cannot be performed on PQAC. As a result, a method based on word definitions in a monolingual dictionary is proposed. Specifically, for each sense, kernel words are first extracted from its definition, and the senses of each kernel word are then determined by graph-based Word Sense Disambiguation. Finally, one optimal sense is chosen from the kernel word senses to guide the mapping between the word sense and PWN synset. In this research, we obtain 66 % PQAC senses that can be shared with English and another 14 % language-specific senses that were added to PQAC-WN as new synsets. Overall, the automatic mapping achieves a precision of over 85 %.     

Mean field annealing: a formalism for constructing GNC-likealgorithms

Optimization problems are approached using mean field annealing (MFA), which is a deterministic approximation, using mean field theory and based on Peierls's inequality, to simulated annealing. The MFA mathematics are applied to three different objective function examples. In each case, MFA produces a minimization algorithm that is a type of graduated nonconvexity. When applied to the ;weak-membrane' objective, MFA results in an algorithm qualitatively identical to the published GNC algorithm. One of the examples, MFA applied to a piecewise-constant objective function, is then compared experimentally with the corresponding GNC weak-membrane algorithm. The mathematics of MFA are shown to provide a powerful and general tool for deriving optimization algorithms.     

Xheal: a localized self-healing algorithm using expanders

We consider the problem of self-healing in reconfigurable networks e.g., peer-to-peer and wireless mesh networks. For such networks under repeated attack by an omniscient adversary, we propose a fully distributed algorithm, Xheal, that maintains good expansion and spectral properties of the network, while keeping the network connected. Moreover, Xheal does this while allowing only low stretch and degree increase per node. The algorithm heals global properties like expansion and stretch while only doing local changes and using only local information. We also provide bounds on the second smallest eigenvalue of the Laplacian which captures key properties such as mixing time, conductance, congestion in routing etc. Xheal has low amortized latency and bandwidth requirements. Our work improves over the self-healing algorithms Forgiving tree [PODC 2008] and Forgiving graph [PODC 2009] in that we are able to give guarantees on degree and stretch, while at the same time preserving the expansion and spectral properties of the network.     

Hierarchical hybrid control systems: a lattice theoreticformulation

The notion of dynamical consistency is extended to hybrid systems so as to define the set of dynamically consistent hybrid partition machines associated with a continuous system S. Following the formulation of the notions of between-block and in-block controllable hybrid partition machines, the lattice HIBC(S) of hybrid in-block controllable partition machines is defined and investigated. Based on these constructions, the definition and properties of hierarchical-hybrid control systems are presented together with an example     

Exemplar queries: a new way of searching

Modern search engines employ advanced techniques that go beyond the structures that strictly satisfy the query conditions in an effort to better capture the user intentions. In this work, we introduce a novel query paradigm that considers a user query as an example of the data in which the user is interested. We call these queries exemplar queries. We provide a formal specification of their semantics and show that they are fundamentally different from notions like queries by example, approximate queries and related queries. We provide an implementation of these semantics for knowledge graphs and present an exact solution with a number of optimizations that improve performance without compromising the result quality. We study two different congruence relations, isomorphism and strong simulation, for identifying the answers to an exemplar query. We also provide an approximate solution that prunes the search space and achieves considerably better time performance with minimal or no impact on effectiveness. The effectiveness and efficiency of these solutions with synthetic and real datasets are experimentally evaluated, and the importance of exemplar queries in practice is illustrated.     

Extremely localized interaction in a market model

The model of self-organized criticality (SOC) is a useful tool to understand the complexity of natural systems in the form of the artificial life and the artificial market. However, SOC remains the question what guarantees the criticality even though the natural systems seem to keep itself in the critical state. In this paper, we focus on the locality of interaction in zero-intelligence plus (ZIP) model. The extremely localized interaction changes the behavior of the ZIP model from equilibrium to intermittency. Although the original ZIP model falls into unstable with some noise, extremely localized interaction model archives robust intermittency against the noise parameter. Further, the statistical property of intermittent behavior shows the power-law nature.     

Adaptive virtual sensors using SNPER for the localized construction and elastic net regularization in nonlinear processes

Traditional data-driven virtual sensors were constructed upon the macro-perspective of the manifold structure using generalized models. They did not focus on the local relationships among the data samples through micro-perspective of manifold proximity indicating the local relationships among the data samples. In the case with the quantity of data points fewer than the dimensions of the data variables, the virtual sensor model is likely to be unstable, ill-conditioned, and computationally expensive. And the real-world data often vary with time. It is difficult, in the long term, to sustain good performance by a single fixed model. This paper addresses the aforementioned issues by proposing three algorithms (NPER, SNPER, and LW-SNPER) to successively improve the virtual sensor modeling performance for nonlinear, high-dimensional and time-varying processes. It is shown through the numerical cases and a real semiconductor process that the proposed algorithms perform better than the other regular regression algorithms.