Pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter, inscrivez-vous gratuitement !

 

  1. #1
    Chroniqueur Actualités

    Homme Profil pro
    Administrateur systèmes et réseaux
    Inscrit en
    juin 2016
    Messages
    179
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Bénin

    Informations professionnelles :
    Activité : Administrateur systèmes et réseaux
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : juin 2016
    Messages : 179
    Points : 6 054
    Points
    6 054

    Par défaut Des chercheurs de Harvard ont développé un nouvel algorithme d'optimisation

    Des chercheurs de Harvard ont développé un nouvel algorithme d'optimisation
    qui augmente de manière exponentielle la vitesse de calcul des ordinateurs

    Entre le temps de calcul qui peut s’avérer relativement long et les résultats qui ne sont pas toujours les meilleurs, les algorithmes d’optimisation semblaient avoir atteint leurs limites jusqu’à ce que des chercheurs de l'université Harvard décident de s’y pencher. Yaron Singer et Eric Balkanski, deux chercheurs de Harvard, ont développé un algorithme qui serait capable de résoudre les problèmes d’optimisation à un niveau de vitesse largement au-dessus de celui que les algorithmes existants peuvent atteindre. La méthode étape par étape qu’utilisaient les autres algorithmes avait déjà démontré qu’elle offrait des résultats de moins en moins bons le long des étapes.

    Les deux chercheurs se sont donc dit qu’ils pourraient grandement augmenter la vitesse de calcul de leur algorithme si le nombre d’étapes nécessaires était proportionnellement réduit. Le risque avec cette méthode, c’est qu’elle pourrait, elle aussi, grandement compromettre la qualité des résultats de l’algorithme. Les deux chercheurs de Harvard rassurent cependant qu’il n’en est rien. Ils annoncent que les résultats de leurs expériences ont montré que l’algorithme pourrait analyser 20 fois plus vite, un ensemble de données avec 1 million d'évaluations de 4 000 films de 6 000 utilisateurs et donner des recommandations de films similaires à des algorithmes de pointe.

    Nom : MzA4NTYyNw.jpeg
Affichages : 8629
Taille : 35,8 Ko

    L’algorithme serait aussi capable d’analyser plus de 2 millions de voyages en taxi de la compagnie de taxis et de limousines de New York pour déterminer, six fois plus vite que n’importe quel autre algorithme, les emplacements où les véhicules sont susceptibles de couvrir le plus de clients. Contrairement aux autres algorithmes qui n’analysaient que dans une seule direction, le nouvel outil échantillonnerait plusieurs directions parallèles à la fois ; ce qui aurait réglé le problème de la baisse progressive de la qualité des résultats le long des étapes. Les deux chercheurs disent avoir basé le fonctionnement de leur algorithme sur deux aspects spécifiques qu'ils ont dénommés « la courbure et l’homogénéité ».

    Ils ont expliqué ces deux aspects sur la base des recommandations de films et de la répartition des taxis. Ils disent qu’en matière de films, les objectifs avec des « courbures » élevées sont les films ressemblant beaucoup aux films qu’on a déjà vus et que les objectifs avec une grande « homogénéité » sont ceux qui sont du même genre que les films qu’on a vus. En matière de taxis, par contre, la « courbure » représente le temps de réactivité moyen des taxis dans une zone ; et l’homogénéité représente la répartition des clients entre les sites. Les deux chercheurs de Harvard finissent en disant que cet algorithme, du fait de l’accélération du temps de fonctionnement qu’il provoque, pourrait avoir des possibilités d’applications dans des domaines tels que la santé, la biologie, l’intelligence artificielle, etc.

    Détail de la recherche

    Source : IEEE Spectrum

    Et vous ?

    Que pensez-vous de ce nouvel algorithme d'optimisation ?

    Voir aussi

    Notes de cours Python scientifique : Apprendre l'optimisation du code avec Python

    Le Ministère de l'Enseignement Supérieur publie l'algorithme de Parcoursup à la veille de ses premières réponses

    OpenAI conçoit un algorithme basé sur l'IA qui permet à un robot d'imiter des tâches réalisées par des humains dans un environnement virtuel
    Contribuez au club : Corrections, suggestions, critiques, ... : Contactez le service news et Rédigez des actualités

  2. #2
    Membre habitué
    Inscrit en
    octobre 2005
    Messages
    96
    Détails du profil
    Informations forums :
    Inscription : octobre 2005
    Messages : 96
    Points : 137
    Points
    137

    Par défaut Super mais...

    Quasi impossible à mettre en œuvre de manière simple pour le commun des devs, il faut être un sacré gros matheux !

  3. #3
    Membre averti
    Inscrit en
    juin 2010
    Messages
    475
    Détails du profil
    Informations forums :
    Inscription : juin 2010
    Messages : 475
    Points : 395
    Points
    395

    Par défaut

    ça me f'ra de la lecture pour la semaine

  4. #4
    Membre expérimenté
    Homme Profil pro
    Développeur informatique
    Inscrit en
    avril 2017
    Messages
    371
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : avril 2017
    Messages : 371
    Points : 1 538
    Points
    1 538

    Par défaut

    Optimiser une fonction f, ça veut dire trouver le point x du domaine de f pour lequel la valeur f(x) est maximale.

    Donc ça n'a à peu près aucun rapport avec l'optimisation de code python, la publication de parcoursup ou l'algo de deep-learning d'openai.

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    février 2005
    Messages
    38
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : février 2005
    Messages : 38
    Points : 60
    Points
    60

    Par défaut

    j'ai pas trop pigé le rapport entre l'article et le papier du coup j'ai cherché un peu sur le net pour tomber sur ça:

    This is specifically talking about submodular function maximization problems. A submodular set function is a function f(S) that takes a set S and returns a "score". The objective is to find the set S with the highest score. The "submodular" property means that f(S) has "diminishing returns", meaning roughly that each new element contributes less to the score as the set S gets bigger. It turns out that this is hard to maximize exactly, but the simplest possible greedy algorithm already achieves an impressive approximation ratio of 1 - 1/e. The downside is that even the fully greedy algorithm is still pretty slow if you need to find a large set S, which is what this paper is addressing with a parallelizable randomized algorithm. (It's not the first such algorithm, but it's apparently much faster than the previous state of the art.)

    [disclaimer: not an expert in any of this]
    Submodular maximization is indeed NP-complete, but we can find approximate solutions in polynomial time. This paper speeds up the parallel running time of the approximation from O(n) to O(log n), meaning that they've found a way to make the algorithm more parallelizable, though you still have to do the same amount of work.
    source:https://news.ycombinator.com/item?id=17433525

    Je pense que ça explique bien mieux le papier des chercheurs.

  6. #6
    Membre chevronné
    Homme Profil pro
    Consultant Ingenierie mécanique
    Inscrit en
    mars 2006
    Messages
    948
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Consultant Ingenierie mécanique
    Secteur : Transports

    Informations forums :
    Inscription : mars 2006
    Messages : 948
    Points : 2 040
    Points
    2 040

    Par défaut

    quand je vois le terme "exponentielle" je me marre. c'est tellement galvaudé et ça correspond que très rarement au sens précis de ce mot... risible

  7. #7
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    23 484
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 23 484
    Points : 144 219
    Points
    144 219

    Par défaut

    Sauf qu'ici le mot est bien utilisé : cet algorithme permet de se débarrasser d'une exponentielle dans la complexité de résolution d'un problème — maximisation d'une fonction sous-modulaire monotone sur un ensemble discret assez simple — au prix d'une solution approchée plutôt qu'exacte.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  8. #8
    Membre éclairé Avatar de Matthieu76
    Homme Profil pro
    Consultant informatique
    Inscrit en
    mars 2013
    Messages
    477
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Consultant informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2013
    Messages : 477
    Points : 686
    Points
    686

    Par défaut Ici, c'est bien exponentielle !

    Citation Envoyé par Aiekick Voir le message
    quand je vois le terme "exponentielle" je me marre. c'est tellement galvaudé et ça correspond que très rarement au sens précis de ce mot... risible
    Oui mais dans l'article c'est il est question de log(x)/log(log(x)) et -log(x)/log(log(x)) tend plus rapidement vers +Inf que exp(x) donc le terme exponentielle est largement justifier ici.

  9. #9
    Nouveau membre du Club
    Profil pro
    Inscrit en
    janvier 2010
    Messages
    25
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : janvier 2010
    Messages : 25
    Points : 33
    Points
    33

    Par défaut Titre trompeur

    Le titre de l'article est « The Adaptive Complexity of Maximizing a Submodular Function ».
    Sauf que, quand on lit le papier, on voit qu'il s'agit du cas particulier « monotone submodular functions » (en gros, si f est définie sur des sous-ensembles et que A est inclus dans B, alors f(A)< f(B)).

  10. #10
    Membre averti
    Homme Profil pro
    Webdesigner
    Inscrit en
    juin 2014
    Messages
    189
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 58
    Localisation : France, Hautes Pyrénées (Midi Pyrénées)

    Informations professionnelles :
    Activité : Webdesigner
    Secteur : Associations - ONG

    Informations forums :
    Inscription : juin 2014
    Messages : 189
    Points : 386
    Points
    386

    Par défaut

    Bonjour. J'ai tiqué aussi sur le mot « exponentielle ». Sur une courbe exponentielle, on place une abscisse et une ordonnée. Que met ont-on ici dans ces deux coordonnées, puisqu'il n'est question que de « vitesse de calcul des ordinateurs » ?

  11. #11
    Membre éclairé Avatar de Matthieu76
    Homme Profil pro
    Consultant informatique
    Inscrit en
    mars 2013
    Messages
    477
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Consultant informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2013
    Messages : 477
    Points : 686
    Points
    686

    Par défaut

    Citation Envoyé par domi65 Voir le message
    Bonjour. J'ai tiqué aussi sur le mot « exponentielle ». Sur une courbe exponentielle, on place une abscisse et une ordonnée. Que met ont-on ici dans ces deux coordonnées, puisqu'il n'est question que de « vitesse de calcul des ordinateurs » ?
    C'est de la complexité algorithmique, il s'agit de minimiser le nombre d'instructions en fonction de la taille des données d'entrée. Et je parle de « nombre d'instructions » et non de « vitesse de calcul » car peu importe la vitesse du processeur, cela fonctionnera toujours. D'ailleurs il s'agirait plus d'une fonction avec 2 paramètres du genre z = f(x, y), le second paramètre étant le nombre de thread, même si ce paramètre semble linéaire : avec 1000 threads on va 10 fois plus vite qu'avec 100.

  12. #12
    Membre à l'essai
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2013
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Agroalimentaire - Agriculture

    Informations forums :
    Inscription : septembre 2013
    Messages : 12
    Points : 22
    Points
    22

    Par défaut

    Matthieu76 :

    log(x)/log(log(x)) tend plus rapidement vers +Inf que exp(x)
    Je ne vois pas trop ce que tu veux dire : vite fait sur Gnuplot, on a log(x)/log(log(x)) > exp(x) sur un tout petit domaine, entre 2.71 et 2.95

  13. #13
    Membre éclairé Avatar de Matthieu76
    Homme Profil pro
    Consultant informatique
    Inscrit en
    mars 2013
    Messages
    477
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Consultant informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2013
    Messages : 477
    Points : 686
    Points
    686

    Par défaut

    Citation Envoyé par Hervé Autret Voir le message
    Je ne vois pas trop ce que tu veux dire : vite fait sur Gnuplot, on a log(x)/log(log(x)) > exp(x) sur un tout petit domaine, entre 2.71 et 2.95
    J'ai écrit -log(x)/log(log(x)) et pas log(x)/log(log(x)) et -log(x)/log(log(x)) > exp(x) est vrai de environ 25000 à plus +l'infini.

    PS : Le signe - est là car vitesse = 1 / durée

  14. #14
    Membre à l'essai
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2013
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Agroalimentaire - Agriculture

    Informations forums :
    Inscription : septembre 2013
    Messages : 12
    Points : 22
    Points
    22

    Par défaut

    Citation Envoyé par Matthieu76 Voir le message
    J'ai écrit -log(x)/log(log(x)) et pas log(x)/log(log(x)) et -log(x)/log(log(x)) > exp(x) est vrai de environ 25000 à plus +l'infini.
    Ah bon. J'avais bien vu le moins mais je l'avais pris pour un signe de ponctuation.

    On s'intéresse donc à log(x)/log(log(x)) pour x tendant vers +infini

    Le numérateur = log(x) > 0 ==> x > 1

    Le dénominateur = log(log(x)) > 0 ==> x > e

    Intuitivement (soyons fou) : le dénominateur > 1, donc log(log(x)) >1, ce qui implique x > ee (soit environ 15.15).

    Et comme log(x)/log(log(x)) < log(x) pour tout x > ee, alors log(x)/log(log(x)) < exp(x) dans les mêmes conditions.

    Donc, voilà qu'il est faux que -log(x)/log(log(x)) > exp(x) pour x > 25000

    Citation Envoyé par Matthieu76 Voir le message
    PS : Le signe - est là car vitesse = 1 / durée
    Tu sembles assimiler division et changement de signe... Allez, je me lance : sors-tu d'une école de commerce ?

  15. #15
    Membre éclairé Avatar de Matthieu76
    Homme Profil pro
    Consultant informatique
    Inscrit en
    mars 2013
    Messages
    477
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Consultant informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2013
    Messages : 477
    Points : 686
    Points
    686

    Par défaut

    Pour te répondre :

    Si log(x) > 0 ==> x > 1

    Alors log(log(x)) > 0 ==> x > log(1) et non > à e , déjà ça c'est faux.

    Ensuite :

    clique ici

  16. #16
    Membre éprouvé
    Homme Profil pro
    F5(){F5}
    Inscrit en
    avril 2008
    Messages
    630
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : F5(){F5}
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : avril 2008
    Messages : 630
    Points : 988
    Points
    988

    Par défaut

    bj

    pour le lecteur inaverti.. Hervé manque de rigueur (pbmlt volontairement) mais la dem est correcte et niveau lycée.
    effectivement log/(logolog) croit moins vite que exp

    pour info
    log(log(x)) > 0 => log(x) > 1 (en composant par exponentielle, fct strct croissante sur R, des deux cotés)
    puis log(x) > 1 => x > e (de la même manière)


    Une manière plus grossière et succinte:
    log/(logolog) < log pour x assez grand (car logolog > 1 pour x assez grand)
    et log < exp par fonction comparée

    quant à -log(...) un peu de bon sens, si log/(logolog) est positive, -log/(logolog) est négative et de fait tjs inférieure à exp

    ----
    soit dit en passant la comparaison ne se fait pas sur log(x)/log(log(x)).
    Dans le papier (résumé)
    jusqu'avant la complexité adaptative était au mieux entre O(1) et O(n) et ils obtiennent O(log(n)) (avec solution approchée)
    bon... le passage de log(n) à n c'est exp d'où le terme de exponentially faster.

    à noter qu'apparemment on a (ils ont) amélioré le bound de la solution approché à 1-1/e
    https://arxiv.org/pdf/1804.06355.pdf

    après bon, j'en sais pas plus pour autant

  17. #17
    Membre éclairé Avatar de Matthieu76
    Homme Profil pro
    Consultant informatique
    Inscrit en
    mars 2013
    Messages
    477
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Consultant informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2013
    Messages : 477
    Points : 686
    Points
    686

    Par défaut

    Je soutiens que -log(x)/log(log(x)) croît plus vite qu’exponentielle de x.

  18. #18
    Membre éprouvé
    Homme Profil pro
    F5(){F5}
    Inscrit en
    avril 2008
    Messages
    630
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : F5(){F5}
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : avril 2008
    Messages : 630
    Points : 988
    Points
    988

    Par défaut

    Je soutiens que -log(x)/log(log(x)) croît plus vite qu’exponentielle de x.
    curieux de savoir d'où vient ton assurance?

  19. #19
    Membre éclairé Avatar de Matthieu76
    Homme Profil pro
    Consultant informatique
    Inscrit en
    mars 2013
    Messages
    477
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Consultant informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2013
    Messages : 477
    Points : 686
    Points
    686

    Par défaut

    Au temps pour moi.

    -log(x)/log(log(x)) tend vers +INF lors que x tend vers 10 et -log(x)/log(log(x)) tend extrêmement lentement vers -INF lors que x tend vers +INF.

    Désolé

Discussions similaires

  1. Réponses: 9
    Dernier message: 27/05/2016, 16h51
  2. Et si vous pouviez boire de l’alcool afin de résoudre des problèmes ?
    Par Stéphane le calme dans le forum Actualités
    Réponses: 11
    Dernier message: 30/12/2014, 09h11
  3. Résolution des problèmes d'optimisation
    Par MariaDV dans le forum Mathématiques
    Réponses: 1
    Dernier message: 05/05/2013, 17h28
  4. Réponses: 1
    Dernier message: 27/07/2011, 19h00

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo