2008-06-05 “Душа назаем”, ИББ
by Vasil KolevОтидох на представяне на “Душа назаем” на Тишо – беше интересно, особено четенето на част от книгата (видях се и с много хора, дето не бях виждал от бая време). Взех си книжката и я чета в момента…
Българските автори имат един специфичен стил на разказване, имам чуството, че е от езика. Тишо също не е избягал от него, но е четим и приятен, а не натруфен (например и на Георги Марков ужасно му личи (въпреки, че е велик), с изключение на “Репортажите”, май само И. Попов от тия, дето съм чел има коренно различен стил). Книжката радва (поне до тук), само имам едно гадно чуство, че за толкова къса книжка няма да успее да развие историята, а дано греша :)
(Молба от крокодила към българските автори: “Пишете повече, не ща книгата да свършва малко след като съм я започнал…”)
На ИББ Гунински даде много интересна задача (довела до няколко часа забавни сметки на мене, червото и Стефан) – имаме система от N линейни уравнения с k неизвестни (N>k), да се намери решение, което удовлетворява максимален брой от тези уравнения. Нещата се свеждат до откриване на K на брой максимални по големина линейно зависими групи от тия уравнения, ама май ще се окаже, че това е NP-пълна задача.
(или поне така решихме ние, някой да има по-добра идея ?:) )
Не само това беше забавно, видях се с един приятел, с който не се бяхме засичали от 4-5 години (имаше една минута, в която се гледахме и се чудехме дали се познаваме), изговорихме стандартното количество простотии, а Мариела ми домъкна поръчаното CD на Diablo Swing Orchestra.
Започнаха да се виждат очертанията на големия проект. Измислихме схема на базата, днеска решихме, че ще я сменяме, ама се надявам до края на седмицата да успеем да я бетонираме и да попишем малко код, та да има и какво да се тества.
June 5th, 2008 at 08:20
Diablo Swing Orchestra!!!!! ААaaaa-ТУП! :D Трябва да се сдобия и аз :)
June 5th, 2008 at 10:07
Задачата, която сте се опитвали да решите, всъщност е решената отдавна. Това е класическата задача за решение на преопределена система в линейни уравнения. Тя няма точно решение в общия случай, но има решение удовлетворяващо системата с линейни уравнения статистически. На български решението на задачата се нарича “Метод на най-малките квадрати”. На английски е “Least Squares Method” и мисля, че в Wikipedia постановката и решението на задачата е представено много добре:
http://en.wikipedia.org/wiki/Least_squares
Самото решение представлява средноквадратично приближение, което дори може да си го онагледите като качество, ако имате конкретните коефициенти на линейните уравнения. Малко по-сложен е проблемът с дискретизацията на решението, т.е. ако искате да получавате цели числа като компоненти на вектора с решението. Общо взето най-реалният подход е да закръглите полученото числено решение покомпонентно.
June 5th, 2008 at 12:03
@Весо: Най-малките квадрати не може да се използва за подход. В общия случай при най-малките квадрати е възможно нито едно уравнение да не е удовлетворено, а при преопределена система винаги ще може да удовлетвориш брой уравнения равни най-малко на броя на неизвестните.
June 5th, 2008 at 12:12
@Веселин: Като прочетох първият път задачата и аз за LLSQ си помислих, обаче това не е метод да се задоволят най-много уравнения напълно, а да се задоволят всички уравнения оптимално и незнам дали Васил иска това или другото. Иначе ако е това може и с Singular Value Decomposition да намери приблизително решение ако уравненията не са много лошо кондиционирани.
http://en.wikipedia.org/wiki/Singular_value_decomposition#Solving_homogeneous_linear_equations
В случай, че наистина търсиш максималното множество уравнения, което се състой от непротиворечащи си уравнения, може да видиш някой солвър за линейно оптимиране. Те разполагат с функция за намиране на irreducible infeasible set (IIS), което е такова можество, че премахването на което е да е 1 уравнение от него го прави решимо, докато то самото не е. Така можеш да получиш (надявам се максималното) непротиворечащо си множество уравнения.
June 5th, 2008 at 16:33
@Д.Василев: LSQ може да удовлетворява повече или по-малко дадено уравнение. На всяко уравнение в преопределената система може да се задава тегло, което накрая се появява като знаменател в целевата функция. Така можеш да си избереш модел на удовлетворяване по тегла. Но стои открит въпросът как да подбереш теглата. На практика написаното от Васил за сегментиране на задачата на по блокове от K уравнения, е горе-долу апроксимация на идеята с теглата. Възможно е да се постави задача за LSQ в комбинация с вариационен метод и може да бъде открит набора от K уравнения, като във формирания функционал да се търси параметър K, който да бъде максимален по стойност. В задачата не се казва дали при намиране на решението за K набора уравнения следва да се взема предвид информация за всички N уравнения. Или според мен условието не е предадено както трябва тук или е непълно заданието по него. Примерно аз не разбирам следното. Имаме ли право да не взимаме предвид някои от уравненията. Трябва ли да разбираме задачата като “купчинка” уравнения, от които си избираме такава K-торка, че да удовлетворим някакво условие (в случая да намерим тази K-торка (K>k), за която LSQ дава най-малко стандартно отклонение).
В моделирането на данни често се среща задача, в която да подбереш модел из множества линейни уравнения от дадена степен, който да описва данни и там има подобна задача, но там първо има връзки между множествата и второ винаги има функционал. Май е по-добре да пиша лично на Георги и да разбера какво точно се иска в задачата.
June 6th, 2008 at 13:23
Здрасти, аз ще напиша нещо за Тишо, а не за Diablo (което всъщност съм играла до припадък, хех).
И аз бях на представянето на “Душа назаем”, беше много добро, кратко и стойностно. Чета книжката умишлено бавно, за да й се насладя :) До момента ми харесва много.
Поздрави!
Биляна
June 8th, 2008 at 23:02
Значи правилно чух думата “блог” из пространството, но не те познах :) За съжаление не можах да остана за коктейла и си чакам книгата с нетърпение :) Самото представяне ми се стори кратко но идейно, а това със рисунките няма аналог…