因果模型中因果效应的可识别性研究

对有向非循环图中的因果关系进行探讨,提出了相应的虚拟事实模型,并利用条件独立关系作为辅助信息对一种较为简单的虚拟事实模型的可识别性进行了研究.将可忽略假设推广为可替换性假设,并且得到：在可替换性假设之下,因果效应具有可识别性,即有可能从观察数据直接计算因果效应.     

借助优势比信息识别不可忽略缺失数据的模型参数

由不可忽略缺失机制引起的缺失数据,常使得模型变得不可识别。对于那些不可识别的模型,可以通过添加协变量和借助其他来源的外部数据来达到识别的目的。本文探讨不可忽略缺失机制下,利用外部获得的优势比估计,来达到识别联合概率的方法。     

结构VAR的有向非循环图模型

研究用图模型方法辨识结构向量自回归(VAR)模型,图中的结点表示不同时刻的随机变量,结点间的边表示其所表示的随机变量之间存在的因果相依关系.针对建立有向非循环图的问题,提出了一种基于回归分析的判断方法,用回归方程的回归平方和之差作为统计量,确定当前变量之间相依关系的方向.与R ea le的逐一判别法和A lessio的图搜索方法相比,文中提出的基于统计分析的方法简单易行,且可获得唯一的当前变量有向非循环图.最后以两组模拟序列为例,验证了所提出的方法是可行且有效的.     

图模型及其在统计建模中的应用

图模型是近年来兴起的一个新的统计研究方向,主要借助拓扑图的直观形式对多维概率分布进行统计推断和因果分析。本文对图模型的基本概念、原理、建模及应用进行了简单介绍。     

基于VAR和DAG的中国经济增长实证研究

本文利用近年来新发展的DAG方法对我国的GDP、投资、消费和出口的因果关系进行研究.与以前的研究方法相比较,DAG方法可为宏观经济变量的结构VAR模型的过度识别提供限制,同时能给出经济变量的同期和动态因果关系.实证研究表明,投资和消费既是我国GDP增长的同期原因,又是经济增长的短期和长期原因,而且实证结论不支持我国的出口导向型经济增长假设.     

一类五次系统的奇点量和可积性条件

本文采用代数运算方法研究了一类五次系统的原点奇点量和可积性条件,并给出了该系统的15个基本Lie-不变量。     

一类特殊五次系统的奇点量与可积性条件的研究

本文采用代数运算方法研究了一类五次系统的中心一焦点判定问题,给出了系统的13个基本如不变量,得到了直接用系统的系数表示的奇点量公式与可积性条件。     

不等式约束下线性模型中线性估计的可容许性

研究了线性模型在不等式约束条件下齐次和非齐次线性估计的可容许性,刻画了两者之间的关系,得到了不等式约束条件下非齐次线性估计可容许性的充要条件．     

平衡损失下一般Gauss—Markoff模型中回归系数的非齐次线性可容许估计

提出了适用于—般Gauss-Markoff模型的平衡损失函数,并在该平衡损失下,研究了模型中回归系数的非齐次线性估计在非齐次线性估计类中的可容许性,得到了充要条件．     

一类具有1:-4共振奇点的复三次Lotka-Volterra系统的可积性条件

对于一类具有1:-4共振奇点的复三次Lotka-Volterra系统,通过前12阶广义奇点量的计算,给出系统可积的充分条件.这些条件通过构造积分因子或形式积分得以证明.     

Directed acyclic subsequence graph—Overview

The subsequence matching problem is to decide, for given strings S and T, whether S is a subsequence of T. The string S is called the pattern and the string T the text. We consider the case of multiple texts and show how to solve the subsequence matching problem in time linear in the length of the pattern. For this purpose we build an automaton that accepts all subsequences of given texts. This automaton is called the Directed Acyclic Subsequence Graph (DASG). We prove an upper bound for its number of states. Furthermore, we consider a modification of the subsequence matching problem: given a string S and a finite language L, we are to decide whether S is a subsequence of any string in L. We suppose that a finite automaton accepting L is given and present an algorithm for building the DASG for language L. We also mention applications of the DASG to some problems related to subsequences.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

Parseval wavelets on hierarchical graphs

Wavelets on graphs have been studied for the past few years, and in particular, several approaches have been proposed to design wavelet transforms on hierarchical graphs. Although such methods are computationally efficient and easy to implement, their frames are highly restricted. In this paper, we propose a general framework for the design of wavelet transforms on hierarchical graphs. Our design is guaranteed to be a Parseval tight frame, which preserves the $l_2$ norm of any input signals. To demonstrate the potential usefulness of our approach, we perform several experiments, in which we learn a wavelet frame based on our framework, and show, in inpainting experiments, that it performs better than a Haar-like hierarchical wavelet transform and a learned treelet. We also show with category theory that the algebraic properties of the proposed transform have a strong relationship with those of the hierarchical graph that represents the structure of the given data.     

Decomposition of search for -structures in DAGs

We show that the problem of searching for v-structures in a directed acyclic graph can be decomposed into searches in its decomposed subgraphs. This result simplifies the search for v-structures and the recovery of local causal relationships.     

Domain extender for collision resistant hash functions: Improving upon Merkle-Damgård iteration

We study the problem of securely extending the domain of a collision resistant compression function. A new construction based on directed acyclic graphs is described. This generalizes the usual iterated hashing constructions. Our main contribution is to introduce a new technique for hashing arbitrary length strings. Combined with DAG-based hashing, this technique yields a new hashing algorithm. The amount of padding and the number of invocations of the compression function required by the new algorithm is smaller than the general Merkle-Damgård algorithm.     

不含相邻三角形的平面图的无圈边着色

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a(G).In this paper we prove that χ ’ a(G) ≤(G) + 5 for planar graphs G without adjacent triangles.