×

zbMATH — the first resource for mathematics

Fuzzy constraint networks for signal pattern recognition. (English) Zbl 1082.68792
Summary: This paper deals with representation and reasoning on information concerning the evolution of a physical parameter by means of a model based on the Fuzzy Constraint Satisfaction Problem formalism, and with which it is possible to define what we call Fuzzy Temporal Profiles (FTP). Based on fundamentally linguistic information, this model allows the integration of knowledge on the evolution of a set of parameters into a knowledge representation scheme in which time plays a fundamental role.
The FTP model describes the behaviour of a physical parameter on the basis of a set of signal events, and which allows the evolution of the parameter between each pair of events to be modelled as signal episodes. Given the fundamentally linguistic nature of the information represented, the consistency analysis of this information is an essential task. Nevertheless, the obtention of the minimal representation of the network that defines an FTP is an NP-hard problem. In spite of this, we supply algorithms guaranteeing local levels of consistency that allow to correct a large proportion of the errors committed by a human expert in the linguistic description of the profile. Furthermore, we propose a new topology whose consistency can be guaranteed in polynomial time. We also study the applicability of this model in the recognition of signal patterns.

MSC:
68T10 Pattern recognition, speech recognition
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, J., Towards a general theory of action and time, Artificial intelligence, 23, 123-154, (1984) · Zbl 0567.68025
[2] Attneave, F., Some informational aspects of visual perception, Psychological rev., 61, 3, 183-193, (1954)
[3] Barro, S.; Marı́n, R.; Mira, J.; Patón, A., A model and a language for the fuzzy representation and handling of time, Fuzzy sets and systems, 61, 153-175, (1994)
[4] Bellman, R.E.; Zadeh, L.A., Decision-making in a fuzzy environment, Management sci., 17, 4, 141-154, (1970) · Zbl 0224.90032
[5] Bistarelli, S.; Montanari, U.; Rossi, F., Semiring-based constraint solving and optimization, J. ACM, 44, 2, 201-236, (1997) · Zbl 0890.68032
[6] Cheung, J.T.Y.; Stephanopoulos, G., Representation of process trends. part I: A formal representation framework, Computers chemical engineering, 14 (4/5), 495-510, (1990)
[7] Dechter, R., Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition, Artificial intelligence, 41, 3, 273-312, (1990)
[8] Dechter, R., Constraint networks, (), 276-285
[9] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artificial intelligence, 49, 61-95, (1991) · Zbl 0737.68070
[10] Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, Artificial intelligence, 34, 1-38, (1987) · Zbl 0643.68156
[11] Drakengren, T.; Jonsson, P., Maximal tractable subclasses of Allen’s interval algebra: preliminary report, (), 389-394 · Zbl 0894.68144
[12] Drakopoulos, J.A.; Hayes-Roth, B., Tfpr: A fuzzy and structural pattern recognition system of multi-variate time-dependent pattern classes based on sigmoidal functions, Fuzzy sets and systems, 99, 57-72, (1998)
[13] Dubois, D.; Fargier, H.; Prade, H., Fuzzy constraints in job-shop scheduling, J. intelligent manufacturing, 6, 215-234, (1995)
[14] Dubois, D.; Fargier, H.; Prade, H., Possibility theory in constraint satisfaction problems: handling priority, preference and uncertainty, Appl. intelligence, 6, 287-309, (1996) · Zbl 1028.91526
[15] Dubois, D.; Prade, H., Fuzzy real algebra: some results, Fuzzy sets and systems, 2, 327-348, (1979) · Zbl 0412.03035
[16] Dubois, D.; Prade, H., Fuzzy sets and systems: theory and applications, (1980), Academic Press New York · Zbl 0444.94049
[17] Dubois, D.; Prade, H., Systems of linear fuzzy constraints, Fuzzy sets and systems, 3, 37-48, (1980) · Zbl 0425.94029
[18] Dubois, D.; Prade, H., Possibility theory: an approach to computerized processing of uncertainty, (1985), Plenum Press New York
[19] Dubois, D.; Prade, H., Processing fuzzy temporal knowledge, IEEE trans. systems man cybernet., 19, 4, 729-744, (1989)
[20] Félix, P.; Barro, S., A fuzzy model for the representation and recognition of linguistically described trends, Intelligent data analysis, 5, 6, 503-529, (2001) · Zbl 1088.68763
[21] Félix, P.; Fraga, S.; Marı́n, R.; Barro, S., Linguistic representation of fuzzy temporal profiles, Internat. J. uncertainty, fuzziness and knowledge-based systems, 7, 3, 243-256, (1999) · Zbl 1087.93503
[22] Freuder, E.C., A sufficient condition of backtrack-free search, Comm. ACM, 29, 1, 24-32, (1982) · Zbl 0477.68063
[23] Gaganov, A.A., Computational complexity of the range of the polynomial in several variables, Cybernetics, 418-421, (1985) · Zbl 0608.68028
[24] Garey, M.R.; Johnson, D.S., Computers and intractability. A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company San Francisco, CA · Zbl 0411.68039
[25] Ghallab, M., On chronicles: representation, on-line recognition and learning, (), 597-606
[26] Ghallab, M.; Mounir Alaoui, A., Managing efficiently temporal relations through indexed spanning trees, (), 1297-1303 · Zbl 0718.68080
[27] Haimowitz, I.J.; Le, P.P.; Kohane, I.S., Clinical monitoring using regression-based trend templates, Artificial intelligence in medicine, 7, 473-496, (1995)
[28] Hyvönen, E., Constraint reasoning based on interval arithmetic: the tolerance propagation approach, Artificial intelligence, 58, 71-112, (1992) · Zbl 0782.68102
[29] Kaufmann, A.; Gupta, M.M., Introduction to fuzzy arithmetic, (1985), Van Nostrand Reinhold · Zbl 0588.94023
[30] Kautz, H.; Ladkin, P., Integrating metric and qualitative temporal reasoning, (), 241-246
[31] Khatib, L.; Morris, P.; Morris, R.; Rossi, F., Temporal constraint reasoning with preferences, (), 322-327
[32] V. Kreinovich, Personal communication, 2003
[33] Kreinovich, V.; Lakeyev, A.; Rohn, J.; Kahl, P., Computational complexity and feasibility of data processing and interval computations, (1998), Kluwer Dordrecht · Zbl 0945.68077
[34] Ligomenides, P.A., Real-time capture of experiential knowledge, IEEE trans. systems man cybernet., 18, 4, 542-551, (1988)
[35] Lowe, A.; Harrison, M.J.; Jones, R.W., Diagnostic monitoring in anaesthesia using fuzzy trend templates for matching temporal patterns, Artificial intelligence in medicine, 16, 2, 183-199, (1999)
[36] Mackworth, A., Consistency in networks of relations, Artificial intelligence, 8, 99-118, (1977) · Zbl 0341.68061
[37] Marı́n, R.; Barro, S.; Bosch, A.; Mira, J., Modeling the representation of time from a fuzzy perspective, Cybernetics and systems: an international journal, 25, 2, 217-231, (1994) · Zbl 0809.68111
[38] Meiri, I., Combining qualitative and quantitative constraints in temporal reasoning, Artificial intelligence, 87, 343-385, (1996)
[39] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inform. sci., 7, 95-132, (1974) · Zbl 0284.68074
[40] Moore, R.E., Methods and applications of interval analysis, (1979), SIAM Philadelphia, PA · Zbl 0417.65022
[41] Navarrete, I.; Sattar, A.; Wetprasit, R.; Marı́n, R., On point-duration networks for temporal reasoning, Artificial intelligence, 140, 1-2, 39-70, (2002) · Zbl 0999.68203
[42] Nebel, B.; Bürckert, H., Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra, (), 356-361
[43] Oppenheim, A.V.; Schafer, R.W., Discrete-time signal processing, signal processing, (1989), Prentice-Hall Englewood Cliffs, NJ · Zbl 0676.42001
[44] Piater, J.; Stuchlik, F.; von Specht, H.; Muhler, R., Fuzzy sets for feature identification in biomedical signals with self-assessment of reliability: an adaptable algorithm modeling human procedure in BAEP analysis, Comput. biomed. res., 28, 335-353, (1995)
[45] Qian, D., Representation and use of imprecise temporal knowledge in dynamic systems, Fuzzy sets and systems, 50, 59-77, (1992)
[46] Rommelfanger, H.J., Network analysis and information flow in fuzzy environment, Fuzzy sets and systems, 67, 119-128, (1994)
[47] Schalkoff, R., Pattern recognition. statistical, structural and neural approaches, (1992), Wiley New York
[48] Schwalb, E.; Dechter, R., Processing disjunctions in temporal constraints networks, Artificial intelligence, 93, 29-61, (1997) · Zbl 1017.68536
[49] Steimann, F., The interpretation of time-varying data with DIAMON-1, Artificial intelligence in medicine, 8, 343-357, (1996)
[50] Tsang, E., Foundations of constraint satisfaction, (1993), Academic Press New York
[51] van Beek, P., Reasoning about qualitative temporal information, Artificial intelligence, 58, 297-326, (1992) · Zbl 0782.68106
[52] Vila, L.; Godó, L., On fuzzy temporal constraint networks, Mathware and soft computing, 1, 3, 315-334, (1994) · Zbl 0833.68012
[53] Vilain, M.; Kautz, H., Constraint propagation algorithms for temporal reasoning, (), 377-382
[54] Vilain, M.; Kautz, H.; van Beek, P., Constraint propagation algorithms for temporal reasoning: A revised report, (), 373-381
[55] Zadeh, L.A., The concept of a linguistic variable and its application to approximate reasoning, Inform. sci., 8, 199-249, (1975), Part 1 · Zbl 0397.68071
[56] Zadeh, L.A., Fuzzy sets as a basis for a theory of possibility, Fuzzy sets and systems, 1, 3-28, (1978) · Zbl 0377.04002
[57] Zadeh, L.A., Fuzzy sets and applications: selected papers by L.A. zadeh, (1987), Wiley New York · Zbl 0671.01031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.