Discussion :

[koamh]

Bonjour à tous,

Je me permets de demander de l'aide à vos brillants cerveaux, puisque le mien semble être à court d'idées.

Voilà le contexte : Pour un projet, je développe un soft en python. Je vous passe le but de ce soft, ce n'est pas utile. Toujours est-il que, dans ce soft, il me faut trouver tous les maxima locaux d'une fonction discrete, et ce, le plus efficacement possible (en terme de temps de calcul, notament).

Bon, jusque là, pas de soucis. Ayant souvenir de mes années de lycée, ça devrait aller, me dis-je. Dérivées première et seconde, à la limite un peu d'éléments finis, et c'est marre.

Ce qui complique un peu la tâche, c'est que les points déterminant la fonction sont tirés aléatoirement. Ok. Pas encore insurmontable, il suffirait de les trier.

Ce qui complique un peu plus, c'est que je n'ai pas de connaissance a priori de la dimension du problème. Ma fonction peut très bien dépendre d'un seul paramètre, 2,15,35 ou 2000000. (bon j'exagère un peu, quand même.).

Donc voilà. J'ai un espace à n dimensions, rempli de k points tirés aléatoirement, dont je connais les valeurs. Mais où se cachent tous les maxima?

J'espère avoir été assez clair...

Avez-vous une idée?

P.S. : On est d'accord que le maximum global est facile à trouver. Ce sont les maxima locaux qui le sont moins.

[FR119492]

Salut!

J'ai un espace à n dimensions, rempli de k points tirés aléatoirement, dont je connais les valeurs. Mais où se cachent tous les maxima?

Je reformule le problème d'une manière moins "géométrique":

J'ai une fonction de n variables dont je connais k valeurs. Quelles sont les valeurs de cette fonction qui sont supérieures à toutes les plus proches?

Est-ce que ça correspond bien à ton problème? Si oui, je crains bien que ton problème soit insoluble, mais ça ne fait rien: on va quand même essayer. Pour le moment, j'y réfléchis; alors, je te demande un tout petit peu de patience.
Jean-Marc Blanc

[FR119492]

Salut!
J'ai commencé à réfléchir, et je te propose un exemple très simple: une fonction d'une seule variable:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
0.025  0.4579
0.075  0.9801
0.125  1.1961
0.175  1.0337
0.225  0.5671
0.275 -0.0108
0.325 -0.4605
0.375 -0.5843
0.425 -0.2912
0.475  0.4280
0.525  1.0476
0.575  1.3273
0.625  1.4160
0.675  1.1577
0.725  0.6074
0.775 -0.0507
0.825 -0.5842
0.875 -0.8038
0.925 -0.6378
0.975 -0.1601

Où vois-tu les maxima?

Jean-Marc Blanc

[souviron34]

Je crois qu'il faudrait en savoir plus sur le vrai problème de base..

Le problème est difficilement compréhensible..

• Est-ce une interpolation de surface , et trouver les extrémas sur cette surface ?
• Est-ce un problème de traitement d'image ?
• Est-ce un problème purement statistique ?
• Autre..

[Invité]

Ce qui complique un peu plus, c'est que je n'ai pas de connaissance a priori de la dimension du problème. Ma fonction peut très bien dépendre d'un seul paramètre, 2,15,35 ou 2000000. (bon j'exagère un peu, quand même.).

Ca n'a pas grand chose à voir avec la dimension du problème. Une fonction d'un seul paramètre, par exemple cos(ax) peut avoir un (très) grand nombre de maxima locaux si a est assez élevé.

Un premier algorithme consisterait à déterminer parmi tes données des voisinages de chacun des points, et à retenir comme maxima locaux ceux qui maximisent la fonction. Tu pourras ensuite raffiner l'approche en interpolant, ou en utilisant des noyaux pour "lisser" les données (si celles ci sont de nature statistique).

Ceci pose deux questions :

1- comment déterminer efficacement les voisinages? si ton problème est multidimensionnel, le mot "KD-tree" vient natuellement à l'esprit

2- quel "rayon" de voisinage choisir? ceci relève des statistiques, il faudrait regarder du côté des lois de Weibull (c'est l'équivalent de la loi normale quand on prend des maxima), et des tests qui lui sont associés.

Sans plus d'information, il est difficile d'en dire plus, mais ce n'est pas exactement du niveau Terminale...

Francois

[koamh]

Bonjour à tous,

Déjà désolé du retard dans la réponse, mais pour être tout à fait honnête, je ne pensais pas avoir de réponses. C'était manifestement bien mal connaitre les personnes de ce forum, et je vous présente donc mais plus plates excuses.

J'aimerais vraiment vous détailler avec précision ce que fait mon programme, mais pour des raisons de propriétés intellectuels, je suis un peu pieds et poings liés.

Ce que je peux dire, c'est ceci: Si mon projet traite effectivement, dans sa globalité, d'interpolation statistique, ce n'est pas le cas dans la partie qui me pose problème.

En fait, cette partie traite d'un choix de point:
Pour améliorer l'interpolation nommée ci-dessus (pour ceux à qui ça parle, je parle ici de Krigeage et d'optimisation globale, et j'en dis déjà beaucoup), il me faut choisir les points qui semble les plus intéressant.
Il s'agit d'un problème itératif: à chaque boucle on estime quels sont les points les plus à même d'améliorer l'interpolation, donc les plus intéressant à calculer.

Pour faire ce choix, on utilise une fonction dont nous connaissons l'expression mathématique, mais qui va dépendre de la valeur d'une autre fonction qui, elle, est simulée. Et c'est cette dernière qui va dépendre d'un nombre non connu a priori de paramètres.

Les points améliorant l'interpolation sont ceux qui maximise la fonction d'optimisation globale. Voilà pourquoi j'aimerais avoir l'ensemble des maxima locaux.

Il faut savoir que je ne veux pas connaître l'emplacement réel de tous les maxima locaux de cette fonction, mais déterminer, sur l'ensemble des points tirés aléatoirement, lesquels ont une valeur plus haute que ses voisins. (ce qui pose le problème de définition de voisins, évidement).

En d'autres mots : Soit {x1,x2,x3,....,xn} appartenant à R^d des points tirés aléatoirement (grâce à une méthode de type latin hypercube) et f:=R^d->R. Quels sont les points pour lesquels f(xi)>f(xk), avec xk l'ensemble de ces voisins?

J'espère que c'est un peu plus clair. Je vais essayer de répondre maintenant à chacun.

@Jean Marc Blanc : C'est tout à fait le problème. Par contre je ne vois pas où tu veux en venir sur ton deuxième post.
Les maximas sont en position 3 et 13, veux-tu parler de normes? J'ai déjà essayé quelque chose de ce style, mais le problème vient lorsque les pentes ne sont pas les même de tous les côtés de la bosse. Si ce n'est pas là où tu veux en venir, je suis tout ouïe. Ou toute vue, dans le cas présent.

@souviron34: J'espère avoir pu éclairer ta lanterne avec ce que j'ai décrit précédemment. N'hésite pas à me demander de plus amples explications, j'essaierais d'y répondre sans me faire virer.

@françois: J'ai en effet commencé à regarder ces problèmes de "kd-tree" et de définition de maxima en statistique. J'ai lu pas mal d'article comme Wei-mei et al. 2012 et certaines de ces références, comme Bentley et al., 1975 (ça date un peu, d'accord...).
Je dois avouer que je dois peut-être m'y plonger avec un peu plus de profondeur. J'ai pas encore tout à fait saisi l'intégralité du concept. Ah ça, les physiciens ne sont pas des mathématiciens.
Par contre, je ne connais pas les lois de Weibull. Je vais me renseigner. Si tu as quelques liens que tu penses utiles, je suis preneur.

edit: url

[Invité]

Bonjour,

Bentley, c'est effectivement le texte de base sur les Kd-tree. Le chapitre "retrieval on secondary keys" du tome trois de Knuth pose également très bien le problème (mais c'est assez profond, comme tous ce que fait Knuth). C'est encore plus vieux que Bentley, mais en informatique, la littérature des années 70 est souvent excellente, la littérature actuelle est juste abondante...

Pour le côté pratique, il y a des explications et des exemples de codes dans la troisième édition de Numerical Recipes, et dans Introduction to Algorithms de Cormen.

Pour des choses plus modernes, tu peux chercher ce qui a été écrit sur les algorithmes kNN (k-nearest neighbours), ils ont en fait le même problème que toi, à ceci prêt qu'ils cherchent une moyenne au lieu d'un arg-max.

Le problème que les kd-trees et approches similaires cherchent à résoudre, c'est comment trouver les plus proches voisins d'un ensemble de N points, sans avoir à calculer une matrice N^2 de distances, ni avoir à faire N tris de ceux ci (o(NlogN), les tris).


Le théorème sur les maxima et la loi de Weibull doit s'appeler Fisher-Tippett. L'idée générale c'est que quand le nombre d'observations augmente, tout comme la moyenne d'une VA suit une loi normale, son maximum suit une loi de Weibull. Donc, tout test statistique peut facilement être adapté à une "prise de max" en remplaçant l'une par l'autre.

Le point important, c'est qu'il va falloir décider à un moment quelle taille de voisinage tu prends pour décider qu'un point est un maximum local. Ca dépend de la forme de la fonction sous jacente, que tu ne connais pas. Mon idée (mais je n'ai pas beaucoup réfléchi, donc c'est peut être naif et stupide), c'est qu'on pourrait ajouter les voisins un par un. Avec 0 voisins, le point est toujours un maximum, à moins qu'il s'agisse d'un maximum global, il existe un nombre maximum N de voisins pour lequel le point prend la plus grande valeur du voisinage.

Un test ultra naif consisterait à choisir une valeur de N (par exemple, si n>3, on dit que c'est un maximum local). Une approche plus saine consisterait à prendre en compte les valeurs prises par les voisins, et peut être à pondérer par les distances, pour obtenir une statistique, qui servirait de base à un test.

A ce stade tu as deux approches : les paramétriques (et donc Weibull) et les non paramétriques, et des dérivées du test de Wilcoxon (qui repose sur des rangs, donc probablement adaptables à des notions de maximum).

Francois

[FR119492]

Salut!

Si ce n'est pas là où tu veux en venir, je suis tout ouïe.

Le but est de mettre en évidence le caractère insoluble de ton problème. Voici maintenant une seconde série de valeurs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
0.000  0.1386
0.050  0.7474
0.100  1.1343
0.150  1.1610
0.200  0.8285
0.250  0.2772
0.300 -0.2660
0.350 -0.5718
0.400 -0.4907
0.450  0.0110
0.500  1.8421
0.550  1.1873
0.600  1.4118
0.650  1.3306
0.700  0.9098
0.750  0.2773
0.800 -0.3469
0.850 -0.7410
0.900 -0.7677
0.950 -0.4280
1.000  0.1387

Comme tu le vois, les maxima ne sont pas les mêmes que dans l'exemple précédent; et pourtant, il s'agit de la même fonction, soit:
f(x)=sin(4*pi*x)-0,1*ln(x-0,5001)^2
Cet exemple montre qu'en discrétisant une fonction, c'est-à-dire en ne considérant qu'un nombre fini de valeurs, on perd une partie de l'information et que cette partie peut être essentielle.
Jean-Marc Blanc

[koamh]

Cet exemple montre qu'en discrétisant une fonction, c'est-à-dire en ne considérant qu'un nombre fini de valeurs, on perd une partie de l'information et que cette partie peut être essentielle.
Jean-Marc Blanc

Ca, j'en suis bien conscient. Cela dit je ne peux pas me permettre, pour l'application qui m'interesse, de déterminer la fonction le plus finement possible. Pour des raisons de temps de calcul, je dois me contenter des points aléatoirement distribués, et choisir les maxima de ces points, et pas les maxima réels. Quite à tomber à côté des vrais maxima locaux.

(A la reflexion, je me demande si je ne pourrais rafiner mon problème pour avoir les vrais maxima, mais ceci est un autre problème.)

Si nous considérons qu'on a les vrais valeurs des maxima, le problème se pose toujours.

@françois : un grand merci à toi, je vais essayer de potasser tout ça, ça m'a l'air bigrement interessant.