Encuentra el número óptimo de videoclips para ver (dependiendo de la longitud) para obtener puntos máximos.

Question

Problema: Cómo encontrar el número óptimo de clips de vídeo para ver (dependiendo de la longitud) para obtener el Máximo de puntos.

Descripción: solicito clip de vídeo, entonces tengo dos opciones: a ver (pasar tiempo) y recibir puntos o a saltar y a no recibir puntos (para no gastar el tiempo).
Tiempo de espera entre el nuevo vídeo de 5s.

(Esta es la estadística histograma donde (eje Y es el número de vídeos, el eje X es la duración del vídeo)

Limitaciones && Supuestos:
- No sabemos videos previamente (por eso he reunido los datos para construir un histograma de estadísticos para conocer sus probabilidades.)
- Cuando nos saltamos el clip de vídeo que no podemos perder puntos.
Sí sabemos que la duración del vídeo antes de verlo.
- Recibimos puntos para ver el vídeo completo.
- Recibimos la misma cantidad de puntos para cada vídeo.

Así que, básicamente, tenemos que saltar esos videos que son largas y ver esos videos con una longitud óptima. (también conocido como encontrar la forma de maximizar los puntos por unidad de tiempo)

Answer 1

Voy a suponer que el suministro de videos es ilimitado y cada vídeo es un valor de 1 punto (oferta limitada haría que el problema de forma significativa más difícil).

Lo que queremos es maximizar los puntos ganados por unidad de tiempo. Es más fácil (equivalente) reducir al mínimo el tiempo necesario para obtener un punto. Ya que esto es aleatorio, vamos a minimizar el tiempo de espera necesario para ganar un punto. Nuestra estrategia sería para ver todos los vídeos que no son más que algunos de los tiempo máximo $m$.

Por lo tanto, si conocemos $m$, ¿cuál es el tiempo necesario para obtener un punto? En primer lugar, tenemos que esperar 5 años para cada uno de los vídeos que tenemos más de $m$. Entonces, tenemos que ver el video que tenemos que es el más corto de $m$.

La probabilidad de obtener un video largo (y por lo tanto saltar) puede ser calculado a partir del histograma. Permite llamar a ese $p_m$. A continuación, el número de vídeos que vamos a saltar sigue una distribución binomial negativa con $r=1$ y la probabilidad de $p_m$. El número esperado de salta es así $\frac{p_m}{1-p_m}$.

Del mismo modo, a partir del histograma podemos calcular la espera de la duración del vídeo, dado que es en la mayoría de las $m$.

Por lo tanto, si $L$ denota la duración del vídeo, nuestro tiempo dedicado a cada punto es $T(m) = 5\sec\frac{p_m}{1-p_m} + \mathbb{E}[L | L \leq m]$.

Ahora queremos minimizar $T(m)$. Se pueden calcular mediante nuestro histograma si se les da $m$. Aunque no tenemos una forma cerrada de expresión, sólo tenemos un único parámetro, $m$, que toma valores entre 0 y 1000, así que no debería ser difícil para optimizar, podemos utilizar una simple rejilla de búsqueda para encontrar el mejor $m$.

Nota adicional: No podría ser una formulación alternativa, donde en lugar de la maximización de los puntos ganados por unidad de tiempo, tenemos un duro límite de tiempo para ver vídeos y se desea maximizar la puntuación total. Si el límite de tiempo es grande, la de arriba es una buena aproximación. Pero para un pequeño límite de tiempo, el problema se vuelve significativamente más difícil. En ese caso, el umbral óptimo podría cambiar con el tiempo restante. Podemos tratar de hacer frente a ese caso por la definición de dos funciones de $S(t)$, lo que da el óptimo resultado esperado si tenemos tiempo $t$, e $m(t)$, la duración del video umbral como una función del tiempo. Entonces tenemos, $S(t) = S(t-5)\mathbb{P}[L>m(t)] + \mathbb{E}[S(t-L) + 1|L\leq m(t)]\mathbb{P}[L\leq m(t)]$. A continuación, podemos utilizar programación dinámica para encontrar $m(t)$ e $S(t)$.

Answer 2

He escrito una pequeña herramienta de simulación en Python (código agregado al final de este post). Calcula el número de vídeos que se pueden ver en una semana:

El azul es la media, la roja es una medida de la simulación de error. Vamos a acercar alrededor del pico (dejando x de ejecución de 45 a 55, y aumentar el número de repeticiones):

Esto sugiere que usted debe ver vídeos de en la mayoría de los 49 segundos y saltar los vídeos de 50 segundos o más. Esta conclusión depende de los datos de entrada.

data = """31
31
[removed for brevity]
897"""

data = [int(duration) for duration in data.split("\n")]

import random
def get_random_video():
    return random.choice(data)

def average(x):
    return sum(x) / float(len(x))

def std(x):
    avg = average(x)
    avgsq = average([i*i for i in x])
    return (avgsq - avg*avg) / float(len(x))

simulation_duration = 3600*36 # one week
replications = 10
x = range(31,897)
y = []
y_std = []

for threshold in x:
    points_threshold = []
    for replication in range(replications):
        time = 0
        points = 0
        num_videos = 0
        while time < simulation_duration and num_videos < 100000:
            video = get_random_video()
            if video<=threshold:
                points += 1
                time += video
            time += 5
            num_videos += 1
        points_threshold.append(points)
    y.append( average(points_threshold) )
    y_std.append( std(points_threshold) )

from math import sqrt
y_err_1 = [x[0] - 2*x[1]/sqrt(replications) for x in zip(y,y_std)]
y_err_2 = [x[0] + 2*x[1]/sqrt(replications) for x in zip(y,y_std)]

import matplotlib.pyplot as plt
plt.plot(x,y,'b')
plt.plot(x,y_err_1,'r')
plt.plot(x,y_err_2,'r')
plt.xlabel('watch video if shorter than (s)')
plt.ylabel('expected videos seen per week')
plt.show()

Answer 3

Bueno, aquí están los datos, excepto los clasificados. Ahora, queremos maximizar los puntos, sí. Y que tenemos que ver un video de, digamos, 1 punto. (Se dice un número constante de puntos, digo yo que ya que este es el único método y cualquier cantidad de puntos es un múltiplo de, sin embargo, muchos puntos este método da.) Por lo tanto, tenemos todos estos vídeos, con una duración promedio de... Bueno, así que hay 2905 elementos de la lista. Restar 1, dividir por 2, añadir 1, que es el 1453rd elemento, que es igual a 49. La mediana es de 49. Y a partir de un simple programa que yo he escrito, la suma de todos los elementos es 252464. Niza, dos concatenados palíndromos, ahora dividir por 2905 y tenemos una media de 86.9! Ahora, agregue 5 segundos (el tiempo entre vídeos) para ambos de estos, y tenemos 54 y 91.9 para la mediana y la media. Ahora, desea omitir los videos que le dan un bajo número de puntos, y porque no necesitamos aprender cómo los números se comparan entre sí, sólo para el promedio, se puede tirar de la mediana de la ventana. Así que... Espera, esto es difícil.

Bueno, ahora he utilizado una hoja de cálculo, y se encontró todo tipo de interesantes piezas de metadatos, pero fue en vano. Todo lo que puedo decir por ahora es que cualquier cosa con menos de 87 segundos es probablemente vale la pena "mirando", y si es en la parte inferior 25 percentiles (es decir. 40 o menos), luego ir a por ello. Y esta recompensa de su bien ganada reputación borrará toda culpa.

Answer 4

Su estrategia claramente tiene que ser para establecer una longitud de $L$, aceptar todos los vídeos de menos de eso y rechazar todos los videos más largos. Dada una propuesta de $L$ puede calcular el promedio de la longitud que usted va a aceptar, $M$ y la probabilidad de $p$ rechazó el siguiente. Su tiempo medio de espera es $5(p+p^2+p^3+\ldots)=\frac{5p}{(1-p)}$ debido a que esperas $5$ segundos con una probabilidad de $p$, otro $5$ segundos con una probabilidad de $p^2,$ y así sucesivamente, por lo que su promedio de tiempo para terminar un vídeo es $M+\frac{5p}{(1-p)}$

Al aceptar los videos más largos, $M$ aumentará, pero $p$ disminuirá. Usted está buscando para establecer $L$ para el equilibrio de este. Como un ejemplo, supongamos que (yo estoy haciendo los números) que si se establece $L=100$ el promedio de vídeo que aceptar es $60$ segundos, y usted acepta la $40\%$ de los videos. El promedio de tiempo para terminar uno es, a continuación, $60+\frac {5\cdot 0.4}{1-0.4}\approx 63.333$ segundos. Si aumenta el $L$ a $110$ y aceptan $62\%$ de los vídeos, el promedio de la longitud de reloj ahora es $\frac {20\cdot 60+105}{21}\approx 62.143$ y el tiempo de espera disminuye a $\frac {5\cdot 0.38}{1-0.38}\approx 3.064$. Claramente esta es una mala comercio y que debe buscar en la disminución de $L$ por debajo de $100$.

Answer 5

Según tengo entendido hay una espera de 5 segundos para los dos videos que usted puede observar y aquellos que no lo veas. Algunos de los carteles parecen pensar de manera diferente. El uso de los datos como dado, un simple ¿Qué pasa Si la tabla en Excel sugirió que sólo viendo videos de menos de 43.

Traté de ajuste de distribuciones para el histograma, pero nada, he intentado funcionado demasiado bien. Pero digamos que la distribución de vídeo longitudes podría ser aproximada por una distribución de probabilidad continua $p(l)$. Luego se le da un corte de $L$ el número de clips visto iría como $\int_0^L p(l) dl$ y el tiempo total de observación de ellos se van como $5 +\int_0^L l p(l) dl$. Crear el reloj de la tasa por la formación de la relación de los dos. La diferenciación de w.r.t. $L$ encontrar el máximo da la siguiente ecuación ($5 +\int_0^L l p(l) dl)=L \int_0^L p(l) dl$. Para más factible distribuciones de esto no va a tener una solución de forma cerrada, de modo que es mejor que se pegue a la hoja de cálculo.