检索结果-内蒙古大学图书馆

JOURNAL OF THE ACM 1995年第6期42卷 1169-1193页

作者： Boyar, J Brassard, G Peralta, R UNIV MONTREAL DEPT IRO MONTREAL PQ H3C 3J7 CANADA UNIV WISCONSIN DEPT ELECT ENGN & COMP SCI MILWAUKEE WI 53201 USA

We improve on the communication complexity of zero-knowledge proof systems. Let C be a Boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiability of C require the use of Omega(kn) bit commitments in order to achieve a probability of undetected cheating below 2(-k). In the case k = n, the communication complexity of these protocols is therefore Omega(n(2)) bit commitments. In this paper, we present a zero-knowledge proof system for achieving the same goal with only O(n(1+epsilon n) + k root n(1+epsilon n)) bit commitments, where epsilon(n) goes to zero as n goes to infinity. In the case k = n, this is O(n root n(1+epsilon n)). Moreover, only O(k) commitments need ever be opened, which is interesting if it is substantially less expensive to commit to a bit than to open a commitment.

关键词： bit commitment circuit evaluation communication complexity cryptography interactive proofs matrix multiplication non-averaging sets probabilistic algorithms proof systems randomness zero knowledge

来源：评论

学校读者我要写书评

暂无评论

Model-based hand tracking using a hierarchical Bayesian filter

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2006年第9期28卷 1372-1384页

作者： Stenger, Bjorn Thayananthan, Arasanathan Torr, Philip H. S. Cipolla, Roberto Toshiba Co Ltd R&D Ctr Kawasaki Kanagawa 2128582 Japan Univ Cambridge Dept Engn Cambridge CB2 1PZ England Oxford Brookes Univ Dept Comp Oxford OX33 1HX England

This paper sets out a tracking framework, which is applied to the recovery of three-dimensional hand motion from an image sequence. The method handles the issues of initialization, tracking, and recovery in a unified way. In a single input image with no prior information of the hand pose, the algorithm is equivalent to a hierarchical detection scheme, where unlikely pose candidates are rapidly discarded. In image sequences, a dynamic model is used to guide the search and approximate the optimal filtering equations. A dynamic model is given by transition probabilities between regions in parameter space and is learned from training data obtained by capturing articulated motion. The algorithm is evaluated on a number of image sequences, which include hand motion with self-occlusion in front of a cluttered background.

关键词： probabilistic algorithms video analysis tracking

来源：评论

学校读者我要写书评

暂无评论

Hill-climbing to Pasch valleys

引用

JOURNAL OF COMBINATORIAL DESIGNS 2007年第5期15卷 405-419页

作者： Heap, Danny Danzigerl, Peter Mendelsohn, Eric Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada Ryerson Univ Dept Math Toronto ON M5B 2K3 Canada Univ Toronto Dept Math Toronto ON M5S 3G4 Canada

Exhaustive enumeration of Steiner Triple Systems is not feasible, due to the combinatorial explosion of instances. The next-best hope is to quickly find a sample that is representative of isomorphism classes. Stinson's Hill-Climbing algorithm [20] is widely used to produce random Steiner Triple Systems, and certainly finds a sample of systems quickly, but the sample is not uniformly distributed with respect to the isomorphism classes of STS with upsilon <= 19, and, in particular, we find that isomorphism classes with a large number of Pasch configurations are under-represented. No analysis of the non-uniformity of the distribution with respect to isomorphism classes or the intractability of obtaining a representative sample for upsilon > 19 is known. We also exhibit a modification to hill-climbing that makes the sample if finds closer to the uniform distribution over isomorphism classes in return for a modest increase in running time. (c) 2007 Wiley Periodicals, Inc.

关键词： hill climbing triple system Pasch configuration probabilistic algorithms combinatorial designs

来源：评论

学校读者我要写书评

暂无评论

PresQ: Discovery of Multidimensional Equally-Distributed Dependencies via Quasi-Cliques on Hypergraphs

引用

IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTING 2024年第1期12卷 224-239页

作者： Alvarez-Ayllon, Alejandro Palomo-Duarte, Manuel Dodero, Juan-Manuel Univ Geneva Dept Astron CH-1290 Versoix Switzerland Univ Cadiz Dept Comp Sci & Engn Puerto Real 11519 Spain

Cross-matching data stored on separate files is an everyday activity in the scientific domain. However, sometimes the relation between attributes may not be obvious. The discovery of foreign keys on relational databases is a similar problem. Thus techniques devised for this problem can be adapted. Nonetheless, when the data is numeric and subject to uncertainty, this adaptation is not trivial. This article first introduces the concept of Equally-Distributed Dependencies, which is similar to the Inclusion Dependencies from the relational domain. We describe a correspondence in order to bridge existing ideas. We then propose PresQ: a new algorithm based on the search of maximal quasi-cliques on hyper-graphs to make it more robust to the nature of uncertain numerical data. This algorithm has been tested on seven public datasets, showing promising results both in its capacity to find multidimensional equally-distributed sets of attributes and in run-time.

关键词： Data mapping probabilistic algorithms hypergraphs inclusion dependencies equally-distributed dependencies quasi-clique

来源：评论

学校读者我要写书评

暂无评论

Analyzing and capturing articulated hand motion in image sequences

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2005年第12期27卷 1910-1922页

作者： Wu, Y Lin, J Huang, TS Northwestern Univ Dept Elect & Comp Engn Evanston IL 60208 USA Proximex Corp Cupertino CA 95014 USA Univ Illinois Beckman Inst Urbana IL 61801 USA Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA

Capturing the human hand motion from video involves the estimation of the rigid global hand pose as well as the nonrigid finger articulation. The complexity induced by the high degrees of freedom of the articulated hand challenges many visual tracking techniques. For example, the particle filtering technique is plagued by the demanding requirement of a huge number of particles and the phenomenon of particle degeneracy. This paper presents a novel approach to tracking the articulated hand in video by learning and integrating natural hand motion priors. To cope with the finger articulation, this paper proposes a powerful sequential Monte Carlo tracking algorithm based on importance sampling techniques, where the importance function is based on an initial manifold model of the articulation configuration space learned from motion-captured data. In addition, this paper presents a divide-and-conquer strategy that decouples the hand poses and finger articulations and integrates them in an iterative framework to reduce the complexity of the problem. Our experiments show that this approach is effective and efficient for tracking the articulated hand. This approach can be extended to track other articulated targets.

关键词： motion tracking video analysis statistical computing probabilistic algorithms face and gesture recognition

来源：评论

学校读者我要写书评

暂无评论

A Stochastic Computational Approach for Accurate and Efficient Reliability Evaluation

引用

IEEE TRANSACTIONS ON COMPUTERS 2014年第6期63卷 1336-1350页

作者： Han, Jie Chen, Hao Liang, Jinghang Zhu, Peican Yang, Zhixi Lombardi, Fabrizio Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G2V4 Canada Northeastern Univ Dept Elect & Comp Engn Boston MA 02115 USA

Reliability is fast becoming a major concern due to the nanometric scaling of CMOS technology. Accurate analytical approaches for the reliability evaluation of logic circuits, however, have a computational complexity that generally increases exponentially with circuit size. This makes intractable the reliability analysis of large circuits. This paper initially presents novel computational models based on stochastic computation;using these stochastic computational models (SCMs), a simulation-based analytical approach is then proposed for the reliability evaluation of logic circuits. In this approach, signal probabilities are encoded in the statistics of random binary bit streams and non-Bernoulli sequences of random permutations of binary bits are used for initial input and gate error probabilities. By leveraging the bit-wise dependencies of random binary streams, the proposed approach takes into account signal correlations and evaluates the joint reliability of multiple outputs. Therefore, it accurately determines the reliability of a circuit;its precision is only limited by the random fluctuations inherent in the stochastic sequences. Based on both simulation and analysis, the SCM approach takes advantages of ease in implementation and accuracy in evaluation. The use of non-Bernoulli sequences as initial inputs further increases the evaluation efficiency and accuracy compared to the conventional use of Bernoulli sequences, so the proposed stochastic approach is scalable for analyzing large circuits. It can further account for various fault models as well as calculating the soft error rate (SER). These results are supported by extensive simulations and detailed comparison with existing approaches.

关键词： Reliability testing and fault-tolerance reliability and testing error-checking fault injection probabilistic algorithms random number generation

来源：评论

学校读者我要写书评

暂无评论

Managing Evolving Uncertainty in Trajectory Databases

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2014年第7期26卷 1692-1705页

作者： Jeung, Hoyoung Lu, Hua Sathe, Saket Yiu, Man Lung SAP Res Brisbane Qld 4105 Australia Aalborg Univ Dept Comp Sci DK-9220 Aalborg Denmark Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland Hong Kong Polytech Univ Dept Comp Hong Kong Hong Kong Peoples R China

Modern positioning technologies enable collecting trajectories from moving objects across different locations over time, typically containing time-varying measurement errors of positioning systems. Unfortunately, current models on uncertain trajectories are incapable of capturing dynamically changing uncertainty in trajectory data, and lack the support of recent progress made in improving localization accuracy. In order to tackle these problems, we address three important issues centric to uncertain trajectory management. First, we propose a flexible trajectory modeling approach that takes into account model-inferred actual positions, time-varying uncertainty, and nondeterministic uncertainty ranges. Second, we develop three estimators that effectively infer evolving densities of trajectory data. Last, we present an efficient mechanism to evaluate probabilistic range queries on those evolving-density trajectories. Empirical results on two large-scale real datasets demonstrate the quality and efficiency of our approach.

关键词： Query processing spatial databases and GIS probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

Informed Adaptive Sensing

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2024年第5期46卷 3230-3241页

作者： Morssy, Amr Frean, Marcus R. Teal, Paul D. Victoria Univ Wellington Sch Comp Sci & Engn Fac Engn Wellington 6012 New Zealand

For many inverse problems, the data on which the solution is based is acquired sequentially. We present an approach to the solution of such inverse problems where a sensor can be directed (or otherwise reconfigured on the fly) to acquire a particular measurement. An example problem is magnetic resonance image reconstruction. We use an estimate of mutual information derived from an empirical conditional distribution provided by a generative model to guide our measurement acquisition given measurements acquired so far. The conditionally generated data is a set of samples which are representative of the plausible solutions that satisfy the acquired measurements. We present experiments on toy and real world data sets. We focus on image data but we demonstrate that the method is applicable to a broader class of problems. We also show how a learned model such as a deep neural network can be leveraged to allow generalisation to unseen data. Our informed adaptive sensing method outperforms random sampling, variance based sampling, sparsity based methods, and compressed sensing.

关键词： Inverse problems Entropy Adaptation models Mutual information Deep learning Training Numerical models Experimental design inverse problems iterative solution techniques machine learning medical imaging phase retrieval probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

RANDOMIZATION FOR ROBOT TASKS - USING DYNAMIC-PROGRAMMING IN THE SPACE OF KNOWLEDGE STATES

引用

ALGORITHMICA 1993年第2-4期10卷 248-291页

作者： ERDMANN, M CARNEGIE MELLON UNIV INST ROBOT PITTSBURGH PA 15213 USA

This paper explores the use of randomization as a primitive action in the solution of robot tasks. An example of randomization is the strategy of shaking a bin containing a part in order to orient the part in a desired stable state with some high probability. Further examples include tapping, vibrating, twirling, and random search. For instance, it is sometimes beneficial for a system to execute random motions purposefully when the precise motions required to perform an operation are unknown, as when they lie below the available sensor resolution. The purpose of this paper is to provide a theoretical framework for the planning and execution of randomized strategies for robot tasks. This framework is built on the standard backchaining approach of dynamic programming. Specifically, a randomizing planner backchains from the goal in a state space whose states describe the knowledge available to the system at run-time. By choosing random actions in a principled manner at run-time, a system can sometimes obtain a probabilistic strategy for accomplishing a task even when no guaranteed strategy exists for accomplishing that task. In other cases, the system may be able to obtain a speedup over an existing guaranteed strategy. The main result of this paper consists of two examples. One example shows that randomization can sometimes speed up task completion from exponential time to polynomial time. The other example shows that such a speedup is not always possible.

关键词： UNCERTAINTY ROBOTICS RANDOMIZATION probabilistic algorithms AUTOMATIC PROGRAMMING PLANNING WITH UNCERTAINTY

来源：评论

学校读者我要写书评

暂无评论

A Hybrid Smartphone Indoor Positioning Solution for Mobile LBS

引用

SENSORS 2012年第12期12卷 17208-17233页

作者： Liu, Jingbin Chen, Ruizhi Pei, Ling Guinness, Robert Kuusniemi, Heidi Finnish Geodet Inst Dept Nav & Positioning Masala 02431 Finland

Smartphone positioning is an enabling technology used to create new business in the navigation and mobile location-based services (LBS) industries. This paper presents a smartphone indoor positioning engine named HIPE that can be easily integrated with mobile LBS. HIPE is a hybrid solution that fuses measurements of smartphone sensors with wireless signals. The smartphone sensors are used to measure the user's motion dynamics information (MDI), which represent the spatial correlation of various locations. Two algorithms based on hidden Markov model (HMM) problems, the grid-based filter and the Viterbi algorithm, are used in this paper as the central processor for data fusion to resolve the position estimates, and these algorithms are applicable for different applications, e.g., real-time navigation and location tracking, respectively. HIPE is more widely applicable for various motion scenarios than solutions proposed in previous studies because it uses no deterministic motion models, which have been commonly used in previous works. The experimental results showed that HIPE can provide adequate positioning accuracy and robustness for different scenarios of MDI combinations. HIPE is a cost-efficient solution, and it can work flexibly with different smartphone platforms, which may have different types of sensors available for the measurement of MDI data. The reliability of the positioning solution was found to increase with increasing precision of the MDI data.

关键词： smartphone positioning mobile LBS probabilistic algorithms sensor fusion ubiquitous computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：