Learning A* priority function from unlabeled data

Details Learning A* priority function from unlabeled data Learning A* priority function from unlabeled data

2007-04-10

2010-11-23

Holmes, Michael B. (Department: 2129)

Data processing: artificial intelligence

Machine learning

C706S020000, C706S045000, C707S706000, C707S713000, C707S748000, C707S758000

Reexamination Certificate

active

07840503

ABSTRACT:
A technique for increasing efficiency of inference of structure variables (e.g., an inference problem) using a priority-driven algorithm rather than conventional dynamic programming. The technique employs a probable approximate underestimate which can be used to compute a probable approximate solution to the inference problem when used as a priority function (“a probable approximate underestimate function”) for a more computationally complex classification function. The probable approximate underestimate function can have a functional form of a simpler, easier to decode model. The model can be learned from unlabeled data by solving a linear/quadratic optimization problem. The priority function can be computed quickly, and can result in solutions that are substantially optimal. Using the priority function, computation efficiency of a classification function (e.g., discriminative classifier) can be increased using a generalization of the A* algorithm.

REFERENCES:
patent: 5168549 (1992-12-01), Takagi et al.
patent: 6556960 (2003-04-01), Bishop et al.
patent: 6697788 (2004-02-01), Fukuda et al.
patent: 6931608 (2005-08-01), Teig et al.
patent: 7024360 (2006-04-01), Savic et al.
patent: 7529761 (2009-05-01), Wen et al.
patent: 2005/0105723 (2005-05-01), Dupaquis et al.
patent: 2005/0129122 (2005-06-01), Booth et al.
patent: 2005/0143845 (2005-06-01), Kaji
patent: 2005/0267885 (2005-12-01), Klier
patent: 2006/0045337 (2006-03-01), Shilman et al.
patent: 2006/0245654 (2006-11-01), Viola et al.
patent: 2007/0011123 (2007-01-01), Ruml et al.
Pearl, Judea; Kim, Jin H., “Studies in Semi-Admissible Heuristics,” Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol. PAMI-4, No. 4, pp. 392-399, Jul. 1982.
Kohli, P.; Torr, P.H.S., “Efficiently solving dynamic Markov random fields using graph cuts,” Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on , vol. 2, No. pp. 922-929 vol. 2, Oct. 17-21, 2005.
Bagchi, A. and Mahanti, A. 1983. Search Algorithms Under Different Kinds of Heuristics-A Comparative Study. J. ACM 30, 1 (Jan. 1983), 1-21.
Baksalary, J. K. and Mathew, T. 1988. Admissible linear estimation in a general Gauss-Markov model with an incorrectly specified dispersion matrix. J. Multivar. Anal. 27, 1 (Oct. 1988), 53-67.
Aron Culotta and Ron Bekkerman and Andrew Mccallum. Extracting Social Networks and Contact Information from Email and the Web. Proceedings of the First Conference on Email and Anti-Spam. Jul. 2004.
Dechter, R. and Pearl, J. 1985. Generalized best-first search strategies and the optimality of A*. J. ACM 32, 3 (Jul. 1985), 505- 536.
Eaton, M. L. 1999 Markov Chain Conditions for Admissibility in Estimation Problems with Quadratic Loss. Technical Report. UMI Order No. PNA-R9904., CWI (Centre for Mathematics and Computer Science).
Korf, R. E. and Reid, M. 1998. Complexity analysis admissible heuristic search. In Proceedings of the Fifteenth National/Tenth Conference on Artificial intelligence/innovative Applications of Artificial intelligence (Madison, Wisconsin, United States). American Association for Artificial Intelligence, Menlo Park, CA, 305-310.
Kristjansson, T., Culotta, A., Viola, P., and McCallum, A. 2004. Interactive information extraction with constrained conditional random fields. In Proceedings of the 19th National Conference on Artifical intelligence (San Jose, California, Jul. 25-29, 2004). A. G. Cohn, Ed. Aaai Conference On Artificial Intelligence. AAAI Press / The MIT Press.
Andrew McCallum. Efficiently Inducing Features of Conditional Random Fields. In Proceedings of the 19th Conference in Uncertainty in Articifical Intelligence (UAI-2003). 2003.
Sarawagi, S., & Cohen, W. W. (2004). Semi-Markov conditional random felds for information extraction. Proceedings of the Eighteenth Annual Conference on Neural Information Processing Systems (NIPS-2004).
Daumé, H. and Marcu, D. 2005. Learning as search optimization: approximate large margin methods for structured prediction. In Proceedings of the 22nd international Conference on Machine Learning (Bonn, Germany, Aug. 7-11, 2005). ICML '05, vol. 119. ACM, New York, NY, 169-176. DOI= http://doi.acm.org/10.1145/1102351.1102373, sec. 1-5.
L. Harris, The bandwidth heuristic search. In: Proceedings International Joint Conferences on Artificial Intelligence (1973), pp. 23-29.
Russel and Norvig, Artificial Intelligence. Pearson Education, Inc. 2003. Chapter 4.1, pp. 94-110.
Dixon, et al., “Inference methods for a pseudo-Boolean satisfiability solver”, Date: 2002, http://www.cs.mcgill.ca/˜cmeagh1/CS566/AAAI02Dixon.pdf.
Tillman, Christoph, “Efficient Dynamic Programming Search Algorithms for Phrase-Based SMT”, Date: Jun. 2006, http://acl.ldc.upenn.edu/W/W06/W06-3602.pdf.
Viola, et al., “Learning to Extract Information from Semistructured Text using a Discriminative Context Free Grammar”; Date: Aug. 2005, http://delivery.acm.org/10.1145/1080000/1076091/p330-viola.pdf? key 1=1076091&key2=8266781711&coll=GUIDE&d1=GUIDE&CFID-147275 48&CFTOKEN=17436925.

Affiliated with

Also associated with

Rating

Learning A* priority function from unlabeled data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Learning A* priority function from unlabeled data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning A* priority function from unlabeled data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4228033