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

graph-based analysis of human transfer learning using a game testbed

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2007年第11期19卷 1465-1478页

作者： Cook, Diane J. Holder, Lawrence B. Youngblood, G. Michael Washington State Univ Sch Elect Engn & Comp Sci Pullman WA 99164 USA Univ N Carolina Dept Comp Sci Charlotte NC 28223 USA

The ability to transfer knowledge learned in one environment in order to improve performance in a different environment is one of the hallmarks of human intelligence. Insights into human transfer learning help us to design computer-based agents that can better adapt to new environments without the need for substantial reprogramming. In this paper, we study the transfer of knowledge by humans playing various scenarios in a graphically realistic urban setting that are specifically designed to test various levels of transfer. We determine the amount and type of transfer that is being performed based on the performance of trained and untrained human players. In addition, we use a graph-based relational learning algorithm to extract patterns from player graphs. These analyses reveal that indeed humans are transferring knowledge from one set of games to another and the amount and type of transfer varies according to player experience and scenario complexity. The results of this analysis help us understand the nature of human transfer in such environments and shed light on how we might endow computer-based agents with similar capabilities. The game simulator and human data collection also represent a significant testbed in which other AI capabilities can be tested and compared to human performance.

关键词： data mining graph algorithms transfer learning games

来源：评论

学校读者我要写书评

暂无评论

Testing versus estimation of graph properties

引用

SIAM JOURNAL ON COMPUTING 2007年第2期37卷 482-501页

作者： Fischer, Eldar Newman, Ilan Technion Israel Inst Technol Fac Comp Sci IL-32000 Haifa Israel Univ Haifa Dept Comp Sci IL-31905 Haifa Israel

Tolerant testing is an emerging topic in the field of property testing, which was defined in [M. Parnas, D. Ron, and R. Rubinfeld, J. Comput. System Sci., 72 ( 2006), pp. 1012-1042] and has recently become a very active topic of research. In the general setting, there exist properties that are testable but are not tolerantly testable [E. Fischer and L. Fortnow, Proceedings of the 20th IEEE Conference on Computational Complexity, 2005, pp. 135-140]. On the other hand, we show here that in the setting of the dense graph model, all testable properties are not only tolerantly testable (which was already implicitly proved in [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 ( 2000), pp. 451-476] and [O. Goldreich and L. Trevisan, Random Structures algorithms, 23 ( 2003), pp. 23-57]), but also admit a constant query size algorithm that estimates the distance from the property up to any fixed additive constant. In the course of the proof we develop a framework for extending Szemeredi's regularity lemma, both as a prerequisite for formulating what kind of information about the input graph will provide us with the correct estimation, and as the means for efficiently gathering this information. In particular, we construct a probabilistic algorithm that finds the parameters of a regular partition of an input graph using a constant number of queries, and an algorithm to find a regular partition of a graph using a TC0 circuit. This, in some ways, strengthens the results of [N. Alon, R. A. Duke, H. Lefmann, V. Rodl, and R. Yuster, J. algorithms, 16 ( 1994), pp. 80-109].

关键词： property testing graph algorithms approximation regularity lemma

来源：评论

学校读者我要写书评

暂无评论

Multiview stereo via volumetric graph-cuts and occlusion robust photo-consistency

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2007年第12期29卷 2241-2246页

作者： Vogiatzis, George Hernandez, Carlos Torr, Philip H. S. Cipolla, Roberto Toshiba Res Europe Ltd Cambridge CB4 0GZ England Oxford Brookes Univ Dept Comp Brookes Comp Vis Grp Oxford OX33 1HX England Univ Cambridge Dept Engn Cambridge CB2 1PZ England

This paper presents a volumetric formulation for the multiview stereo problem which is amenable to a computationally tractable global optimization using graph- cuts. Our approach is to seek the optimal partitioning of 3D space into two regions labeled as "object" and "empty" under a cost functional consisting of the following two terms: 1) A term that forces the boundary between the two regions to pass through photo- consistent locations and 2) a ballooning term that inflates the "object" region. To take account of the effect of occlusion on the first term, we use an occlusion robust photo- consistency metric based on Normalized Cross Correlation, which does not assume any geometric knowledge about the reconstructed object. The globally optimal 3D partitioning can be obtained as the minimum cut solution of a weighted graph.

关键词： 3D/stereo scene analysis shape graph algorithms global optimization

来源：评论

学校读者我要写书评

暂无评论

Approximate labeling via graph cuts based on linear programming

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2007年第8期29卷 1436-1453页

作者： Komodakis, Nikos Tziritas, Georgios Univ Crete Dept Comp Sci Iraklion 71409 Greece

A new framework is presented for both understanding and developing graph-cut-based combinatorial algorithms suitable for the approximate optimization of a very wide class of Markov Random Fields (MRFs) that are frequently encountered in computer vision. The proposed framework utilizes tools from the duality theory of linear programming in order to provide an alternative and more general view of state-of-the-art techniques like the alpha-expansion algorithm, which is included merely as a special case. Moreover, contrary to alpha-expansion, the derived algorithms generate solutions with guaranteed optimality properties for a much wider class of problems, for example, even for MRFs with nonmetric potentials. In addition, they are capable of providing per-instance suboptimality bounds in all occasions, including discrete MRFs with an arbitrary potential function. These bounds prove to be very tight in practice ( that is, very close to 1), which means that the resulting solutions are almost optimal. Our algorithms' effectiveness is demonstrated by presenting experimental results on a variety of low-level vision tasks, such as stereo matching, image restoration, image completion, and optical flow estimation, as well as on synthetic problems.

关键词： global optimization graph-theoretic methods linear programming Markov Random Fields pixel classification graph labeling graph algorithms early vision stereo motion image restoration

来源：评论

学校读者我要写书评

暂无评论

Toward An Intelligent Informative System to Determine Locations Paths in Doha City

Toward An Intelligent Informative System to Determine Locati...

引用

3rd International Conference on Information and Communication Technologies, vol.1

作者： Jihad M. Alja'am Shagra Ali Hassan Lulwa Burshaid Arwa Ali Suad Kaseem Department of Computer Science and Engineering Qatar University Doha Qatar

Tourists and new comers arriving to Doha city, the capital of Qatar, need always to know about specific locations (i.e., Tourist Sites, Hotels, Schools, Universities, Shopping Centers, Hospitals, Health Centres, Mosques, Sporting Clubs, etc.) and the possible routes leading to them. They are generally using static sources (i.e., Doha maps, brochures, diverse websites, etc) to get information about theses locations or they may ask others (i.e., residents, colleagues, passer-by). Even these information seem useful, they are however imprecise and will not fully satisfy the people requests and fulfill their incremental needs. An intelligent system helping these people to find quickly a location in Doha city is needed. Such a system will give detailed information about a specific location and determine the possible paths to reach it. People are always looking to save on time and resource (i.e., gas consumption, distances, time), therefore the system will be able to find the shortest routes leading to a specific location. In addition, it will help the potential users to plan a trip and visit a set of different locations within a limited period of time. Our system proposes routes leading to the user's destination and avoid passing thru locations with high accidents rates or heavy traffic. Doha city is divided into 71 different regions which are modeled by a weighted and connected graph. Each vertex of this graph represents a specific region, which, in turn, can be a sub-graph to allow internal search within the region. Dijkestra's algorithm is used to find the shortest paths between the regions. Information's about the regions are stored in a database for possible retrieval. The weight of the edge connecting two vertices represents the distance in KM between two regions.

关键词： Intelligent Systems Artificial Intelligence Transportation Optimization graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimizing graph algorithms for improved cache performance

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2004年第9期15卷 769-782页

作者： Park, JS Penner, M Prasanna, VK Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Univ So Calif Dept Elect Engn Los Angeles CA 90089 USA

In this paper, we develop algorithmic optimizations to improve the cache performance of four fundamental graph algorithms. We present a cache-oblivious implementation of the Floyd-Warshall Algorithm for the fundamental graph problem of all-pairs shortest paths by relaxing some dependencies in the iterative version. We show that this implementation achieves the lower bound on processor-memory traffic of Omega(N-3/rootC), where N and C are the problem size and cache size, respectively. Experimental results show that this cache-oblivious implementation shows more than six times the improvement in real execution time over that of the iterative implementation with the usual row major data layout, on three state-of-the-art architectures. Second, we address Dijkstra's algorithm for the single-source shortest paths problem and Prim's algorithm for minimum spanning tree problem. For these algorithms, we demonstrate up to two times the improvement in real execution time by using a simple cache-friendly graph representation, namely adjacency arrays. Finally, we address the matching algorithm for bipartite graphs. We show performance improvements of two to three times in real execution time by using the technique of making the algorithm initially work on subproblems to generate a suboptimal solution and, then, solving the whole problem using the suboptimal solution as a starting point. Experimental results are shown for the Pentium III, UltraSPARC III, Alpha 21264, and MIPS R12000 machines.

关键词： cache-friendly algorithms cache-oblivious algorithms graph algorithms shortest path minimum spanning trees graph matching data layout optimizations algorithm performance

来源：评论

学校读者我要写书评

暂无评论

On a check-digit method based on graph coloring

On a check-digit method based on graph coloring

引用

International Conference on Computer as a Tool (EUROCON 2007)

作者： Kulesza, Kamil Kotulski, Zbigniew Univ Cambridge Dept Appl Math & Theoret Phys Cambridge CB3 9EW England

ISBN: (纸本)9781424408122

We propose a check-digit scheme that makes use of graph vertex coloring. It complements known schemes, which rather make use of the graph structure. Our scheme can be used simultaneously with them to compensate for mutual weaknesses. We show that feasibility of the proposed scheme increases with the size of the number whose digits are checked, and with the overall probability of digit errors.

关键词： graph algorithms coding digital signal processing error detection

来源：评论

学校读者我要写书评

暂无评论

graph decomposition approaches for terminology graphs

Graph decomposition approaches for terminology graphs

引用

6th Mexican International Conference on Artificial Intelligence (MICAI 2007)

作者： Biha, Mohamed Didi Kaba, Bangaly Meurs, Marie-Jean SanJuan, Eric Univ Avignon LIA BP 1228 F-84911 Avignon 9 France LANLG F-84000 Avignon France Univ Blaise Pascal LIMOS F-63177 Clermont Ferrand France

ISBN: (纸本)9783540766308

We propose a graph-based decomposition methodology of a network of document features represented by a terminology graph. The graph is automatically extracted from raw data based on Natural Language Processing techniques implemented in the TermWatch system. These graphs are Small Worlds. Based on clique minimal separators and the associated graph of atoms: a subgraph without clique separator, we show that the terminology graph can be divided into a central kernel which is a single atom and a periphery made of small atoms. Moreover, the central kernel can be separated based on small optimal minimal separators.

关键词： graph algorithms graph decomposition polyhedral approach text mining topic vizualisation

来源：评论

学校读者我要写书评

暂无评论

A logical approach to multicut problems

引用

INFORMATION PROCESSING LETTERS 2007年第4期103卷 136-141页

作者： Gottlob, Georg Lee, Stephanie Tien Univ Oxford Comp Lab Oxford OX1 3QD England

Multicut problems are well-studied NP-complete problems in the field of network theory. Previously, by using graph theoretic methods, they have been shown to be fixed parameter tractable for different combinations of parameters, but not for any single parameter. In this paper different versions of the multicut problem are expressed in Monadic Second Order Logic (MSO) and an extended version of Courcelle's Theorem due to Amborg, Lagergren and Seese is used to demonstrate that these problems are fixed parameter tractable with respect to the parameter omega*, the treewidth of the input structure. Here, the input structure consists of a set V of vertices with two relations, the edge relation E of the input graph G = (V, E), and a relation H encoding all pairs of vertices to be disconnected. The contribution of this paper is two-fold: to introduce a single parameter for which the major variants of the multicut problem are fixed parameter tractable, and to use multicut problems as examples for demonstrating fruitful practical applications of logical properties and results in network theory. (C) 2007 Elsevier B.V. All rights reserved.

关键词： multicut parameterized complexity fixed-parameter tractability graph algorithms logic complexity networks

来源：评论

学校读者我要写书评

暂无评论

Edge distance and gray level extraction and orientation invariant transform for Chinese seal recognition

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第2期193卷 325-334页

作者： Su, Ching-Liang Da Yeh Univ Dept Ind Engn & Technol Da Tsuen 51505 Chang Hua Taiwan

This study finds distances between edge and centroid. The gray levels around edge are also found. These gray levels are used as parameters to conduct pattern recognition. The entire edge gray levels are recorded in a vertical strip. The "vector magnitude invariant transform" technique is used to transfer gray level quantity to an invariant vector magnitude quantity for object-identification. The "vector magnitude invariant transform" technique can solve image rotation problem. Various gray level vertical magnitude quantity strips are generated to cope with image-shifting problem. In this study, 150 comparisons are conducted to find the accuracy-rate of the developed algorithm. Within those 150 comparisons, 15 comparisons are conducted for self-comparison. The other 90 comparisons are conducted for comparisons between two different object images. The algorithm developed in this study can precisely classify seal-print image. (C) 2007 Elsevier Inc. All rights reserved.

关键词： graph algorithms edge distance extraction edge gray level extraction orientation invariant transform object-identification

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：