PREZENTARE PROIECT

Proiectul cercetari privind interpolarea polinomiala multidimensionala, clasificatorii polinomiali si aplicatii, are ca obiectiv principal realizarea unei cercetari fundamentale in domeniul interpolarii polinomiale multidimensionale, a clasificatorilor polinomiali si explorarea posibilitatilor de aplicare in domenii de varf, cum ar fi invatarea automata, data mining, clasificarea documentelor pe web. In ceea ce priveste clasificatorii, ideea originala pe care urmarim sa o aplicam este utilizarea unor alte distante decat cele euclidiene, care ne conduc la obtinerea unor suprafete interpolatoare de separare, pentru niste conditii care sunt determinate de distanta aleasa, in felul acesta obtinand o optimizare a metodei soft margin si respectiv, diversi clasificatori hibrizi. Ne propunem de asemenea analiza, din punct de vedere al eficientei, a diferitilor clasificatori polinomiali nou obtinuti, precum si realizarea unei comparatii intre acesti clasificatori si clasificatorii existenti in literatura de specialitate. Valorificarea cercetarii fundamentale se va reflecta si in proiectarea unui software multifunctional destinat obtinerii spatiilor de interpolare minimale pentru multimi date de conditii, a operatorului de interpolare, precum si obtinerea unor seturi de conditii pentru care anumite spatii de polinoame sunt interpolatoare. De asemenea se urmareste dezvoltarea resurselor umane prin antrenarea studentilor doctoranzi si a celor din anii terminali in cadrul cercetarilor fundamentale si a aplicatiilor care pot fi obtinute din aceste cercetari. Parte din rezultate vor sta la baza unui program de tip master si a doua cursuri din programele doctorale. Avand in vedere bogatia aplicatiilor practice care se intrezaresc, urmarim constituirea unui grup stabil de lucru in acest domeniu si a unei retele internationale de excelenta.
Interpolarea multidimensionala este un instrument care permite modelarea a numeroase sisteme complexe, multimea conditiilor de interpolare folosite in modelare, fiind dependenta de particularitatile sistemului modelat. Aplicatiile sunt multiple, dar cele mai relevante pentru societatea cunoasterii sunt cele legate de clasificare si predictie. Clasificatorii sunt mapari dintr-un spatiu x de caracteristici (discret sau continuu) intr-o multime y discreta de etichete. Clasificatorii sunt ficsi, sau cu invatare (supervizata sau nesupervizata). Clasificatorii au aplicatii practice in multe domenii din inginerie, stiintele exacte si stiintele vietii (life sciences), de la computer vision (recunoastere fata, urmarirea tintelor) si telefonie mobila, la medicina (analiza experimentelor clinice, analiza datelor rmn) si finante (analiza bursiera, predictie indicatori), de la recunoasterea vocii la data mining. Atat studiul interpolararii multidimensionale cat si a clasificatorilor sunt domenii de varf, in care se inregistreaza o cercetare intensa, la nivel mondial.
Proiectul Cercetari privind interpolarea polinomiala multidimensionala, clasificatorii polinomiali si aplicatii, are ca obiectiv principal realizarea unei cercetari fundamentare in domeniul interpolarii polinomiale multidimensionale, a clasificatorilor polinomiali si explorarea posibilitatilor de aplicare in domenii de varf, cum ar fi invatarea automata, data mining, clasificarea documentelor pe web. Cercetarile facute pe plan mondial in domeniu interpolarii multidimensionale si al clasificatorilor, desi foarte active in ultimii ani, nu acopera decat o mica parte a problemelor ridicate de studiul acestor domenii. Abordarile asupra interpolarii multidimensionale, existente pe plan mondial nu sunt unitare si se refera in special la cazuri particulare de conditii de interpolare. Realizarea unei cercetari fundamentale in domeniul interpolarii polinomiale multidimensionale, care sa ofere rezolvarea analitica si constructiva a problemei determinarii spatiilor de interpolare minimale pentru conditii generale de interpolare precum si informatii asupra proprietatilor schemelor de interpolare obtinute si a eficientei diferitelor metode care pot fi folosite in acest scop este de mare importanta, oferind un important instrument pentru rezolvarea problemelor de modelare a sistemelor complexe. In cadrul studiului fundamental pe care ni-l propunem referitor la interpolarea multidimensionala, urmarim sa oferim o solutie constructiva generala a problemei de interpolare multidimensionale, sa facem o comparatie intre proprietatile spatiile de interpolare minimale obtinute pentru aceleasi conditii de interpolare (invarianta la scalare, D-invarianta, monotonie, etc) si sa oferim o estimare a restului formulei de interpolare obtinute. Se urmareste studierea unor scheme de interpolare care apar in modelarea unor sisteme complexe: interpolarea ponderata si interpolarea prin polinoame de un anume grad generalizat. Tema propusa ofera multiple posibilitati de obtinere a unor rezultate originale cu potentiale aplicatii practice, in domenii de varf, de mare interes pentru societate, cum ar fi invatarea automata, data mining, clasificarea documentelor pe web. Numeroase aplicatii in analiza exploratorie a patternurilor, precum si luarea de decizii, necesita lucrul pe multimi mari de date. Algoritmii de clasificare sau clustering (clasificare nesupervizata) sunt instrumente ideale pentru rezumarea datelor, regasire documente, data mining, recunoastere obiecte, filtrarea informatiei. Acestea sunt motivele care ne-au determinat sa utilizam rezultatele studiului fundamental facut in prima parte a proiectului pentru optimizarea clasificatorilor hibrizi. Pentru a realiza acest obiectiv, avem insa nevoie de un studiu fundamental asupra clasificatorilor in general si a clasificatorilor polinomiali in special. Urmarim introducerea unor noi clasificatori hibrizi, folosind suprafete interpolatoare, analiza, din punct de vedere al eficientei, a diferitilor clasificatori nou obtinuti, precum si realizarea unei comparatii intre acesti clasificatori si clasificatorii existenti in literatura de specialitate. Importanta stiintifica a temei propuse rezida si din multitudinea domeniilor in care rezultatele funtamentale, teoretice, pe care ne propunem sa le obtinem, pot fi aplicate. Rezultatele teoretice vor fi valorificate si prin proiectarea unui software multifunctional destinat obtinerii spatiilor de interpolare minimale pentru multimi date de conditii, a operatorului de interpolare, precum si obtinerea unor seturi de conditii pentru care anumite spatii de polinoame sunt interpolatoare, acest software putand fi folosit pentru modelarea sistemelor complexe, care impun diverse conditii de interpolare. Avand in vedere bogatia aplicatiilor practice care se intrezaresc, studiul prezentei teme da posibilitatea cooperarii stiintifice internationale. Urmarim constituirea unui grup stabil de lucru in acest domeniu si a unei retele internationale de excelenta. In acest sens, avem deja acordul Universitatii St. Kliment Ohridski din Sofia, colectivul catedrei de Metode Numerice si Algoritmi fiind interesat in colaborare cu noi pe aceasta tema.
Interpolarea multidimensionala este un instrument care permite modelarea a numeroase sisteme complexe, multimea conditiilor de interpolare folosite in modelare fiind dependenta de particularitatile sistemului modelat. Rationamente legate de eficienta computationala a polinoamelor de interpolare impun utilizarea unor spatii de interpolare de grad minimal. Deoarece pot exista mai multe spatii de interpolare minimale pentru aceeasi multime de conditii de interpolare, se impune alegerea unui anumit spatiu, in functie de fenomenul sau sistemul modelat. Pe de alta parte, in practica poate apare si problema inversa, de determinare a unor multimi de conditii pentru care un anume spatiu polinomial este interpolator. Aceasta problema apare de exemplu in modelarea unor elemente aflate pe frontiera unor sisteme. O incercare de generalizare a problemei apare pentru prima data in 1992, in [2]. Acesta este articolul de baza care trateaza un caz general de alegere a functionalelor. Alte articole aparute pe aceasta tema se refera doar la cazuri particulare determinate de probleme concrete (vezi [5] –[6]). In prezent nu exista un studiu global al problemei generale de interpolare multidimensionala, care sa permita determinarea efectiva a unui spatiu interpolator minimal pentru o multime oarecare de conditii. Cateva implementari realizate in MAPLE, permit alegerea interpolantului pentru anumite conditii de interpolare ([5]), fara a oferi informatii despre unicitatea solutiei obtinute si erorii de calcul. Mai mult, daca nu intreg spatiul de polinoame de un anume grad este interpolator pentru o multime de conditii, atunci exista mai multe spatii de interpolare minimale si deci mai multe posibilitati de modelare a sistemelor. Nu exista in literatura de specialitate un studiu referitor la comparatia acestor spatii sub aspectul diverselor proprietati pe care le au. O proprietate de maxima importanta a unei scheme de interpolare este constructibilitatea, adica posibilitatea de a obtine prin metode numerice spatiul interpolator (printr-o baza a sa ) si interpolantul. Exista mai multe metode pentru realizarea acestor deziderate, dar nu toate metodele sunt proprii de aplicat pentru orice problema. Principalele metode sunt a) - metode analitice, prin care se foloseste un algoritm iterativ de constructie a unei baze a spatiului de interpolare. Acest algoritm foloseste un proces de ortogonalizare fata de un produs scalar particular considerat. Baza obtinuta este folosita apoi la obtinerea polinomului de interpolare. Se poate folosi insa determinarea spatiului de interpolare prin determinarea unei baze Lagrange sau a unei baze Newton a spatiului de interpolare b)- metode algebrice, bazate pe reducerea problemei de interpolare la rezolvarea unui sistem algebric de ecuatii, de grad necunoscut apriori. Pentru rezolvarea acestui sistem se foloseste metoda eliminarii Gauss pe segmente . c)- metode care sunt folosite in cazul in care ker-ul multimii de functionale L, ce constituie conditiile de interpolare, este un ideal de polinoame. In aceasta situatie, se poate folosi un algoritm de reducere relativ la o H-baza a idealului ker(L), spatiul polinoamelor reduse obtinut, fiind un spatiu de interpolare minimal pentru conditiile L. d) – metode particulare, care se folosesc numai pentru anumite multimi de conditii. Metodele a,b,c au fost descrise in lucrarile [1]-[4]. Reluarea si adaptarea acestor metode pentru cazuri particulare de functionale este intalnita in articole din ultimii ani ( vezi [7]) Nu exista insa in literatura de specialitate nici o abordare unitara si comparativa a tuturor metodelor. De aceea, in partea de cercetare fundamentala in domeniul interpolarii multidimensionale ne propunem un studiu care sa permita alegerea intre una dintre aceste metode in functie de multimea de conditii de interpolare si de caracteristicile principale pe care le dorim pentru schema de interpolare ( stabilitate a schemei, continuitate, ordin redus de complexitate a algoritmului folosit). Modelarea prin interpolare are multiple aplicatii in ITC, in prelucrarea de imagini, in realitatea virtuala, e-aplicatii etc Exista numeroase aplicatii in care analiza exploratorie a patternurilor precum si luarea de decizii se face pe multimi mari de date. Un exemplu clasic in acest sens a devenit regasirea documentelor pe web. Documentele relevante trebuie selectate dintre milioane de documente de dimensiuni mai mari de 1000. Procedeul standard consta in rezumarea datelor si prelucrarea acestei forme compacte. Algoritmii de clasificare sau clustering (clasificare nesupervizata) sunt instrumente ideale pentru rezumarea datelor, regasire documente, data mining, recunoastere obiecte, filtrarea informatiei. Metodele de clasificare pot fi considerate de doua tipuri, generative si discriminante. Support Vector Machines – SVM si regresia logistica sunt, de exemplu, metode discriminante de clasificare. Aceste metode sunt utilizate in numeroase articole. In cazul metodelor discriminante de invatare se optimizeaza o frontiera de decizie. Metodele generative creaza intai un model al distributiei conjugate (joint) pentru eticheta de clasa si caracteristici, iar apoi clasifica o instanta ca apartinand clasei cele mai probabile conform modelului. Problemele de clasificare apar deseori in procesele de invatare automata – machine learning. In astfel de procese avem o multime de puncte dintr-un spatiu multidimensional si dorim sa vedem daca le putem imparti in doua clase, respectiv sa stabilim daca le putem separa printr-un hiperplan (clasificare liniara). Ideea este ca separarea sa se realizeze cu ca mai multa acuratete, respectiv ca distanta, numita margine, dintre cele mai apropiate puncte din cele doua clase, sa fie maxima. Daca exista un hiperplan de separare, acesta se numeste hiperplan optim sau hiperplan de margine maxima (maximum-margin hyperplan). Vectorii cei mai apropiati de hiperplanul optim se numesc vectori suport. Support Vector Machine- SVM – motor cu support vectorial este un nou tip de masina de invatare in problemele de regresie si de recunoastere a pattern-urilor. SVM construieste solutia plecand de la o multime de date de antrenament care constituie vectorii suport. Practic, SVM folosesc o tehnica denumita kernel trick pentru a aplica tehnici de clasificare liniara in probleme de clasificare neliniara. V. Vapnik a propus in 1963 un algoritm pentru gasirea hiperplanului optim. Plecand de la acest algoritm, Vsapnik, impreuna cu Bernhard Boser si Isabelle Guyon, propun, in 1992, crearea unor clasificatori neliniari prin aplicarea metodei kernel trick hiperplanelor optimale, practic, fiecare produs scalar din algoritmul original fiind inlocuit printr-o functie nucleu neliniara. Avantajul acestui nou algoritm consta in aceea ca permite potrivirea hiperplanului optim in spatiul transformat de caracteristici. Transformarea poate fi neliniara iar spatiUl caracteristicilor, multidimensional. Majoritatea articolelor referitoare la SVM ( vezi [15] – [19]), urmaresc utilizarea unui anumit nucleu.In 1995, C. Cortes si Vapnik [13] propun un algoritm care tine cont de elementele clasificate gresit sau care nu pot fi etichetate. Metoda, numita Soft Margin, margine imprecisa, se aplica atunci cand nu exista un hiperplan care sa separe multimea de puncte din setul de antrenament in doua clase distincte. In acest caz se va alege hiperplanul care separa punctele cat mai bine posibil, si in acelasi timp maximizeaza distanta fata de cel mai aproape set separate clar.

Bibliografie:

1. Carl de Boor, Amos Ron, The least solution for the polynomial interpolation problem; Math.Zeitschrift; 210; 1992; 347--378;
2. Carl de Boor , Gauss elimination by segments and multivariate polynomial interpolation. Approximation and Computation : A Festschrift in Honor of Walter Gautschi, Birkhauser Verlag, 1994, pag. 87-96.
3. Carl de Boor,Computational Aspects of multivariate polynomial interpolation: Indexing the coefficients, \AICM; 12; 2000; 289-301
4. Carl de Boor: Ideal interpolation, TexasXI, 2005, 59-91
5. Holger Wendland, R. Ahrem and A. Beckert A new multivariate interpolation method for large-scale spatial coupling problems in aeroelasticity, to appear in the Proceedings to the International Forum on Aeroelasticity and Structural Dynamics 2005.
6. J.M. Carnicer, M. Gasca, Classification of Bivariate Configurations with Simple Lagrange Interpolation Formulae, Journal, Advances in Computational Mathematics PublisherVolume 20, Numbers 1-3 / January, 2004, Pages 5-16
7. Zhang Chuanlin,, A New Method for the Construction of Multivariate Minimal Interpolation Polynomial Journal Approximation Theory and its Applications Publisher Springer Netherlands, Volume 17, Number 1 / March, 2001, Pages 10-17
8. H. M Moller., T. Sauer H-bases for polynomial interpolationand system solving, Advanced in Computational Mathematics, !999.
9. Dana Simian, Homoheneous Polynomial Interpolation of Multivariate Functions. Automation, Computers, Applied Mathematics, Scientific Journal, Vol 11, 2002, nr.1, pag. 133-138.
10. Dana Simian, Corina Simian, On multivariate interpolation by weights. Analele stiintifice ale Universitatii Ovidius Constanta, seria Matematica,vol. 11, 2003
11. Dana Simian, A generalization of the remainder in multivariate interpolation, WSEAS Transactions on Mathematics, nr. 484, 2004, pag. 334-340, ISSN 1109-2769
12. Dana Simian, The ?- Error Order in Multivariate Interpolation. Lectures Notes in Computer Science, (2005), Springer Berlin Heildelberg New York,ISSN 0302-9743, ISBN 3-540-24937-0, pag. 478-486
13. CECM Annual Summer Meetings. MAPLE package MultiInterp, 2005;
14. B. E. Boser, I. M. Guyon, and V. N. Vapnik. A training algorithm for optimal margin classifiers. In D. Haussler, editor, 5th Annual ACM Workshop on COLT, pages 144-152, Pittsburgh, PA, 1992. ACM Press
15. Corinna Cortes and V. Vapnik, Support-Vector Networks, Machine Learning, 20, 1995.
16. Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based learning methods. Cambridge University Press, 2000. ISBN 0-521-78019-5SVM Boo
17. Huang T.-M., Kecman V., Kopriva I. (2006), Kernel Based Algorithms for Mining Huge Data Sets, Supervised, Semi-supervised, and Unsupervised Learning, Springer-Verlag, Berlin, Heidelberg, 260 pp. 96 illus., Hardcover, ISBN 3-540-31681-7.
18. Vojislav Kecman: Learning and Soft Computing - Support Vector Machines, Neural Networks, Fuzzy Logic Systems , The MIT Press, Cambridge, MA, 2001.
19. Tapio Pahikkala, Sampo Pyysalo, Jorma Boberg, Aleksandr Mylläri and Tapio Salakoski. Improving the Performance of Bayesian and Support Vector Classifiers in Word Sense Disambiguation using Positional Information. In Proceedings of the International and Interdisciplinary Conference on Adaptive Knowledge Representation and Reasoning (AKRR'05), Jun 2005