Hola usuario de nuestra web, tenemos la respuesta a lo que buscabas, has scroll y la encontrarás un poco más abajo.
Solución:
Como se discutió en los comentarios, aquí hay una idea para un algoritmo codicioso. Básicamente, el objetivo es encontrar iterativamente el rectángulo que minimizará $ | w-w ‘| $ en esa situación particular. Una combinación de un subarreglo máximo y un algoritmo de subarreglo mínimo encuentra un rectángulo que se acerca bastante, si usa el promedio sobre el subarreglo resultante como $ a_i $. El único problema es que los valores por debajo de ese promedio (o por encima, para rectángulos negativos) ya deberían contar como negativos (positivos); No sé si hay una forma sencilla de resolver esto (y también es un poco difícil de explicar). Una forma de reducir este problema es recortar el rectángulo si eso mejora el resultado. Otra es limitar la longitud del rectángulo, ya que los rectángulos más largos tienden a tener un mayor porcentaje de valores por debajo del promedio. Puede haber mejores opciones, posiblemente dependiendo de la forma de la señal.
De todos modos, necesitaba experimentar con esto para averiguar si realmente funciona, así que aquí hay algo de código (en C, pero debería ser fácil de transferir):
/* Type of index into signal. */
typedef unsigned int Index;
/* This should be a floating-point type. If you decide to use integers, change
the division to round away from zero instead of towards zero. */
typedef double Value;
/* Represents a rectangle at [start,end). */
typedef struct
Index start, end;
Value height;
Rectangle;
/* Trims the rectangle by removing samples whose absolute value will increase
when preliminaryHeight is subtracted. */
static Index optimizeRectangle(const Value signal[], Rectangle *rectangle, Value preliminaryHeight)
Index result = 0;
/* Divided into two cases for better efficiency. */
if (preliminaryHeight >= 0)
while (rectangle->start + 1 < rectangle->end)
Value value = signal[rectangle->start];
if (preliminaryHeight - value < value)
break;
rectangle->start++;
rectangle->height -= value;
result++;
while (rectangle->start + 1 < rectangle->end)
Value value = signal[rectangle->end - 1];
if (preliminaryHeight - value < value)
break;
rectangle->end--;
rectangle->height -= value;
result++;
else
while (rectangle->start + 1 < rectangle->end)
Value value = signal[rectangle->start];
if (preliminaryHeight - value > value)
break;
rectangle->start++;
rectangle->height -= value;
result++;
while (rectangle->start + 1 < rectangle->end)
Value value = signal[rectangle->end - 1];
if (preliminaryHeight - value > value)
break;
rectangle->end--;
rectangle->height -= value;
result++;
return result;
/* Finds the rectangle that seems most appropriate at the moment, and whose
length is at most maxResultLength.
Returns the original length of the rectangle, before optimization. This
value should be used for maxResultLength in the next iteration. If it is
zero, the entire signal was zero. */
static Index findRectangle(const Value signal[], Index signalLength, Rectangle *result, Index maxResultLength)
result->start = result->end = 0;
result->height = 0;
Value resultHeightAbs = 0;
/* Start index and height of current maximum and minimum subarrays. */
Index posStart = 0, negStart = 0;
Value posHeight = 0, negHeight = 0;
for (Index index = 0; index < signalLength; index++)
/* If the length of a subarray exceeds maxResultLength, backtrack
to find the next best start index. */
Index nextIndex = index + 1;
if (nextIndex - posStart > maxResultLength && index > 0)
Index oldStart = posStart;
posStart = index;
posHeight = 0;
Value newHeight = 0;
for (Index newStart = index - 1; newStart > oldStart; newStart--)
newHeight += signal[newStart];
if (newHeight > posHeight)
posStart = newStart;
posHeight = newHeight;
if (nextIndex - negStart > maxResultLength && index > 0)
Index oldStart = negStart;
negStart = index;
negHeight = 0;
Value newHeight = 0;
for (Index newStart = index - 1; newStart > oldStart; newStart--)
newHeight += signal[newStart];
if (newHeight < negHeight)
negStart = newStart;
negHeight = newHeight;
/* Extend the subarrays. */
Value value = signal[index];
posHeight += value;
negHeight += value;
/* Throw away the entire maximum subarray if it is negative or zero. */
if (posHeight <= 0)
posStart = nextIndex;
posHeight = 0;
else
/* Update result if current maximum subarray is better. */
if (posHeight > resultHeightAbs)
result->start = posStart;
result->end = nextIndex;
result->height = posHeight;
resultHeightAbs = posHeight;
/* Throw away the entire minimum subarray if it is positive or zero. */
if (negHeight >= 0)
negStart = nextIndex;
negHeight = 0;
else
/* Update result if current minimum subarray is better. */
Value negHeightAbs = -negHeight;
if (negHeightAbs > resultHeightAbs)
result->start = negStart;
result->end = nextIndex;
result->height = negHeight;
resultHeightAbs = negHeightAbs;
Index resultLength = result->end - result->start;
if (!resultLength)
/* Return now to avoid division by zero. */
return 0;
/* Trim rectangle. */
Value normalizedHeight;
Index trimLength;
do
normalizedHeight = result->height / (result->end - result->start);
trimLength = optimizeRectangle(signal, result, normalizedHeight);
while (trimLength);
/* Normalize height. */
result->height = normalizedHeight;
return resultLength;
/* Subtracts a rectangle from a signal. */
static void subtractRectangle(Value signal[], const Rectangle *rectangle)
for (Index index = rectangle->start; index < rectangle->end; index++)
signal[index] -= rectangle->height;
/* Decomposes a signal into rectangles. Stores at most resultLength rectangles
in result, and returns the actual number of rectangles written. All
rectangles are subtracted from the signal. */
unsigned int extractRectangles(Value signal[], Index signalLength, Rectangle result[], unsigned int resultLength)
Index rectangleLength = signalLength;
for (unsigned int resultIndex = 0; resultIndex < resultLength; resultIndex++)
Rectangle *rectangle = &(result[resultIndex]);
rectangleLength = findRectangle(signal, signalLength, rectangle, rectangleLength);
if (!rectangleLength)
return resultIndex;
subtractRectangle(signal, rectangle);
return resultLength;
La función principal es extractRectangles. Devuelve los rectángulos como un array, pero esto se puede adaptar fácilmente. Divertirse.
Estimados Raskolnikov, Brian y Sebastian, muchas gracias por compartir sus ideas.
Publiqué mi pregunta en dos foros, por lo que puede consultar la discusión completa mirando aquí y aquí.
De la discusión obtuve tres elementos principales:
- Haar wavelet proporciona una solución a mi problema, aunque muy subóptima
- Este problema podría resolverse mediante un enfoque de búsqueda de coincidencia similar (pero debe evitarse la enumeración completa del diccionario de bases, porque es demasiado grande en mi problema)
- Sebastian Reichelt proporcionó código para un enfoque basado en la búsqueda de subarreglos máxima y mínima
En general, terminé con cuatro soluciones diferentes al problema presentado:
explore_aindica mi solución original sugerida en cuestión (cuantificar los valores $ a_i $ y resolver múltiples problemas de subarreglos máximos)brute_forceindica el enfoque basado en aproximar $ left | w '- w right | $ por $ left (w' - w right) ^ 2 $. En este enfoque, resulta que cada posibilidad de rectángulo se puede evaluar con solo dos lecturas de memoria, una multiplicación y una división, lo que hace que una exploración de fuerza bruta sea manejable.reicheltindica un puerto del código de Sebastian a Python (que usé para probar las ideas)abs_maxindica un enfoque en el que en cada iteración se selecciona un rectángulo de un solo elemento, colocado en el valor absoluto máximo de la señal.
Todo el código que implementa estos métodos y algunos resultados de ejemplo están disponibles en http://lts.cr/Hzg
En cada ejecución, el código generará una nueva señal "aleatoria" (con un paso ruidoso). Una señal de ejemplo (etiquetada a[0:n]) y el primer rectángulo seleccionado por cada método se puede ver a continuación. Señal de ejemplo http://lts.cr/adL
Luego, cada método se ejecuta de forma recursiva para aproximar la señal de entrada, hasta que el error de aproximación sea muy bajo o se haya alcanzado el número máximo de iteraciones.
En el resultado típico se puede ver a continuación (y otro aquí) Resultado de ejemplo 1 http://lts.cr/adT
Después de ejecutar el código varias veces (para diferentes señales aleatorias), el comportamiento parece consistente:
- Como era de esperar,
abs_maxalcanza la convergencia en un número de iteraciones igual a la longitud de la señal. Lo hace bastante rápido (decaimiento exponencial). explore_aDisminuye la energía rápidamente al principio y luego tiende a estancarse.reicheltes consistentemente peor queexplore_a, quedando atascado en un nivel de energía más alto. Espero no haber cometido ningún error tonto en el puerto de C a Python. Por inspección visual, el primer rectángulo seleccionado parece razonable.brute_forceconsistentemente es el método que disminuye la energía más rápido. También se cruza consistentemente con elabs_maxsolución, lo que indica que una mejor estrategia sería cambiar de un método a otro.
Obviamente, el comportamiento exacto cambia de una ejecución a otra y ciertamente cambiaría dependiendo del método utilizado para generar la señal "aleatoria". Sin embargo, creo que estos resultados iniciales son un buen indicador. Siento que es razonable ahora proceder a generar mis datos reales y evaluar qué tan bien / rápido brute_force y explore_a correr allí.
Siéntase libre de agregar comentarios o jugar con el código.
Una vez más, ¡muchas gracias por sus aportes y conocimientos!
Experimenté un poco con su código y encontré tantas cosas que pensé que debería publicar otra respuesta:
-
Como se indica en un comentario, cometió un error cuando transfirió mi código. (Por cierto, quise decir "convergencia" en lugar de "conversión", por supuesto).
-
los
explore_ala función no hace lo que dice en la lata (así que también lograste descifrar tu propio código, supongo :-)). Dado que utiliza directamente el valor del subarreglo máximo como puntuación, solo las dos instancias dea_valuemás cercanos a cero se toman. En su lugar, debe calcular el efecto en $ | w-w '| $. -
Tampoco coincide con tu descripción: true efecto de
a_valuees que convierte muestras positivas a continuacióna_valueen muestras negativas (y niega la array si es negativo). Sin embargo, esta es en realidad una buena solución para el problema que traté de describir en mi primera respuesta. Entonces decidí arreglar el código; ahora parece funcionar muy bien. -
También creo que el cero siempre debe probarse como un
a_value, tanto con como sin negar la señal (que es equivalente a encontrar el subarreglo máximo y mínimo, de manera similar a mi primer algoritmo). -
Esto se puede combinar tanto con la restricción de longitud como con el recorte, como se describe en mi primera respuesta. La restricción de longitud resulta en peores resultados y también es bastante cara. El único efecto positivo es que se degrada al algoritmo de "valor absoluto máximo" una vez que la longitud máxima se convierte en 1, por lo que alcanza la convergencia más rápidamente. El recorte tiende a ayudar un poco, pero (como en todos los algoritmos codiciosos) un mejor resultado en un paso puede conducir a peores resultados en los siguientes pasos.
Aquí hay un gráfico actualizado (de una señal diferente, ya que lamentablemente no usaste semillas aleatorias fijas, y con diferente orden y colores porque se eligen automáticamente):
explore_a está escondido detrás explore_a_opt (es decir, con recorte), y explore_a_len (con restricción de longitud) está oculto detrás explore_a_len_opt.
Al observar este gráfico, me vienen a la mente algunas cosas más:
-
El fijo
explore_aparece producir mejores resultados quebrute_force(que en realidad es un nombre engañoso porque realmente sigue siendo un algoritmo codicioso, solo con fuerza bruta en cada paso). Supongo que esto significa quebrute_forcetampoco hace lo que se supone que debe hacer. -
La señal de prueba no es particularmente adecuada para la aproximación usando rectángulos. Es esencialmente ruido blanco con dos rectángulos agregados. Una vez que los algoritmos han "encontrado" estos rectángulos, no pueden hacer nada mejor que
abs_maxya no. -
Probablemente tenga más sentido comparar los algoritmos en un número de pasos que sea significativamente menor que la longitud de la señal. (De lo contrario, ¿cuál es el punto?)
Entonces, aquí hay un gráfico que pertenece a una señal de longitud 500 con más contenido de baja frecuencia, que muestra los primeros 100 pasos:
Finalmente, dado que todos los algoritmos son codiciosos, creo que también debería compararlos con algo como el recocido simulado (como mencioné en los comentarios).