Добро пожаловать!

Pages:     | 1 |   ...   | 45 | 46 || 48 | 49 |   ...   | 82 |

Within the framework of statistical learning theory the structured risk minimization method was suggested. The idea of the method consists in consequent consideration of classes of decision functions, ranked on growth of their complexity. The function minimizing empirical risk in the corresponding class and simultaneously giving the best value for guaranteed risk is chosen. Support vectors machine [6] uses an implicit transformation of data to the space of high dimensionality by means of the given kernel function. In this space, a hyperplane maximizing the margin between support vectors of different classes is found. It is proved that the main factor influences the risk is not the dimensionality of the space but margin width.

In ''PAC-learning'' approach [7,8] (''Probably Approximately Correct''; developed within the framework of computational learning theory) the complexity of learning algorithm is taken into consideration. It is required that learning algorithm, with probability not smaller than finding the decision function for which the probability of mistake does not exceed, has time of work polynomially depended on sample size, complexity of class of decision functions, and on values 1/, 1/. The existence of such algorithms for some classes of recognition decision functions is proved, for instance, for conjunctions of Boolean predicates, linear decision functions, some types of neural networks, decision trees.

Statistical and computational learning theories suggest the worst-case analysis. From standpoints of statistical decision theory, their evaluations are of minimax type. However it is possible to use the average-case analysis (in Bayesian learning theory) for which it is necessary to define certain priory distribution (either on the set of distribution parameters or on the set of decision functions) and to find the evaluations at the average [9,10]. The main task is to find the decision function for which a posterior probability of error is minimal. As a rule, the finding of such function is computationally expensive, so the following rule of thumb can be used. Instead of optimum decision function search, less expensive function which is close (under determined conditions) to optimum is found. An example is minimum description length principle (minimizing the sum of the code length describing the function and the code length describing the data misclassified by this function). Another example is maximum a posterior probability function. From the other hand, the estimations can be done by statistical modeling (Markov Chain Monte Carlo method).

The main problem at the motivation of the Bayesian approach is a problem of choice of a priori distribution. In the absence of a priori information, it is possible to follow Laplace principle of uncertainty, according to which uniform a priori distribution is assumed. If the uncertainty in the determining of a priory distribution presents, the robust Bayesian methods can be applied.

Decision Making Bayesian learning theory was used for discrete recognition problem [10], for decision trees learning algorithms [11] etc. Within the Bayesian framework, the case of one discrete variable is mostly suitable for analytical calculations. Hughes [10] received the expression for the expected probability of recognition error depending on sample size and the number of values of the variable. It was shown that for the given sample size, an optimum number of values exists for which the expected probability of error takes minimum value. Lbov and Startseva [12] received the expressions for the expected misclassification probability for the case of available additional knowledge about the probability of mistake for the optimum Bayes decision function. In [13-15] this approach was generalized. Below we give the summary of the obtained results.

Bayesian Interval Estimates of Recognition Quality on Finite Set of Events a) The functional dependencies are obtained between the quality of an arbitrary method of decision functions construction and learning sample size, number of events [14,15].

b) The theoretical investigation of empirical risk minimization method is done [14,15].

c) The posterior estimates of recognition quality for the given decision function are found (with respect to number of events, empirical risk, sample size) [13].

d) New quality criteria for logical decision functions are suggested on the basis of above mentioned results.

An efficient method for classification tree construction is proposed [15].

e) New methods are suggested for the following data mining tasks: regression analysis, cluster analysis, multidimensional heterogeneous time series analysis, rare events forecasting [15].

Acknowledgements This work was supported by the Russian Foundation of Basic Research, grant 04-01-00858a Bibliography [1] Breiman L. Bagging predictors // Mach. Learn. 1996. V. 24. P. 123-140.

[2] Vapnik V. Estimation of dependencies based on empirical data. Springer- Verlag. 1982.

[3] Fukunaga K. Introduction to statistical pattern recognition. Academic Press, NY and London. 1972.

[4] Raudys S. Statistical and Neural Classifiers: An integrated approach to design. London: Springer-Verl., 2001.

[5] Vapnik V., Levin E. and Le Cun Y. Measuring the VC-Dimension of a Learning Machine // Neural Computation, Vol. 6, N 5, 1994. pp. 851--876.

[6] Vapnik V.N. An Overview of Statistical Learning Theory // IEEE Transactions on Neural Networks. 1999. V.10, N 5.


[7] Valiant L.G. A Theory of the Learnable, CACM, 17(11):1134-1142, 1984.

[8] Haussler D. Probably approximately correct learning // Proc. 0f the 8th National Conference on Artificial Intelligence.

Morgan Kaufmann, 1990. pp. 1101-1108.

[9] D.Haussler, M.Kearns, and R.Schapire. Bounds on sample complexity of Bayesian learning using information theory and the VC dimension // Machine Learning, N 14, 1994. pp. 84-114.

[10] Hughes G.F. On the mean accuracy of statistical pattern recognizers // IEEE Trans. Inform. Theory. 1968. V. IT-14, N 1. P. 55-63.

[11] W. Buntine. Learning classification trees // Statistics and Computing. 1992. V. 2. P. 63--73.

[12] Lbov, G.S., Startseva, N.G., About statistical robustness of decision functions in pattern recognition problems. Pattern Recognition and Image Analysis, 1994. Vol 4. No.3. pp.97-106.

[13] Berikov V.B., Litvinenko A.G. The influence of prior knowledge on the expected performance of a classifier. Pattern Recognition Letters, Vol. 24/15, 2003, pp. 2537-2548.

[14] Berikov, V.B. A Priori Estimates of Recognition Accuracy for a Small Training Sample Size // Computational Mathematics and Mathematical Physics, Vol. 43, No. 9, 2003. pp. 1377- [15] Lbov G.S., Berikov V.B. Stability of decision functions in problems of pattern recognition and heterogeneous information analysis. Inst. of mathematics Press, Novosibirsk. 2005. (in Russian) Author’s Information Vladimir Berikov – Sobolev Institute of Mathematics SD RAS, Koptyug pr.4, Novosibirsk, Russia, 630090;

e-mail: berikov@math.nsc.ru XII-th International Conference "Knowledge - Dialogue - Solution" К ВОПРОСУ О РАССТОЯНИЯХ НА ВЫСКАЗЫВАНИЯХ ЭКСПЕРТОВ И МЕРЕ ОПРОВЕРЖИМОСТИ (ИНФОРМАТИВНОСТИ) ВЫСКАЗЫВАНИЙ ЭКСПЕРТОВ НА КЛАССАХ МОДЕЛЕЙ ТЕОРИЙ Александр Викентьев Аннотация: При анализе знаний, заданных в виде высказываний экспертов, для различия содержащейся в них информации и группирования их по похожести, возникает необходимость введения расстояния между высказываниями экспертов и меры опровержимости (информативности) высказываний экспертов. Этой проблемой занимались Загоруйко Н.Г., Лбов Г.С., Викентьев А.А. [1-4].

Вводим расстояние не на всем множестве моделей, а на моделях некоторой, заранее фиксированной теории Г. Такой подход является естественным при изучении некоторой конкретной прикладной проблемы, (поскольку тогда расстояние и информативность не будут искажены моделями, не относящимися к изучаемой области) заданной например, некоторыми знаниями о ней, далее - теорией.

Работа проделана в рамках проекта РФФИ 04-01-00858а.

Ключевые слова: базы знаний,высказывания экспертов, теория моделй, метрика.

ACM Classification Keywords: I.2.6. Artificial Intelligence - knowledge acquisition.

Введение Мы фиксируем теорию Г, суть, набор таких высказываний, например, с которыми согласились все эксперты. Возможно, что теория Г может сформулирована на языке более высокого порядка и S() = {v1,..., vn} рассматриваются только те модели на которых выполнеы все аксиомы Г. Пусть {1,...,k}- набор элементарных высказываний. Теорией Г назовем набор формул (- гипотез) высказываний экспертов, с которыми все эксперты согласны. Предполагается, что теория Г удовлетворяет следующим требованиям:

1) непротиворечивости (совместности);

2) замкнутости относительно выводимости (это требование не обязательно, но для полноты можно считать, что эксперты могут доказывать формулы с помощью гипотез);

Расстояние на высказываниях экспертов и его свойства Пусть База Знаний состоит из формул исчисления высказываний.

S() = {v1,..., vn} Определение 1. Множество элементарных высказываний, используемых для написания высказываний из, назовем носителем совокупности знаний. Рассматриваем P(S( )){vi | i I} множество всевозможных подмножеств S( ), его элементы, суть наборы, где {1,...,n} истинностных значений элементарных высказываний, называем моделями. Мощность 2|S()| множества моделей исчисления высказываний равна | P(S( ))|=.

{M P(S()) | M Обозначим через ModГ=Mod Г= Г} все модели теории Г. Множество моделей S() из ModГ на которых формула А – истинна, обозначим через Mod (A).

Г Теорема 1. Для логической теории Г справедливы следующие свойства расстояния:

0 Г (,) 1) ;

Г (,) = Г (,) 2) ;

Decision Making Г Г (,) = 3) если,то ;

Г (,) = 1 Г ¬ 4) ;

Г 1 Г 1 Г (,) = Г (1,1) 5) если и,то ;

(,) = 1- (,¬) = (¬,¬) 6) ;

Г (,) Г (,) + (,) 7) ;

(,¬) = (,) + (,¬) 8) ;

(,) = (( & ),( )) 9).

Доказательство аналогично [4] с использованием моделей теории Г.

Мера опровержимости (информативности)высказываний экспертов Мера опровержимости (информативности) высказываний.

Определение 2. Мерой опровержимости высказывания назовем относительное число моделей теории Г на которых высказывание ложно. Для высказываний совместных с теорией определим меру информативности на множестве ModГ, как меру опровержимости высказывания.

| Mod ( & ¬) Mod (¬ & ) | () = (,) = = | Mod | | Mod (¬ & ) | | Mod (¬) | = = | Mod | | Mod | Теорема 2. Для логической теории Г справедливы следующие свойства меры опровержимости (информативности для формул, имеющих модель теории Г) высказываний:

1) 0 () 1;

2) (¬) = 1 - () ;

3) () ( & );

4) ( ) () ;

5) если (,) = 1, то ( & ) = 1 и ( ) = 0 ;

6) если (,) = 0, то () = () = ( & ) = ( );

7) ( & ) = (,) + ( ) ;

8) min{ (), ()} ( ) max{ (), ()} - (,) и min{ (), ()}+ (,) ( & ) max{ (), ()} 9) если () = ( ), () = ( )и (,) (, ), 1 1 1 то ( & ) ( & ) ;

1 10) если () ( ), () = ( ) и (,) = (, ), 1 1 1 то ( & ) ( & ) ;

1 () + () + (,) 11) ( & ) = ;

() + () - (,) 12) ( ) =.

XII-th International Conference "Knowledge - Dialogue - Solution" Доказательство аналогично [3, 4, 1] с использованием теоремы 1.

Заключение Имеет место обобщение этих результатов на теории первого порядка, как и выше с аналогичными обобщениями расстояния и меры опровержимости для предложений и формул первого порядка со свободными переменными. Результаты планируется использовать для кластизации данных знаний.

Список литературы 1. Г.С.Лбов, Н.Г.Старцева. Логические решающие функции и вопросы статистической устойчивости решений.

Новосибирск: Издательство Института математики, 1999. С. 85-102.

2. Н.Г.Загоруйко, М.В.Бушуев. Меры расстояния в пространстве знаний // Анализ данных в экспертных системах.

Новосибирск,1986. Выпуск 117:Вычислительные системы. С.24-35.

3. А.А.Викентьев, Г.С.Лбов. О метризации булевой алгебры предложений и информативности высказываний экспертов // Доклад РАН 1998.Т.361, №2 С.174-176.

4. A.A.Vikentiev, G.S.Lbov. Setting the metric and informativeness on statements of experts // Pattern Recognition and Image Analysis. 1997 V.7, N2, P.175-183.

5. Г.Кейслер, Ч.Ч.Чэн. Теория моделей. Москва:Мир,1977.

6. Ю.Л.Ершов, Е.А.Палютин. Математическая логика. Санкт-Петербург, 2004.

Информация об авторе Александр А. Викентьев – доцент, канд.физ-мат. Наук, Институт математики СО РАН, лаборатория анализа данных; e-mail: vikent@math.nsc.ru THE MEASURE REFUTATION, METRICS ON STATEMENTS OF EXPERTS (LOGICAL FORMULAS) ON A CLASS MODELS SOME THEORYAlexander Vikent’ev Abstract. The paper discusses a logical expert statements represented as the formulas with probabilities of the first order language consistent with some theory T. Theoretical-models methods for setting metrics on such statements are offered. Properties of metrics are investigated. The research allows solve problems of the best reconciliation of expert statements, constructions of decision functions in pattern recognition, creations the bases of knowledge and development of expert systems.

Keywords: pattern recognition, distance between experts statements.

ACM Classification Keywords: I.2.6. Artificial Intelligence - Knowledge Acquisition.

Introduction As the increasing interest to the analysis of the expert information given as probabilities logic statements of several experts is now shown, questions on knowledge of the experts submitted by formulas of the first order language with probabilities are interesting also. With the help of suitable procedure the statement of experts it is possible to write down as formulas of Sentence Logic or formulas of the first order language. Clearly, the various statements of experts (and the formulas appropriate to them) carry in themselves different quantity of the information. To estimate and analyses this information it is necessary to define the degree of affinity of This work was financially supported by the Russian Foundation for Basic Research, project no. 04-01-00858a.

Pages:     | 1 |   ...   | 45 | 46 || 48 | 49 |   ...   | 82 |

© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.