Есть объекты.
Есть информация о параметрах каждого объекта в виде строчки "ai1     ai2    ...ain"

Так в общем виде выглядит вся информация о наших объектах:
a11    a12    a13    ... a1n
a21    a22    a23    ... a2n
a31    a32    a33    ... a3n
...
ak1    ak2    ak3    ... akn

, где аij - конкретное число.

Есть некоторая формула, которая на вход получает информацию о всех объектах, и потом сортирует эти объекты.
Есть практически неограниченное количество данных вида: реальные цифры - как их рассортировала наша формула.

Все, больше ничего нет 

Подскажите пожалуйста следующее: 
    1. как узнать какие именно из параметров важнее других и насколько
    2. как узнать что это за формула

Это сообщение отредактировал(а) kulibinka - 16.3.2007, 04:05

типичная задача "черный ящик".
Существуют следующие методы, описания которых в тернете полно:

1. Генетические алгоритмы (ГА). Или их подвид Селективные алгоритмы. Решение в кратце такое: выбирается полином, запукается указанный алгоритм, и он подбирает коэфициенты полинома так, чтобы результат совпал с Вами указанным. Этот полином и есть искомая функция.

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

3. МНК или МНВК - методы для восстановления функций по некоторым данным.
4. Интерполяция

Вообще надо Вам почитать теорию систем и системного управления. И методы параметрической идентификации.

Это сообщение отредактировал(а) Bitter - 16.3.2007, 20:22

Спасибо, теперь вижу что задача имеет решение.




Много методов это хорошо 
Но для моей конкретной задачи
1. какой из вариантов проще всего в реализации?
2. Не подскажете конкретную литературу по этому варианту? Или никакой особо избранной литературы нет, и просто спросить у гугля?

Это сообщение отредактировал(а) kulibinka - 16.3.2007, 21:46

То, что Вы описали не конкреная задача, а общая постановка задачи черного ящика. По этому какой вариант больше подходит решать Вам. Могу лишь привести несколько ссылок:

1. ГА - http://algolist.manual.ru/ai/ga/index.php

2. Нейросети - http://algolist.manual.ru/ai/neuro/index.php

3. Метод наименьших квадратов (МНК) - http://iglin.exponenta.ru/All/ContData/lsqm.html

4. Интерполяция - 
    http://matlab.exponenta.ru/spline/book1/10.php
    http://www.tspu.tula.ru/ivt/old_site/umr/chislmet/lab7.htm

Спасибо большое за объяснения, пошел разбираться.

Помоему задача не имеет решения в общем случае.

В общем нет- так как ни один из приведенных методов не дает 100% результат для всех случаев, а дает для конкретного.

А вот определить, какие данные важнее- это вам помогут приведенные выше алгоритмы.

Мне кажется, что в данной ветке не было произнесено (хотя подразумевалось) нескольких важных вещей:

• Истинную формулу (т.е. формулу, соответствующую физическому закону, определяющему полученные величины) получить невозможно. Точнее - можно наткнуться на нее случайно, но ничто не укажет, что получена именно она.
• Получена может быть только формула наиболее точно аппроксимируящая данные.
• Если задачу можно переформулировать из получить формулу из "ниоткуда" в выбрать формулу из заранее предложенных вариантов, то тут уже можно вполне достоверно говорить о нахождении истинной формулы. Число вариантов формулы в начальном списке может быть очень большое, при условии, что и данных очень много.
• Метод "в обход": получить формулу "из ниоткуда", а потом придумать для нее физический смысл 

Почему только? Можно получить формулу не точно апроксимирующую данные. Потом для того чтобы говорить о точности надо задавать метрику.

Это сообщение отредактировал(а) esperant0 - 19.3.2007, 14:21

Формула будет чтото вроде:

SUM(@1*a1+@2*a2+...@n*an)


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


Необходимо найти коеффициенты @1..@n (которые по условийу задачи одинаковы, потому что и представляют собой "важность" параметра)

Остальное - дело техники. сортируем N обьектов, выписываем матрицу.

@1*ai1|@2*ai2|...|@n*ain| 0
@1*a(i+1)1|@2*ai(i+1)2|...|@n*a(i+1)n| 1
:
:
@1*a(i+N)1|@2*a(i+N)2|...|@n*a(i+N)n| N

N должно быть N>= n

Упрощаем матрицу в треугольник Гауссом и находим коеффициенты @1..@n

Теперь можем отсортировать любой обьект. Не уверен, что наша функция сортировки будет всегда давать 100 правильный ответ, но соотношение между важностью параметров определим довольно точно.

Для оптимизации надо возможно специально подбирать обьекты со спец. @

Кстати, почему бы нам не просортировать такие обьекты:

0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 1 0 0 0
1 0 0 0 0

Узнаем важность каждого коеффициента 

ПС:
Это я всё так .. набросал думать Вам 

Продолжение.. 

Итак, начинаем с identity matrix I (Это у которой еденицы по диагонали)

Сортируем наши обьекты. Берём самый маленький обьект O0 и увеличиваем его коеффициент с шагом ß до тех пор, пока функция не отсортирует его лучше, обьекта О1. На самом деле идеальным будет найти коеффициент, который приравняет О1 к к О0 Проверить равенство можно запустив эти два обьекта в сортировку в разном порядке. Если на выходе порядок сохранился,  - обьекты равны. 

Всё это проделать с каждым обьектом, пока они все не будут равны.

Таким образом найдём абсолютно точные коеффициенты @ и абсолютно точную функцию сортировки 

Для определения шага существует куча алгов. Так как тут имеем дело с линеарной разницей коеффоф, подойдёт метод половинок. То есть каждый шаг увеличиваем в два раза, пока порядок сортировки остаётся прежним. А как только он поменяется, берём середину разницы между последним и предпоследним и прибавляем её к предпоследнему.






Ну впринципе, надежды оправдались 
Если в условии задачи коефы целые числа, то проблема решается со 100%. Если дробные - как повезёт, но можно максинально приблизится к 100%.

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

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


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

sergejzr, +1. Методы планирования эксперимента рулят. А одновременное изменение переменных (при сохранении ортогональности плана, т.е. эталонных векторов), позволит поймать полиномиальные взаимодействия переменных вида xi*xj, xi*xj*xk в сортирующей функции.

Можно по подробней? Что такое накоторая вероятностная оценка. А главное на каком вероятностном пространстве вы собираетесь ее задавать?

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

Если переформулировать, задача: поиск бинарного отношения линейного порядка на множестве целочисленных векторов Z^n.
На Z^n существуют стандартные порядки: лексикография, обратная лексикография, по полной степени -пост-лексикография (или обратная) и т.д.
В общем случае любой сохраняющий сложение порядок (т.е. если a>b, то a+c>b+c при a,b,c \in Z^n) на Z^n можно определить матрицей n x n, задающей весовые коэффициенты и перестановки для перехода в стандартную лексикографию  ( \exists W - матрица \forall a<b: Wa <_{lex} Wb), и в этом случае как нельзя лучше подходит предложение sergejzr, а при неограниченном количестве входных данных результат будет практически 100-прроцентный.

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

Это сообщение отредактировал(а) Artemios - 26.3.2007, 10:17

Мне кажется kulibinka хочет чтобы была формула в виде f(x)=ax^3+ bx^2+cx+d, нейропакеты в таком виде не выдают формулы (могу конечно ошибаться). Потом если неугадать с функцией активации: то либо будет большая погрешность апроксимирования искомой функции, либо будет работать в пределах икса скажем [0;10] вне этих пределов мусор который даже что-то похожее не будет выдавать.



Это надо заниматься факторным анализом, скажем в Статистике были примеры на этот счёт. Можно попробовать загнать данные в сеть Кохонена и посмотреть на сколько классов будут разделены данные, далее посмотреть чем они кардинально различаются.

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

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

PS Как было уже сказано: в результате одного из методов будет получена функция, которая выдаёт тоже что и надо, но она врят ли будет иметь физический смысл.

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


Ну, не только этот способ возможен. Можно посчитать значимость параметров и исходя из "субъективного" "мнения" именно той функции-формулы, которая будет построена (например, банально посмотреть на частные производные - насколько быстро меняется зависимая переменная при изменении независимой). Т.е. есть возможности оценивания как с точки зрения выведенной формулы, так без всяких предположений об этой формуле (взять, например, банальные парные корреляции или парные/множественные условные энтропии) 

Точнее было бы f(x1,x2)=... , причем область значений функции примерно {-1,0,1}

Добавлено через 8 минут и 38 секунд
Или даже {true,false}  :
f(x1,x2) = x1>x2