java for deep - Как подойти к алгоритму угадывания номера (с помощью твиста)?





2 Answers

Эту проблему решить невозможно.

Предположим, что вы точно знаете, какое количество элементов было увеличено, а не только то, что для этого максимальное отношение.

У пользователя есть N плодов, и у вас есть D дней угадывания.

В каждый день вы получаете N новых переменных, а затем у вас есть полные переменные D * N.

За каждый день вы можете генерировать только два уравнения. Одно уравнение - это сумма цены n_item *, а другая - на известном соотношении. В целом у вас есть не более 2 * D уравнений, если они все независимы.

2 * D <N * D для всех N> 2

learning machine library

Я изучаю программирование (Python и алгоритмы) и пытался работать над проектом, который мне интересен. Я создал несколько базовых сценариев Python, но я не уверен, как подойти к решению игры, которую я пытаюсь создать.

Вот как игра будет работать:

Пользователям будут предоставлены предметы со значением. Например,

Apple = 1
Pears = 2
Oranges  = 3

Затем они получат возможность выбрать любую комбинацию из них (например, 100 яблок, 20 груш и один апельсин). Единственный результат, который получает компьютер, - это общее значение (в этом примере это сейчас $ 143). Компьютер попытается угадать, что у них есть. Который, очевидно, не сможет правильно разобраться в первом повороте.

         Value    quantity(day1)    value(day1)
Apple      1        100                100
Pears      2         20                 40
Orange     3          1                  3
Total               121                143

Следующий поворот пользователя может изменить их количество, но не более 5% от общего количества (или некоторых других процентов, которые мы можем выбрать. Например, я буду использовать 5%). Цены на фрукты могут меняться (случайным образом), поэтому общая стоимость может измениться и на основе этого (для простоты я не меняю цены на фрукты в этом примере). Используя приведенный выше пример, на второй день игры пользователь возвращает значение $ 152 и $ 164 на 3-й день. Вот пример:

Quantity (day2)   %change (day2)    Value (day2)   Quantity (day3)   %change (day3)   Value(day3)
 104                                 104            106                                106
  21                                  42             23                                 46
   2                                   6              4                                 12
 127               4.96%             152            133               4.72%            164

* (Я надеюсь, что таблицы отображаются правильно, мне пришлось вручную их разместить, так что, надеюсь, это не просто делает это на моем экране, если это не работает, дайте мне знать, и я постараюсь загрузить скриншот.)

Я пытаюсь понять, могу ли я определить, что такое количество с течением времени (при условии, что у пользователя будет терпение, чтобы продолжать вводить числа). Я знаю, что сейчас мое единственное ограничение - общая сумма не может превышать 5%, поэтому я не могу быть в пределах 5% точности прямо сейчас, чтобы пользователь входил в нее навсегда.

То, что я сделал до сих пор

Вот мое решение до сих пор (не так много). В принципе, я беру все значения и выясняю все возможные комбинации из них (я делаю эту часть). Затем я беру все возможные комбо и помещаю их в базу данных в виде словаря (например, для $ 143, может быть запись в словаре {apple: 143, Pears: 0, Orange: 0}) до самого {apple : 0, Pears: 1, Апельсины: 47} Я делаю это каждый раз, когда получаю новый номер, поэтому у меня есть список всех возможностей.

Вот где я застрял. Используя приведенные выше правила, как я могу найти наилучшее решение? Я думаю, мне понадобится функция фитнеса, которая автоматически сравнивает данные за два дня и удаляет любые возможности, которые имеют более чем 5% -ную дисперсию данных предыдущих дней.

Вопросов:

Итак, мой вопрос с пользователем, изменяющим общее число, и меня со списком всех вероятностей, как я должен подходить к этому? Что мне нужно узнать? Существуют ли какие-либо алгоритмы или теории, которые я могу использовать, которые применимы? Или, чтобы помочь мне понять мою ошибку, вы можете предложить, какие правила я могу добавить, чтобы сделать эту цель выполнимой (если она не находится в ее нынешнем состоянии. Я подумывал добавить больше фруктов и сказать, что они должны выбрать не менее 3 и т. Д.) ? Кроме того, у меня есть только смутное понимание генетических алгоритмов, но я думал, что могу использовать их здесь, если есть что-то, что я могу использовать?

Я очень очень хочу учиться, поэтому любые советы или советы были бы очень благодарны (просто, пожалуйста, не говорите мне, что эта игра невозможна).

ОБНОВЛЕНИЕ: получение отзывов, которые трудно решить. Поэтому я думал, что добавлю еще одно условие в игру, которое не будет мешать тому, что делает игрок (игра остается для них одинаковой), но каждый день ценность фруктов меняет цену (случайным образом). Помогло бы это решить? Потому что в пределах 5% движения и некоторых изменений стоимости фруктов, только несколько комбинаций вероятны с течением времени.

День 1, все возможно, и получить достаточно близкий диапазон практически невозможно, но поскольку цены на фрукты меняются, и пользователь может выбрать только 5% -ное изменение, то не следует (со временем) диапазон быть узким и узким. В приведенном выше примере, если цены достаточно волатильны, я думаю, что я мог бы переработать решение, которое дало мне возможность угадать, но я пытаюсь выяснить, есть ли более элегантное решение или другие решения, чтобы сузить этот диапазон время.

UPDATE2: После прочтения и опроса, я считаю, что это скрытая проблема Маркова / Витерби, которая отслеживает изменения цен на фрукты, а также общую сумму (взвешивая последние данные, самые тяжелые). Я не уверен, как применять отношения. Я думаю, что это так и может быть неправильным, но, по крайней мере, я начинаю подозревать, что это проблема машинного обучения.

Обновление 3: Я создал тестовый пример (с меньшими числами) и генератор, чтобы помочь автоматизировать созданные пользователем данные, и я пытаюсь создать граф из него, чтобы узнать, что более вероятно.

Вот код, а также общие значения и комментарии о том, что на самом деле представляют собой количество фруктов.

#!/usr/bin/env python
import itertools

# Fruit price data
fruitPriceDay1 = {'Apple':1, 'Pears':2, 'Oranges':3}
fruitPriceDay2 = {'Apple':2, 'Pears':3, 'Oranges':4}
fruitPriceDay3 = {'Apple':2, 'Pears':4, 'Oranges':5}

# Generate possibilities for testing (warning...will not scale with large numbers)
def possibilityGenerator(target_sum, apple, pears, oranges):
    allDayPossible = {}
    counter = 1
    apple_range = range(0, target_sum + 1, apple)
    pears_range = range(0, target_sum + 1, pears)
    oranges_range = range(0, target_sum + 1, oranges)
    for i, j, k in itertools.product(apple_range, pears_range, oranges_range):
        if i + j + k == target_sum:
            currentPossible = {}

            #print counter
            #print 'Apple', ':', i/apple, ',', 'Pears', ':', j/pears, ',', 'Oranges', ':', k/oranges
            currentPossible['apple'] = i/apple
            currentPossible['pears'] = j/pears
            currentPossible['oranges'] = k/oranges

            #print currentPossible
            allDayPossible[counter] = currentPossible
            counter = counter +1
    return allDayPossible

# Total sum being returned by user for value of fruits
totalSumDay1=26 # Computer does not know this but users quantities are apple: 20, pears 3, oranges 0 at the current prices of the day
totalSumDay2=51 # Computer does not know this but users quantities are apple: 21, pears 3, oranges 0 at the current prices of the day
totalSumDay3=61 # Computer does not know this but users quantities are apple: 20, pears 4, oranges 1 at the current prices of the day
graph = {}
graph['day1'] = possibilityGenerator(totalSumDay1, fruitPriceDay1['Apple'], fruitPriceDay1['Pears'], fruitPriceDay1['Oranges'] )
graph['day2'] = possibilityGenerator(totalSumDay2, fruitPriceDay2['Apple'], fruitPriceDay2['Pears'], fruitPriceDay2['Oranges'] )
graph['day3'] = possibilityGenerator(totalSumDay3, fruitPriceDay3['Apple'], fruitPriceDay3['Pears'], fruitPriceDay3['Oranges'] )

# Sample of dict = 1 : {'oranges': 0, 'apple': 0, 'pears': 0}..70 : {'oranges': 8, 'apple': 26, 'pears': 13}
print graph



Я написал программу для игры. Конечно, мне пришлось автоматизировать человеческую сторону, но я считаю, что я сделал все это таким образом, что я не должен был бы аннулировать мой подход, когда играл против настоящего человека.

Я подошел к этому с точки зрения машинного обучения и рассматривал проблему как скрытую марковскую модель, где общая цена была наблюдением. Мое решение - использовать фильтр частиц. Это решение написано на Python 2.7 с помощью NumPy и SciPy.

Я изложил любые предположения, сделанные явным образом в комментариях или неявно в коде. Я также установил некоторые дополнительные ограничения для того, чтобы запустить код в автоматическом режиме. Это не особенно оптимизировано, поскольку я пытался ошибаться на стороне, а не скорости.

Каждая итерация выводит текущие истинные величины и гадание. Я просто передаю вывод в файл, чтобы я мог легко его просмотреть. Интересным продолжением будет построение вывода на графике либо 2D (для 2 фруктов), либо 3D (для 3-х фруктов). Тогда вы сможете увидеть, как фильтр частиц оттачивается в решении.

Обновить:

Отредактировал код, чтобы включить обновленные параметры после настройки. Включены вызовы с использованием matplotlib (через pylab). Планирование работает на Linux-Gnome, ваш пробег может отличаться. По умолчанию NUM_FRUITS - 2 для построения поддержки. Просто закомментируйте все вызовы pylab, чтобы удалить графику и сможете изменить NUM_FRUITS на что угодно.

Хорошо оценивает текущую fxn, представленную UnknownQuantities X Prices = TotalPrice. В 2D (2 Fruits) это линия, в 3D (3 Fruits) это был бы самолет. Кажется, слишком мало данных для фильтра частиц, чтобы надежно оттачивать правильные количества. Нужно немного больше смайликов поверх фильтра частиц, чтобы действительно собрать историческую информацию. Вы можете попробовать преобразовать фильтр частиц в 2-й или 3-й порядок.

Обновление 2:

Я много играл с моим кодом. Я попробовал кучу вещей и теперь представляю последнюю программу, которую я буду делать (начиная с этой идеи).

Изменения:

Частицы теперь используют плавающие точки, а не целые. Не уверен, что это имело какой-либо значимый эффект, но это более общее решение. Округление до целых чисел выполняется только при угадывании.

На графике показаны истинные величины как зеленый квадрат, а текущая догадка - как красный квадрат. В настоящее время считается, что частицы показаны как синие точки (размер которых зависит от того, насколько мы им верим). Это позволяет легко понять, насколько хорошо работает алгоритм. (Plotting также тестировался и работал на 64-разрядной версии Win 7).

Добавлены параметры отключения / изменения количества и изменения цены. Конечно, обе «офф» не интересны.

Это неплохая работа, но, как было отмечено, это очень сложная проблема, поэтому получить точный ответ сложно. Отключение CHANGE_QUANTITIES создает простейший случай. Вы можете получить оценку сложности проблемы, выполнив работу с 2 фруктами с выключенным CHANGE_QUANTITIES. Посмотрите, как быстро он набирает правильный ответ, а затем посмотрите, насколько тяжелее это, так как вы увеличиваете количество фруктов.

Вы также можете взглянуть на трудность, сохранив CHANGE_QUANTITIES, но настроив MAX_QUANTITY_CHANGE с очень малых значений (.001) на «большие» значения (0,05).

Одна из ситуаций, когда он борется, - это то, что по размеру (одно количество фруктов) приближается к нулю. Поскольку он использует среднее количество частиц, чтобы угадать, он всегда будет перескакивать с жесткой границы, равной нулю.

В общем, это отличный учебник по фильтрации частиц.

from __future__ import division
import random
import numpy
import scipy.stats
import pylab

# Assume Guesser knows prices and total
# Guesser must determine the quantities

# All of pylab is just for graphing, comment out if undesired
#   Graphing only graphs first 2 FRUITS (first 2 dimensions)

NUM_FRUITS = 3
MAX_QUANTITY_CHANGE = .01 # Maximum percentage change that total quantity of fruit can change per iteration
MAX_QUANTITY = 100 # Bound for the sake of instantiating variables
MIN_QUANTITY_TOTAL = 10 # Prevent degenerate conditions where quantities all hit 0
MAX_FRUIT_PRICE = 1000 # Bound for the sake of instantiating variables
NUM_PARTICLES = 5000
NEW_PARTICLES = 500 # Num new particles to introduce each iteration after guessing
NUM_ITERATIONS = 20 # Max iterations to run
CHANGE_QUANTITIES = True
CHANGE_PRICES = True

'''
  Change individual fruit quantities for a random amount of time
  Never exceed changing fruit quantity by more than MAX_QUANTITY_CHANGE
'''
def updateQuantities(quantities):
  old_total = max(sum(quantities), MIN_QUANTITY_TOTAL)
  new_total = old_total
  max_change = int(old_total * MAX_QUANTITY_CHANGE)

  while random.random() > .005: # Stop Randomly    
    change_index = random.randint(0, len(quantities)-1)
    change_val = random.randint(-1*max_change,max_change)

    if quantities[change_index] + change_val >= 0: # Prevent negative quantities
      quantities[change_index] += change_val
      new_total += change_val

      if abs((new_total / old_total) - 1) > MAX_QUANTITY_CHANGE:
        quantities[change_index] -= change_val # Reverse the change

def totalPrice(prices, quantities):
  return sum(prices*quantities)

def sampleParticleSet(particles, fruit_prices, current_total, num_to_sample):
  # Assign weight to each particle using observation (observation is current_total)
  # Weight is the probability of that particle (guess) given the current observation
  # Determined by looking up the distance from the hyperplane (line, plane, hyperplane) in a
  #   probability density fxn for a normal distribution centered at 0 
  variance = 2
  distances_to_current_hyperplane = [abs(numpy.dot(particle, fruit_prices)-current_total)/numpy.linalg.norm(fruit_prices) for particle in particles]
  weights = numpy.array([scipy.stats.norm.pdf(distances_to_current_hyperplane[p], 0, variance) for p in range(0,NUM_PARTICLES)])

  weight_sum = sum(weights) # No need to normalize, as relative weights are fine, so just sample un-normalized

  # Create new particle set weighted by weights
  belief_particles = []
  belief_weights = []
  for p in range(0, num_to_sample):
    sample = random.uniform(0, weight_sum)
    # sum across weights until we exceed our sample, the weight we just summed is the index of the particle we'll use
    p_sum = 0
    p_i = -1
    while p_sum < sample:
      p_i += 1
      p_sum += weights[p_i]
    belief_particles.append(particles[p_i])
    belief_weights.append(weights[p_i])

  return belief_particles, numpy.array(belief_weights)

'''
  Generates new particles around the equation of the current prices and total (better particle generation than uniformly random)
'''
def generateNewParticles(current_total, fruit_prices, num_to_generate):
  new_particles = []
  max_values = [int(current_total/fruit_prices[n]) for n in range(0,NUM_FRUITS)]
  for p in range(0, num_to_generate):
    new_particle = numpy.array([random.uniform(1,max_values[n]) for n in range(0,NUM_FRUITS)])
    new_particle[-1] = (current_total - sum([new_particle[i]*fruit_prices[i] for i in range(0, NUM_FRUITS-1)])) / fruit_prices[-1]
    new_particles.append(new_particle)
  return new_particles


# Initialize our data structures:
# Represents users first round of quantity selection
fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)])
fruit_quantities = numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)])
current_total = totalPrice(fruit_prices, fruit_quantities)
success = False

particles = generateNewParticles(current_total, fruit_prices, NUM_PARTICLES) #[numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)]) for p in range(0,NUM_PARTICLES)]
guess = numpy.average(particles, axis=0)
guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)])

print "Truth:", str(fruit_quantities)
print "Guess:", str(guess)

pylab.ion()
pylab.draw()
pylab.scatter([p[0] for p in particles], [p[1] for p in particles])
pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c='g', marker='s')
pylab.scatter([guess[0]], [guess[1]], s=150, c='r', marker='s')
pylab.xlim(0, MAX_QUANTITY)
pylab.ylim(0, MAX_QUANTITY)
pylab.draw()

if not (guess == fruit_quantities).all():
  for i in range(0,NUM_ITERATIONS):
    print "------------------------", i

    if CHANGE_PRICES:
      fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)])

    if CHANGE_QUANTITIES:
      updateQuantities(fruit_quantities)
      map(updateQuantities, particles) # Particle Filter Prediction

    print "Truth:", str(fruit_quantities)
    current_total = totalPrice(fruit_prices, fruit_quantities)

    # Guesser's Turn - Particle Filter:
    # Prediction done above if CHANGE_QUANTITIES is True

    # Update
    belief_particles, belief_weights = sampleParticleSet(particles, fruit_prices, current_total, NUM_PARTICLES-NEW_PARTICLES)
    new_particles = generateNewParticles(current_total, fruit_prices, NEW_PARTICLES)

    # Make a guess:
    guess = numpy.average(belief_particles, axis=0, weights=belief_weights) # Could optimize here by removing outliers or try using median
    guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)]) # convert to integers
    print "Guess:", str(guess)

    pylab.cla()
    #pylab.scatter([p[0] for p in new_particles], [p[1] for p in new_particles], c='y') # Plot new particles
    pylab.scatter([p[0] for p in belief_particles], [p[1] for p in belief_particles], s=belief_weights*50) # Plot current particles
    pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c='g', marker='s') # Plot truth
    pylab.scatter([guess[0]], [guess[1]], s=150, c='r', marker='s') # Plot current guess
    pylab.xlim(0, MAX_QUANTITY)
    pylab.ylim(0, MAX_QUANTITY)
    pylab.draw()

    if (guess == fruit_quantities).all():
      success = True
      break

    # Attach new particles to existing particles for next run:
    belief_particles.extend(new_particles)
    particles = belief_particles
else:
  success = True

if success:
  print "Correct Quantities guessed"
else:
  print "Unable to get correct answer within", NUM_ITERATIONS, "iterations"

pylab.ioff()
pylab.show()



Related