CULTURA, CIENCIA, DIVULGACIóN
258 meneos
3381 clics
Una red neuronal diseña un algoritmo de ordenación que parece más rápido que el quicksort de Hoare

Una red neuronal diseña un algoritmo de ordenación que parece más rápido que el quicksort de Hoare

El aprendizaje automático con redes de neuronas artificiales se puede usar para optimizar algoritmos, la llamada inducción neuronal de programas. Se publica en arXiv un algoritmo de ordenación diseñado mediante aprendizaje con refuerzo que parece ser más eficiente que el algoritmo quicksort de C. A. R. Hoare; por supuesto, su complejidad computacional es la misma, O(n log n) operaciones, pero en los experimentos realizados con 100 secuencias aleatorias de 100.000 números el nuevo algoritmo requiere ~ 92 % del tiempo de ejecución de qu


| etiquetas: inteligencia artificial , redes neuronales , algoritmos de ordenación
128 130 3 K 285
128 130 3 K 285
Comentarios destacados:              
#15 #1 ATENCIÓN: La sugerencia de duple la he publicado yo. Iba dirigida a otra noticia. No me deja ni eliminar el comentario y cuando le he dado a editarlo me ha publicado los dos.
Para el que no entienda que es el quicksort: www.youtube.com/watch?v=ywWBy6J5gz8
#14 me acabo de hacer fan de esta mierda xD
Leyendo el paper me parece que no es exactamente correcto decir que la IA diseña el algoritmo, sino que más bien la IA es el algoritmo. Es decir, aplica la mejor operación en función de la entrada y de su entrenamiento, logrando una pequeña mejora en el tiempo total, y siempre para vectores de la misma longitud que los usados en su entrenamiento. La demostración matemática debería ser sobre el algoritmo en sí, por lo que se debería incluir el propio algoritmo de la red neuronal en la demostración, cosa que ya se me escapa pero parece bastante complicado, aunque como dice el artículo, no imposible.
#28 el mérito es poder entrenar una red neuronal para alterar algoritmos. El que haya conseguido resultados o no es secundario, no invalida el valor del trabajo.
Bueno, lo matiza ahora #30 . Mi gozo en un pozo.
#53 Realmente tampoco, dado que dicen que usan "aprendizaje automático", o sea, se les da entradas, se les dice cuál tiene que ser el resultado y la red neuronal se ajusta internamente hasta que el porcentaje de error con datos del conjunto de validación es lo suficientemente pequeño. Si acaso el mérito es darle un conjunto de datos de prueba y validación de suficiente calidad y en suficiente cantidad.
#44 un algoritmo de caja negra es uno que funciona, pero no sabes lo que hace, o no puedes describir su funcionamiento formalmente.

Una Red neuronal si se puede describir, pero el proceso interno por el que un valor x le corresponde la posición n, es totalmente opaco al investigador.

Es el gran problema al que nos estamos enfrentando en la informática teórica, quizá nuestra frontera actual: tenemos una herramienta eficaz que no sabemos cómo funciona.
Habría que comprarlo también con Timsort, el cual a día de hoy es muy utilizado y en muchos casos más rápido que Quicksort.

Esto se debe a que supone que los datos generados por la naturaleza o por los humanos no son 100% aleatorios, sino que puede tener partes ya ordenadas las cuales no hay que tratarla.

Si con ésto se consigue no sólo un algoritmo de ordenación, sino una forma de conseguir tales algoritmos dependiendo del tipo de datos usados, quizá podría ser sería un gran avance (que alguien que sepa más me corrija si no estoy en lo cierto).
#17 diría que con una red neuronal siempre vas a poder conseguir también algoritmos más específicos. Eso sí, tendrías que entrenarla con secuencia de datos de esa índole.

La cuestión es si existe un algoritmo de ordenación general tan óptimo, que prácticamente le de igual el tipo de datos a tratar/secuencia de inserción.
La aportación del artículo original no es el algoritmo de ordenación, sino la forma de llegar a él.
El futuro
Las redes neuronales, el grafeno de menéame 2020.
#10 Comentario cuñado del día xD

La implantación de las redes neuronales hoy en día son enormes, de hecho es probable que en tu día a día te sirvan y no lo sepas, cuando se use el grafeno un 1% en comparación con las redes neuronales ya será un auténtico éxito para los grafe fan boys.
#41 y así es como skynet tomará cociencia
Podría admitirse una demostración como la del Teorema de los Cuatro Colores.
#11 no se como se hace. De hecho, en vez de editarla me ha publicado los dos comentarios.
#22 Pero en que menú? En privados no va. Además ya dijeron hace tiempo que no se podía eliminar comentarios.
www.meneame.net/notame/1171295
#56 lo he dicho bien. Si hay dependencia probabilistica es mayor.
No merece la pena, obviamente.
#46 tampoco. Si la posibilidad de fallo de cada uno es 1/ 1000, la posibilidad de que fallen los dos a la vez es 1/1000000 o incluso mayor.
#54 Dirás, o incluso menor. Por tanto, hay más probabilidad de que sea correcta.
#35 No, dos algoritmos con dos coches :-P

Era por poner un ejemplo manejable, hombre, no conozco hasta qué punto estás en el mundillo o no xD
Empieza a peligrar mi curro
#26 Logística ?
#26 tu curro consiste en ordenar números? de ser así te diría que lleva unas cuantas décadas peligrando ^_^'
Propuesta de mejora a los admin: se desactiven automáticamente los comentarios éstos dumies de "es el año de linux en el escritorio", " se viene skynet", etc.
Coñazo siempre la misma gracieta. Parecen el Nelson de los Simpsons con el "HA HA!!"
No aportan nada de valor a la información de la noticia y como gracieta ya... :palm:
Del articulo...
"Sin embargo, hay un pero. Por desgracia, no se puede demostrar matemáticamente que el nuevo algoritmo funcione de forma correcta (los autores prometen intentar lograrlo en el futuro). " ... sensacionlaista
¿No lo habrán probado con listas casi ordenadas? :-D
que le pasen la ia a la web de renfe a ver si la optimiza :troll:
#18 no podrían garantizar que funcione, pero en este caso no es un problema
Siento aguar la fiesta, pero hay una demostración matemática que confirma que la forma más rápida de ordenar implica un coste de N*log(N) .

Quicksort no es el único algoritmo que puede ordenar en ese tiempo, aunque sí es de los más usados.

Así que la cosa suena un pelín sensacionalista.

Y para dejarlo claro, soy programador desde hace más de una década, también me dedico al aprendizaje automatico.
#48 el artículo así lo indica.
en matematicas no hay parecidos. o es mas rapido, o no lo es.
#19 No es así, el quickcsort es más rápido en muchas ordenaciones, no en todas.
#19 Formalmente, "ambos juegan en la misma liga" de velocidades, ambos son capaces de ordenar a una velocidad que es proporcional a la cantidad de datos (en otros algoritmos, por ejemplo, la velocidad decrece mucho más rápido que el aumento de la cantidad de datos). Por eso se dice que son parecidos.

Luego, en la photo finish, parece que el algoritmo "inventado" es un pelín más rápido que el quicksort, pero ni se sabe por qué, ni se sabe si siempre dará…   » ver todo el comentario
#28 De verdad comparas un algoritmo con un coche? xD xD xD
#5 #19 esto no son matemáticas, es deep learning. Un conjunto de recetas de cocina que, combinadas con un aprendizaje basado en pseudo-fuerza bruta, funcionan algo mejor que todo lo que se había hecho hasta ahora.

Ya no necesitamos demostraciones formales en aprendizaje computacional, como pasaba en los viejos tiempos de grandes como Vladimir Vapnik y Alexey Chervonenkis.

:troll:
Está en un idioma raro, lástima (y paso del traductor en estos ámbitos)
#21 @theolokun me has votado negativo sin contestar o comentar en contra a mi comentario. No me parece nada bien.
Yo no he faltado a nadie, simplemente he dado una opinión ya que me cuesta mucho entender temas de programación y matemáticas en otras lenguas, mira chico que le vamos a hacer...
Te devuelvo el negativo, pero si quieres podemos contrastar opiniones y aquí no ha pasado nada.
#34 ni me he dado cuenta que te he votado negativo. No era mi intencion. Toma te doy un positivo para compensar
#37 Joder, ahora me siento fatal, disculpa, yo hago lo mismo y perdona, que mal me sabe...
Parece = no noticia.
#5 Es uno de los problemas de la IA; experimentalmente se ha comprobado que el algoritmo es más eficiente, pero no está demostrado matemáticamente... [mode sheldon off]
#6 La complejidad asíntotica es la misma, el tiempo no debe ser muy diferente. Para comprobar cuál es más rápido lo tienes que hacer experimentalmente porque dependerá en parte de la implementación y de la máquina.
En teoría son iguales pero en la práctica parece que sí se nota la diferencia.
Lo que no han demostrado aún es si es correcto. Lo que no se es si ha generado un "algoritmo" o una red neuronal (que también bsenouede ver cómo un algoritmo.
Lo que sí creo que es importante es haber obtenido un resultado tan bueno con redes neuronales para un problema tan aleatorio y concreto.
#8 a mi me da la impresión de que el algoritmo ha aprendido a cambiar de criterio de ordenación en función de la muestra o de la iteración que se encuentra.

Pero como es caja negra... Quien sabe!!!
#43 La muestra se supone que es aleatoria. Pero si no recuerdo mal quickshort usaba un pivote aleatorio, puede haber cambiado los parámetros o jugar con algo.
Caja negra entiendo que no, si es una red neuronal es un conjunto de valores. Otra cosa es que sí es un lío sacar una lógica de qué hace dentro.
#44 cualquier red neuronal multicapa con un numero decente de neuronas = no la vas a entender. Estoy con #43 el que prácticamente cualquier red neuronal ya entrenada es como una caja negra.

Para poder entenderla mas o menos, tendrias que tirar mas de la parte de aprendizaje y retropropagacion. Sinceramente, te seria más viable entender un ejecutable entero de 10MB desensamblandolo y analizando el ensamblador... que entender la mayoría de redes neuronales con uso practico/real (no usos de ejemplo académicos con tres capas y 5 neuronas...).
#6 Teniendo en cuenta que el 99,9% de los humanos usan/usamos la tecnología sin entender en profundidad cómo funciona, creo que no saber qué narices hace el algoritmo importa bien poco. El caso es que es útil.
#41 El problema es otro. Al no haber una demostración matemática de que el algoritmo funciona sólamente disponemos de datos experimentales. El algoritmo de Hoare está comprobado y demostrado. Funciona. Sin una demostración matemática que prueba de forma irrefutable que el algoritmo hace lo que debe en un tiempo óptimo, puede ser que el día de mañana se encuentre un extraño caso en el que no funcione o su tiempo sea terrible, por ejemplo podría fallar si resulta que no ordena correctamente…   » ver todo el comentario
#45 Vale. Hagamos 2 algoritmos caja negra, con IAs para una misma tarea. En procesos críticos usaremos ambos, y si el resultado coincide, lo damos por bueno.
Imagino que la primera réplica es que tardamos el doble, y estoy de acuerdo. Pero y si no existe ningún otro algoritmo disponible para esa tarea en particular?
#41. Es como si la propia evolución biológica hubiera escrito tu comentario. Los cinco sentidos humanos son buena prueba de lo que afirmas si no se estudia medicina (y ni con esas).
(CC #6)
#6 es el problema de los algoritmos de caja negra.

Yo no lo considero ni siquiera un algoritmo de ordenación, sino un algoritmo que se comporta COMO un algoritmo de ordenación.

Efectivamente, un algoritmo de ordenación es un constructo matematico al servicio de la computación, y no al revés.
#5 Eso me pareció a mi. :troll:
#5 Es una noticia.
Hay una teoría que demuestra la complejidad de un algoritmo común y de forma empírica se ha demostrado que tal complejidad podría ser menor lo que lleva a la siguiente pregunta para averiguar el porqué pues experimentalmente se debería haber llegado a la misma conclusión que lo que la teoría dice, y no es el caso.
#1 Gambas es un lenguaje de programación, pero no veo la relación... ?(
#3 yo diria que #1 ha metido la gamba </Matias Prats mode>
#3 era la noticia de despues. Le he dado a editar pero se lo pasa por el forr* y no se como eliminar comentarios
#9 llama a un @admin
#1 ATENCIÓN: La sugerencia de duple la he publicado yo. Iba dirigida a otra noticia. No me deja ni eliminar el comentario y cuando le he dado a editarlo me ha publicado los dos.
#15 Creo que para avisar a un admin tienes que llamarlo así: @admin.

menéame