贝叶斯网络精确推理算法的研究

贝叶斯网络是以概率理论为基础的不确定知识表示模型,贝叶斯网络推理的目的是得到随机变量的概率分布。目前,最流行的推理算法是联合树算法,它的主要思想是将贝叶斯网络转化为一棵无向树,在无向树上完成消息传递过程,求出原贝叶斯网络中任意随机变量的概率分布。为了降低算法的计算时空复杂度,对算法进行了不断的改进,为贝叶斯网络推理算法的进一步研究提供了条件。     

离散动态贝叶斯网络推理的编程计算算法

离散动态贝叶斯网络是对时间序列进行建模和推理的重要工具,具有广泛的建模应用价值,但是其推理算法还有待进一步完善。针对构离散动态贝叶斯网络的推理算法难以理解、编程计算难、推理速度慢的问题,给出了实现离散动态贝叶斯推理算法的数据结构,推导了进行计算机编程计算的推理算法和编程步骤,并通过实例进行了算理验证。     

一种自适应模型构造的层次决策图贝叶斯优化算法

描述和分析零星模型构造(SMB)方法中固定模型构造周期参数对层次决策图贝叶斯优化算法性能的影响,提出了一种基于自适应模型构造(AMB)的层次决策图贝叶斯优化算法,通过计算群体平均信息熵密度而确定相邻两代群体所对应网络模型的相似度,仅当相似度小于给定阈值时自适应重构贝叶斯网络模型,从而在保证贝叶斯网络模型精确性的前提下减少贝叶斯网络模型的构造次数,进而降低算法计算复杂度,加速收敛.实验结果表明,AMB方法有效可行.     

基于贝叶斯网络的系统可靠性分析平台

贝叶斯网络是一种进行不确定性推理和分析的有效工具,针对系统可靠性分析问题,建立了一种基于贝叶斯网络的系统可靠性分析平台。所建立的分析平台将贝叶斯网络应用于系统可靠性分析中,把系统各组部件抽象成节点,从而构成贝叶斯网络模型;通过推理和分析算法找到影响系统可靠性的薄弱环节;通过计算某个部件发生变化时对整个系统的影响,得出各个节点的重要度,给出合理的优化方案,提升系统可靠性。通过对平视显示器实例进行分析,计算了每个组部件对整个系统的影响程度,证明该分析平台在利用贝叶斯网络对系统可靠性分析上的可行性。     

基于贝叶斯网络的健壮社团检测

健壮社团是复杂网络社团结构中稳定部分,健壮社团发现是非常困难的;提出了一种基于贝叶斯网络推理的健壮社团发现算法,把健壮社团发现问题当做推理问题,构造一个贝叶斯网络,根据结点的度来设置贝叶斯网络相关参数,然后将某些内部联系特别紧密的网络结点设为证据结点,在贝叶斯网络中进行信度传播,得到在已知证据的情况下其余结点属于该健壮社团的概率,最后得到复杂网络中的所有健壮社团;对足球俱乐部网络(115个结点)和随机网络(128个结点)的测试结果表明所提方法能有效地检测出复杂网络中存在的健壮社团,具有较好的应用价值。     

网页自动分类不确定性问题的贝叶斯网络解法

针对网页自动分类中存在的类边界模糊、语料不均匀等引起的分类不确定性问题,提出了贝叶斯网络自动分类融合模型和融合算法,该模型和算法基于网页上多种信息进行融合,并采用不同的与处理方法分别对多种信息进行处理,将处理后的信息输入到贝叶斯网络融合中心进行融合推理,得到最终的分类结果。同时,为了降低贝叶斯网络推理时间复杂度,提出了改进的贝叶斯网络图推理算法。实验结果表明,改进后的融合模型和融合算法能有效解决网页自动分类中的不确定性问题,并能提高网页自动分类的准确率和查全率。     

基于贝叶斯网络的多传感器目标识别算法研究

基于贝叶斯网络能够组合多种证据进行不确定性表达和推理的特点,提出以贝叶斯网络为基本结构的目标融合识别模型.通过详细分析空中目标识别的推理规则,建立了空中目标识别的贝叶斯网络拓扑结构.首先对各传感器的数据分别进行融合,然后应用贝叶斯网络推理算法对多种传感器融合结果进行融合计算,最后根据假定变量各状态的概率取值来判断目标平台类型.仿真结果证明了该方法直观、形象,计算速度快,降低了实用的复杂度,提高了目标识别的可靠性.     

动态贝叶斯网络一种自适应的局部抽样粒子滤波算法*

针对传统自适应粒子滤波（APF）对于动态贝叶斯网络推理中高维的问题,提出动态贝叶斯网络一种自适应的局部抽样粒子滤波算法(LSAPF)。LSAPF算法将BK算法分团的思想引入到粒子抽样中,利用策略相关性和局部模型的弱交互性为指导对动态贝叶斯网络进行分割,以降低抽样规模和抽样的状态空间;进而对局部模型用自适应粒子滤波算法进行近似推理,并以粒子的因式积形式近似系统的状态信度。实验结果表明,该算法能很好地兼顾推理精度和推理时间,其性能优于普通PF算法;与APF算法相比,在不增加推理误差的情况下推理时间也有较大的提高。     

基于贝叶斯网络的博弈融合态势评估方法

贝叶斯网络作为一种知识表示和进行概率推理的方法,在不确定性推理决策问题中得到了广泛的应用.针对态势评估系统需要对大量不确定性知识进行处理的情况,利用贝叶斯网络技术,结合博弈论的思想,提出了一种博弈融合态势评估的新算法,并以一个实例来说明该算法计算过程的可行性,指出了贝叶斯网络在实际应用中存在的问题.     

基于结构分析的局部Gibbs抽样自动推理算法

提出一种基于结构分析的局部Gibbs抽样的贝叶斯网络推理算法(S-LGSI).S-LGSI算法基于联合树算法的概率图模型分析思想,对贝叶斯网络进行精确分解,然后根据查询结点和证据结点生成具有强相关性的局部网络模型,进而对局部网络模型进行Gibbs抽样推理.与当前基于抽样的其它近似推理算法相比,该算法降低推理的计算维数.同时,由于局部抽样模型包含了与查询结点相关的重要信息,因此该算法保证局部抽样推理的精度.算法分析和在Alarm网的实验结果表明,S-LGSI算法较显著降低时间复杂度,同时也提高推理精度.S-LGSI算法应用于上海证券交易所股票网络的推理结果与实际情况基本一致,表现出较强的实用性.     

Dynamic Programming via Static Incrementalization

Dynamic programming is an important algorithm design technique. It is used for problems whose solutions involve recursively solving subproblems that share subsubproblems. While a straightforward recursive program solves common subsubproblems repeatedly, a dynamic programming algorithm solves every subsubproblem just once, saves the result, and reuses it when the subsubproblem is encountered again. This can reduce the time complexity from exponential to polynomial. This paper describes a systematic method for transforming programs written as straightforward recursions into programs that use dynamic programming. The method extends the original program to cache all possibly computed values, incrementalizes the extended program with respect to an input increment to use and maintain all cached results, prunes out cached results that are not used in the incremental computation, and uses the resulting incremental program to form an optimized new program. Incrementalization statically exploits semantics of both control structures and data structures and maintains as invariants equalities characterizing cached results. It provides the basis of a general method for achieving drastic program speedups. Compared with previous methods that perform memoization or tabulation, the method based on incrementalization is more powerful and systematic. It has been implemented in a prototype system CACHET and applied to numerous problems and succeeded on all of them.     

An Effective Cache Replacement Algorithm in Transcoding-Enabled Proxies

In this paper, we address the problem of cache replacement for transcoding proxy caching. Transcoding proxy is a proxy that has the functionality of transcoding a multimedia object into an appropriate format or resolution for each client. We first propose an effective cache replacement algorithm for transcoding proxy. In general, when a new object is to be cached, cache replacement algorithms evict some of the cached objects with the least profit to accommodate the new object. Our algorithm takes into account of the inter-relationships among different versions of the same multimedia object, and selects the versions to replace according to their aggregate profit which usually differs from simple summation of their individual profits as assumed in the existing algorithms. It also considers cache consistency, which is not considered in the existing algorithms. We then present a complexity analysis to show the efficiency of our algorithm. Finally, we give extensive simulation results to compare the performance of our algorithm with some existing algorithms. The results show that our algorithm outperforms others in terms of various performance metrics.     

Efficient segment-based video transcoding proxy for mobile multimedia services

To support various bandwidth requirements for mobile multimedia services for future heterogeneous mobile environments, such as portable notebooks, personal digital assistants (PDAs), and 3G cellular phones, a transcoding video proxy is usually necessary to provide mobile clients with adapted video streams by not only transcoding videos to meet different needs on demand, but also caching them for later use. Traditional proxy technology is not applicable to a video proxy because it is less cost-effective to cache the complete videos to fit all kinds of clients in the proxy. Since transcoded video objects have inheritance dependency between different bit-rate versions, we can use this property to amortize the retransmission overhead from transcoding other objects cached in the proxy. In this paper, we propose the object relation graph (ORG) to manage the static relationships between video versions and an efficient replacement algorithm to dynamically manage video segments cached in the proxy. Specifically, we formulate a transcoding time constrained profit function to evaluate the profit from caching each version of an object. The profit function considers not only the sum of the costs of caching individual versions of an object, but also the transcoding relationship among these versions. In addition, an effective data structure, cached object relation tree (CORT), is designed to facilitate the management of multiple versions of different objects cached in the transcoding proxy. Experimental results show that the proposed algorithm outperforms companion schemes in terms of the byte-hit ratios and the startup latency.     

An energy efficient re-access scheme for data caching in data broadcast of a mobile computing environment

Data caching is used to improve the response time and the power consumption of a mobile client in a mobile computing environment. To enhance the performance of data caching, one needs to improve the hit ratio and to reduce the cost in processing a cache miss. In a mobile computing environment, a cached data item of a mobile client needs to remain up-to-date with respect to its corresponding data item in the server. A cached data item which is out of date is called a cached invalidated data item. Accessing a cached invalidated data item can be regarded as processing a cache miss. To access a cached invalidated data item, a mobile client needs to download the new content of the data item from the broadcast channel. This operation is called a re-access operation in this paper. Re-accessing a cached invalidated data item incurs large tuning time overhead. In this paper, we propose a re-access scheme that reduces this overhead by allowing a mobile client to access a cached invalidated data item from the broadcast channel without accessing indices. We analyze the performance of the proposed scheme and validate the analysis through experiments. The experiments showed that the proposed scheme significantly reduces the tuning time of a mobile client. Furthermore, the proposed scheme is robust in the sense that it allows changes on the broadcast structure in data broadcasting.     

基于漏斗的实时VBR视频最短路径平滑算法①

针对实时VBR视频流式传输的在线平滑优化问题,提出一种基于漏斗的最短路径平滑算法——SPSF。SPSF利用滑动窗口对实时VBR视频进行分段处理,顺序读取和缓存每帧视频数据至窗口,并基于漏斗原理求解窗口内数据的最短路径。数据填满窗口后根据求得的最短路径进行传输,同时根据路径特征推进窗口滑动进行下一段数据的平滑处理及传输,以此类推完成整个视频平滑传输。实验结果表明。与传统的在线平滑算法相比,SPSF具有更优的传输比特率峰值、传输比特率谷值、及传输比特率方差;与传统的最短路径算法相比,SPSF具有更快的最短路径求解速度,提高了视频传输的实时性。     

Frame Selection for Dynamic Caching Adjustment in Video Proxy Servers

By caching video data, a video proxy server close to the clients can be used to assist video delivery and alleviate the load of video servers. We assume a video can be partially cached and a certain number of video frames are stored in the proxy server. In our setting, the proxy server is allowed to cache the passing data from the video server. A video provides several options (levels) in terms of bandwidth requirement over the server-proxy path. For each video, the proxy server decides to cache a smaller amount of data at a lower level or to accumulate more data to reach a higher level. The proxy server can dynamically adjust the cached video data by choosing an appropriate level based on the network condition or the popularity of the video. We propose a frame selection scheme, Dynamic Chunk Algorithm, to determine which frames are to be cached in the proxy server for the dynamic caching adjustment scenario. The algorithm guarantees the rate constraint over the server-proxy path to be satisfied for each level. This approach also maintains the set of cached frames at a higher level as a superset of the cached frames at a lower level. Hence, it enforces the proxy server to simply cache more data without dropping frames when it intends to reduce network bandwidth consumption for a video and vice versa.     

Proxy cache algorithms: design, implementation, and performance

Caching at proxy servers is one of the ways to reduce the response time perceived by World Wide Web users. Cache replacement algorithms play a central role in the response time reduction by selecting a subset of documents for caching, so that a given performance metric is maximized. At the same time, the cache must take extra steps to guarantee some form of consistency of the cached documents. Cache consistency algorithms enforce appropriate guarantees about the staleness of the cached documents. We describe a unified cache maintenance algorithm, LNC-R-WS-U, which integrates both cache replacement and consistency algorithms. The LNC-R-WS-U algorithm evicts documents from the cache based on the delay to fetch each document into the cache. Consequently, the documents that took a long time to fetch are preferentially kept in the cache. The LNC-R-W3-U algorithm also considers in the eviction consideration the validation rate of each document, as provided by the cache consistency component of LNC-R-WS-U. Consequently, documents that are infrequently updated and thus seldom require validations are preferentially retained in the cache. We describe the implementation of LNC-R-W3-U and its integration with the Apache 1.2.6 code base. Finally, we present a trace-driven experimental study of LNC-R-W3-U performance and its comparison with other previously published algorithms for cache maintenance     

内容分发网络中基于相关内容吸引的缓存算法

内容分发网络中基于内容名的缓存算法会导致路由表规模随网络增长而膨胀,将严重影响网络路由效率和性能。针对该问题,提出一种基于相关内容吸引的节点缓存算法。利用本地缓存算法,通过节点已缓存内容对其他内容的吸引作用吸引主要特征内容,排斥具有次要特征内容,将缓存中不同特征内容的数量差异进行放大,使缓存内容表现出明显稳定的内容特征。同时设计相关内容生存时间相互增强的缓存策略,以减少路由通告信息量,提高内容分发网络的路由能力。实验结果表明,该算法在有效解决路由问题的同时,能增强缓存内容稳定性,提高路由可信度。     

基于漏斗的实时VBR视频最短路径平滑算法①

针对实时VBR视频流式传输的在线平滑优化问题,提出一种基于漏斗的最短路径平滑算法——SPSF。SPSF利用滑动窗口对实时VBR视频进行分段处理,顺序读取和缓存每帧视频数据至窗口,并基于漏斗原理求解窗口内数据的最短路径。数据填满窗口后根据求得的最短路径进行传输,同时根据路径特征推进窗口滑动进行下一段数据的平滑处理及传输,以此类推完成整个视频平滑传输。实验结果表明,与传统的在线平滑算法相比,SPSF具有更优的传输比特率峰值、传输比特率谷值、及传输比特率方差;与传统的最短路径算法相比,SPSF具有更快的最短路径     

低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法．通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1．1033^n),参数化的3度图点覆盖问题的解决时间为O(kn 1．2174^k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1．1033^n)的解．以上3结果均打破原有最佳下界。