Случайны выбор дневника Раскрыть/свернуть полный список возможностей


Найдено 6257 сообщений
Cообщения с меткой

алгоритмы - Самое интересное в блогах

Следующие 30  »
rss_rss_hh_new

Точка Б: как мы обучали приложение Яндекс.Такси предсказывать пункт назначения

Вторник, 19 Сентября 2017 г. 10:00 (ссылка)






vkantor


сегодня в 10:00

Разработка





Точка Б: как мы обучали приложение Яндекс.Такси предсказывать пункт назначения










    Представьте: вы открываете приложение, чтобы в очередной раз заказать такси в часто посещаемое вами место, и, конечно, в 2017 году вы ожидаете, что все, что нужно сделать – это сказать приложению «Вызывай», и такси за вами тут же выедет. А куда вы хотели ехать, через сколько минут и на какой машине — все это приложение узнает благодаря истории заказов и машинному обучению. В общем-то все, как в шутках про идеальный интерфейс с единственной кнопкой «сделать хорошо», лучше которого только экран с надписью «все уже хорошо». Звучит здорово, но как же приблизить эту реальность? Об этом мы и хотим рассказать.







    На днях мы выпустили новое приложение Яндекс.Такси для iOS. В обновленном интерфейсе один из акцентов, как нетрудно заметить, сделан на выборе конечной точки маршрута («точки Б»). Но новая версия – это не просто новый UI. К запуску обновления мы существенно переработали технологию прогнозирования пункта назначения, заменив старые эвристики на обученный на исторических данных классификатор.



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



    Задача



    При выборе пункта назначения, в поле «куда» у нас есть возможность предложить пользователю буквально 2-3 варианта на главном экране и еще несколько – если он перейдет в меню выбора точки Б:







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



    До построения модели на основе машинного обучения была реализована такая стратегия: берутся все точки из истории, «одинаковые» точки (с одинаковым адресом или находящиеся близко) сливаются, за разные параметры получившимся локациям начисляются различные баллы (если пользователь ездил в эту точку, ездил из этой точки, ездил в эту точку в какое-то временное окно и так далее). Затем выбираются локации с наибольшим числом баллов и рекомендуются пользователю. Как я уже говорил, исторически эта стратегия неплохо работала, но точность прогнозирования можно было повысить. А главное — мы знали как.



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


    Наша задача состояла в том, чтобы поверх «старой» стратегии использовать переранжирование наиболее вероятных «точек Б» с помощью машинного обучения. Общий подход такой: сначала начисляем баллы, как и раньше, затем берём топ n по этим баллам (где n заведомо больше, чем нужно в итоге порекомендовать), а далее переранжируем его и пользователю в итоге показываем только три наиболее вероятные точки Б. Точное число кандидатов в списке, конечно, определяется в ходе оптимизации, чтобы и качество кандидатов и качество переранжирования были как можно выше. В нашем случае оптимальное число кандидатов оказалось равным 20.



    Об оценке качества и результатах



    Во-первых, качество нужно разделить на две части: качество кандидатов и качество ранжирования. Качество кандидатов — это то, насколько отобранные кандидаты в принципе возможно правильно переранжировать. А качество ранжирования — это насколько мы правильно предсказываем точку назначения при условии того, что она вообще есть среди кандидатов.



    Начнём с первой метрики, то есть качества кандидатов. Стоит отметить, что только примерно в 72 процентах заказов выбранная точка Б (или очень близкая к ней географически) присутствовала ранее в истории. Это означает, что максимальное качество кандидатов ограничено этим числом, так как мы пока не можем рекомендовать точки, куда человек еще ни разу не ездил. Мы подобрали эвристики с назначением баллов так, что при отборе топ-20 кандидатов по этим баллам правильный ответ в них содержался в 71% случаев. При максимуме в 72% это весьма неплохой результат. Это качество кандидатов нас полностью устраивало, поэтому эту часть модели мы дальше не трогали, хотя, в принципе, могли бы. Например, вместо эвристик можно было обучить отдельную модель. Но так как механизм поиска кандидатов, основанный на эвристиках, уже был технически реализован, мы смогли сэкономить на разработке, лишь подобрав нужные коэффициенты.



    Снова вернемся к качеству переранжирования. Так как на главном экране заказа поездки показывать мы можем одну, две, ну максимум три точки, то нас интересует доля случаев, когда правильный ответ оказался в топ-1, топ-2 и топ-3 списка ранжирования соответственно. В машинном обучении долю правильных ответов в топ k списка ранжирования (от всех правильных ответов) называют recall@k. В нашем случае нас интересуют recall@1, recall@2 и recall@3. При этом «правильный ответ» в нашей задаче только один (с точностью до близко расположенных точек), а значит, эта метрика как раз будет показывать долю случаев, когда настоящая «точка Б» попадает в топ 1, топ 2 и топ 3 нашего алгоритма.



    В качестве базового алгоритма ранжирования мы взяли сортировку по количеству баллов и получили следующие результаты (в процентах): recall@1 = 63,7; recall@2 = 78,5 и recall@3 = 84,6. Заметим, что проценты здесь – это доля от тех случаев, где правильный ответ в кандидатах вообще присутствовал. В какой-то момент возник логичный вопрос: возможно, простая сортировка по популярности уже даёт хорошее качество, а все идеи сортировки по баллам и использование машинного обучения излишни? Но нет, такой алгоритм показал самое плохое качество: recall@1 = 41,2; recall@2 = 64,6; recall@3 = 74,7.



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





    Доля случаев, когда фактический пункт назначения попадал в число первых k рекомендаций


    Какая модель строилась



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



    Теперь перейдём к модели для переранжирования. Так как мы хотим максимизировать recall@k, в первом приближении мы хотим прогнозировать вероятность поездки пользователя в определенное место и ранжировать места по вероятности. «В первом приближении» потому, что эти рассуждения верны только при очень точной оценке вероятностей, а когда в них появляются погрешности, recall@k может лучше оптимизироваться и другим решением. Простая аналогия: в машинном обучении, если мы точно знаем все распределения вероятностей, самый лучший классификатор — байесовский, но поскольку на практике распределения восстанавливаются по данным приближенно, часто другие классификаторы работают лучше.



    Задача классификации ставилась следующим образом: объектами были пары (история предыдущих поездок пользователя; кандидат в рекомендации), где положительные примеры (класс 1) — пары, в которых пользователь все-таки поехал в эту точку Б, отрицательные примеры (класс 0) — пары, в которых пользователь в итоге поехал в другое место.



    Таким образом, если побыть прожженным формалистом, модель оценивала не вероятность того, что человек поедет в конкретную точку, а сдвинутую вероятность того, что заданная пара «история-кандидат» является релевантной. Тем не менее, сортировка по этой величине столь же осмыслена, что и сортировка по вероятности поездки в точку. Можно показать, что при избытке данных это будут эквивалентные сортировки.



    Классификатор мы обучали на минимизацию log loss, а в качестве модели использовали активно применяемый в Яндексе Матрикснет (градиентный бустинг над решающими деревьями). И если с Матрикснетом всё понятно, то почему всё-таки оптимизировался log loss?



    Ну, во-первых, оптимизация этой метрики приводит к правильным оценкам вероятности. Причина, по которой так происходит, своими корнями уходит в математическую статистику, в метод максимального правдоподобия. Пусть вероятность единичного класса у i-го объекта равна $p_i$, а истинный класс равен $y_i$. Тогда, если считать исходы независимыми, правдоподобие выборки (грубо говоря, вероятность получить именно такой исход, который был получен) равно следующему произведению:

    $\prod_{i}p_i^{y_i}(1-p_i)^{(1-y_i)}$

    В идеале нам хотелось бы иметь такие $p_i$, чтобы получить максимум этого выражения (ведь мы хотим, чтобы полученные нами результаты были максимально правдоподобны, правда?). Но если прологарифмировать это выражение (так как логарифм — монотонная функция, то можно его максимизировать вместо исходного выражения), то мы получим $\sum_i y_i ln (p_i) + (1-y_i)ln(1-p_i)$. А это уже известный нам log loss, если заменить $p_i$ на их предсказания и умножить все выражение на минус-единицу.



    Во-вторых, мы, конечно, доверяем теории, но на всякий случай попробовали оптимизировать разные функции потерь, и log loss показал самый большой recall@k, так что все в итоге сошлось.



    О методе поговорили, о функции ошибки – тоже, осталась одна важная деталь: признаки, по которым мы обучали наш классификатор. Для описания каждой пары «история-кандидат» мы использовали более сотни разных признаков. Вот несколько для примера:



    И, наконец, о результатах: после переранжирования с помощью построенной нами модели мы получили следующие данные (опять же в процентах): recall@1 = 72,1 (+8,4); recall@2 = 82,6 (+4,1); recall@3 = 88 (+3,4). Совсем неплохо, но в будущем возможны улучшения за счет включения в признаки дополнительной информации.



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

    Дальнейшие планы



    Разумеется, впереди много экспериментов по улучшению модели. Будет и добавление новых данных для построения рекомендаций, в том числе интересов пользователя, а также предполагаемых «дома» и «работы» из Яндекс Крипты и связанных с ними признаков, и эксперимент по сравнению различных методов классификации в этой задаче. Например, у Яндекса уже есть не только используемый сугубо внутри команды Матрикснет, но и набирающий популярность и в Яндексе, и за его пределами CatBoost. При этом, конечно же, нам интересно сравнивать не только собственные разработки, но и другие реализации популярных алгоритмов.



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


    Original source: habrahabr.ru (comments, light).

    https://habrahabr.ru/post/337328/

    Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
    rss_rss_hh_new

    [Из песочницы] Генерация родословного дерева на основе данных Wikipedia

    Понедельник, 18 Сентября 2017 г. 17:41 (ссылка)






    fonkost


    сегодня в 17:41

    Разработка





    Генерация родословного дерева на основе данных Wikipedia










    В этой статье я хочу показать, как с помощью фреймворка Selenium Webdriver можно, исходя из данных Wikipedia, составить генеалогическое древо заданной персоны (например, легендарного основателя первой династии русских правителей Рюрика).



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

    Я буду использовать Java, Selenium Webdriver и Chrome. Chrome, потому что он быстрее остальных браузеров, а так как переход по урлу — самое затратное по времени операция в программе, то выбор браузера заметнее всего сказывается на времени. Можно вообще отказаться от браузера и использовать, скажем PhantomJs, но его сложнее дебажить. Поэтому я остановился на Chrome.



    В первую очередь создадим тест, проверяющий, что браузер корректно запустился и что при переходе по урлу https://ru.wikipedia.org/wiki/Рюрик открывается страница с заголовком «Рюрик — Википедия»:



    @BeforeClass
    public static void Start() {
    driver = DriverHelper.getDriver();
    }

    @Test
    public void testGetDriver() {
    driver.navigate().to("https://ru.wikipedia.org/wiki/%D0%A0%D1%8E%D1%80%D0%B8%D0%BA");
    assertTrue(driver.getTitle().equals("Рюрик — Википедия"));
    }

    @AfterClass
    public static void Stop() {
    driver.quit();
    }


    Создаем класс DriverHelper со статичным методом getDriver(), чтобы проект скомпилился и тест прошёл успешно:



    public final class DriverHelper{
    private static final int TIMEOUT = 30;

    public static WebDriver getDriver() {
    WebDriver driver = new ChromeDriver();
    driver.manage().window().maximize();
    driver.manage().timeouts().implicitlyWait(TIMEOUT, TimeUnit.SECONDS);
    return driver;
    }
    }


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



    Создание класса Person



    Перейдем к созданию класса Person, в котором будет храниться информация о персоне, а также к созданию класса страницы персоны на Wikipedia PersonPage.



    В классе Person пока будут только два поля – name и url. В качестве name будем использовать полное имя человека, без разделения на Фамилию, Имя, Отчество, т.к. большинство представителей династии не будут иметь фамилии, зато будут иметь прозвища, титулы и порядковые имена.



    Url будет указывать на страницу Wikipedia, посвященную данному человеку.

    Создаем тест, проверяющий формирование персоны:



    @Test
    public void testGetPerson() throws Exception {
    PersonPage page = new PersonPage(driver);
    Person person = page.getPerson("https://ru.wikipedia.org/wiki/Владимир_Александрович");
    assertTrue(person.getName().equals("Владимир Александрович"));
    assertTrue(person.getUrl().equals(
    "https://ru.wikipedia.org/wiki/
    %D0%92%D0%BB%D0%B0%D0%B4%D0%B8%D0%BC%D0%B8%D1%80_
    %D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87"));
    }


    testGetPerson() не компилится. Нам нужно разработать страницу PersonPage, чтобы определить имя и страницу человека. Url мы определяем по url текущей страницы, а имя – по текстовому содержимому тэга с идентификатором firstHeading. Метод getPerson():



    public Person getPerson(String url) throws MalformedURLException {
    driver.navigate().to(url);

    String name = getName();

    Person person = new Person(driver.getCurrentUrl());
    person.setName(name);
    return person;
    }

    private String getName() throws MalformedURLException {
    String namePage = driver.findElement(By.cssSelector("#firstHeading")).getText();
    return namePage;
    }


    Перепрогоняем тесты – позеленели.

    Отдельно стоит упомянуть, почему переопределяется url, хотя он передается в качестве параметра: дело в том, что в Wikipedia одной персоне может быть посвящено несколько страниц, которые редиректятся на одну. В результате, если использовать исходные урлы, то возможно возникновение дубликатов, когда существует несколько персон с «разными» урлами, которые фактически являются одной персоной. Поэтому в качестве урла используется тот урл, на который редиректятся все остальные.



    Например: страница https://ru.wikipedia.org/wiki/Ярослав_Мудрый перенаправляется на https://ru.wikipedia.org/wiki/Ярослав_Владимирович_Мудрый, а страница https://ru.wikipedia.org/wiki/Андрей_Боголюбский — на https://ru.wikipedia.org/wiki/Андрей_Юрьевич_Боголюбский



    Определение детей персоны



    Попробуем определить детей персоны, которые имеют свои страницы в Wikipedia.

    Для начала напишем тест для определения детей Рюрика (точнее одного — Игоря):



    @Test
    public void testGetChildrenUrl() throws Exception {
    driver.navigate().to("https://ru.wikipedia.org/wiki/Рюрик");
    PersonPage page = new PersonPage(driver);
    List children = page.getChildrenUrl();
    assertTrue(children.size() == 1);
    Person person = children.get(0);
    assertTrue(person.getUrl().equals("https://ru.wikipedia.org/wiki/
    %D0%98%D0%B3%D0%BE%D1%80%D1%8C_
    %D0%A0%D1%8E%D1%80%D0%B8%D0%BA%D0%BE%D0%B2%D0%B8%D1%87"));
    }


    Чтобы тест прошел успешно, нужно добавить на страницу PersonPage метод определения урлов детей человека:



    public List getChildrenUrl() throws MalformedURLException {
    List childrenLinks = driver.findElements(
    By.xpath("//table[contains(@class, 'infobox')]//tr[th[.='Дети:']]//a"));
    List children = new ArrayList();
    for (WebElement link : childrenLinks) {
    Person person = new Person(link.getAttribute("href"));
    children.add(person);
    }
    return children;
    }


    Пока что игнорируем то, что детям могут быть не посвящены страницы в Wikipedia и поэтому они не имеют ссылок на свои страницы. Например, как в случае с детьми Владимира Ярославича (князя галицкого). Также игнорируем то, что информация о потомках может располагаться в основной области, как, например, на странице Марии Добронеги или на странице Святослава Всеволодовича (князя трубчевского).



    Добавляем тесты, проверяющие корректность определения детей для персоны.

    Как было оговорено выше, пока предполагаем, что Владимир Ярославич (князь галицкий) и Мария Добронега детей не имели, а Владимир Святославич имел 16 детей, хотя Wikipedia утверждает, что у него было ещё 5 неизвестных по имени дочерей.



    @Test
    public void testChildrenSize() throws Exception {
    driver.navigate().to("https://ru.wikipedia.org/wiki/Рюрик");
    PersonPage page = new PersonPage(driver);
    List children = page.getChildrenUrl();
    assertTrue(children.size() == 1);

    driver.navigate().to("https://ru.wikipedia.org/wiki/Владимир_Святославич");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 16);

    driver.navigate().to("https://ru.wikipedia.org/wiki/Владимир_Ярославич_(князь_галицкий)");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 0);

    driver.navigate().to("https://ru.wikipedia.org/wiki/Мария_Добронега");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 0);
    }


    В класс Person добавим поля для уникального идентификатора персоны (int id) и списка детей персоны (List children), в котором будут храниться идентификаторы детей.

    Разработаем метод добавления идентификатора ребенка в список детей персоны. Ребенок может быть добавлен в список, только если его там ещё нет.



    public void setChild(int childId) {
    if (!children.contains(childId)) {
    children.add(childId);
    }
    }


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



    Алгоритм поиска потомков



    Теперь перейдем к самому интересному – разработке алгоритма поиска потомков у заданной персоны. Создадим класс GenerateGenealogicalTree с методом main.



    Как уже упоминалось, самое затратное по времени — переход по урлу, поэтому нужно минимизировать количество этих переходов. Для этого создадим список персон, в котором будет хранится всё родословное древо. В этом списке запомним индекс текущей персоны — той, на странице которой находимся на данный момент. Все персоны с меньшим индексом считаются «посещенными», а все с бОльшим индексом (+ текущая) — «непосещенными». После того, как был осуществлен переход на страницу текущей персоны и вычислены её основные данные, индекс увеличивается на единицу. Тем самым текущая персона попадает в разряд «посещенных». И остаётся только обойти оставшихся «непосещенных» персон. В каждый момент времени известны те персоны, страницы которых уже были просмотрены.



    Наполнение родословного древа новыми «непосещенными» персонами происходит за счет добавления в конец списка детей текущей персоны. При этом добавляем только тех детей, которых ещё нет в списке, чтобы не возникали дубликаты (такая ситуация возможна, когда муж и жена — оба являются потомками родоначальника династии от разных ветвей. Примеры: муж и жена — потомки Рюрика, муж и жена — потомки Павла I).



    Родословное древо считается построенным, когда не осталось «непосещенных» персон, т.е. когда индекс текущей персоны стал равным размеру родословного древа.



    Алгоритм такой:




    1. Создается основатель династии на основе заданного урла

    2. Создается родословное древо на основе основателя династии

    3. В цикле до тех пор, пока есть «непосещенные» персоны

    4. Вычисляется персона на основе текущего урла родословного древа. Эта персона устанавливается в качестве текущей.

    5. Если текущая персона не является дубликатом, то вычисляется и устанавливается список её детей. Все дети добавляются в список.

    6. Если текущая персона уже встречалась среди «посещенных» персон, то она удаляется.

    7. Происходит переход к следующей «непосещенной» персоне, которая принимается за «текущую».



    Код алгоритма:



    public final class GenerateGenealogicalTree {
    public static void main(String[] args) throws Exception {
    String url = getUrl(args);
    GenealogicalTree tree = getGenealogicalTreeByUrl(url);
    saveResultAndQuit(tree);
    }

    public static GenealogicalTree getGenealogicalTreeByUrl(String url) throws MalformedURLException {
    WebDriver driver = DriverHelper.getDriver();
    Person person = new Person(url);
    GenealogicalTree tree = new GenealogicalTree(person);
    PersonPage page = new PersonPage(driver);
    while (tree.hasUnvisitingPerson()) {
    String currentUrl = tree.getCurrentUrl();
    Person currentPerson = page.getPerson(currentUrl);
    tree.setCurrentPerson(currentPerson);
    if (!tree.isCurrentPersonDeleted()) {
    List children = page.getChildrenUrl();
    tree.setChildren(children);
    }
    tree.updatingCurrentPerson();
    }
    driver.quit();
    return tree;
    }
    }


    Класс GenealogicalTree имеет три поля: List allPersons — список всех представителей родословного древа, int indexCurrentUnvisitedPerson — индекс текущей персоны в списке allPersons, а также boolean isCurrentPersonDeleted — признак того, удалена ли «текущая» персона (т.е. является ли она дубликатом).



    public final class GenealogicalTree {
    private List allPersons;
    private int indexCurrentUnvisitedPerson;
    private boolean isCurrentPersonDeleted;
    }


    Инициализация происходит на основе «родоначальника» династии — первой персоне, потомков которой мы ищем:



    public GenealogicalTree(Person person) {
    if (person == null) {
    throw new IllegalArgumentException("Укажите непустого основателя династии");
    }
    allPersons = new ArrayList();
    allPersons.add(person);
    indexCurrentUnvisitedPerson = 0;
    isCurrentPersonDeleted = false;
    }


    В этот момент родословное древо состоит из одной текущей «непосещенной» персоны. «Посещенных» персон нет.



    Как уже упоминалось, проверка списка на наличие «непосещенных» персон осуществляется так: если индекс текущей персоны «дошел до конца», то считаем, что «непосещенных» персон не осталось.



    public boolean hasUnvisitingPerson() {
    return indexCurrentUnvisitedPerson < allPersons.size();
    }


    В роли url-а родословного древа выступает url текущей персоны:



    public String getCurrentUrl() {
    return allPersons.get(indexCurrentUnvisitedPerson).getUrl();
    }


    Метод setCurrentPerson заменяет текущую персону на заданную.



    Изначально мы знаем о персоне только её url, который получаем со страницы родителя. Поэтому в родословное древо персона добавляется, имея только эту информацию. По сути все «непосещенные» персоны — это просто url-ы. Метод setCurrentPerson «уточняет» персону после того, как индекс «до неё добрался» и персона стала текущей.



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



    Понятие «встречается раньше» подразумевает, что мы проверяем только «посещенные» персоны. «Непосещенные» не проверяем. Теоретически возможна ситуация, когда url текущей персоны редиректится на url, который может встречатся «позже», среди «непосещенных». Но это настолько редкая ситуация, что она не стоит того, чтобы каждый раз «пробегать» по всему массиву. В этом редком случае дубликат все равно удалится, когда до него «дойдет очередь» и индекс текущей персоны будет указывать на персону с url-ом, на который произошёл редирект.



    public void setCurrentPerson(Person currentPerson) {
    int indexDuplicate = allPersons.indexOf(currentPerson);
    if ((0 <= indexDuplicate) && (indexDuplicate < indexCurrentUnvisitedPerson)) {
    removePerson(indexDuplicate);
    } else {
    allPersons.get(indexCurrentUnvisitedPerson).copyMainData(currentPerson);
    isCurrentPersonDeleted = false;
    }
    }


    Чтобы корректно отработал метод indexOf(Object object) необходимо в классе Person переопределить методы equals(Object object) и hashCode():



    @Override
    public boolean equals(Object object) {
    if ((object == null) || (!(object instanceof Person))) {
    return false;
    }

    Person person = (Person) object;
    return this.url.equals(person.url);
    }

    @Override
    public int hashCode() {
    return this.url.hashCode();
    }


    Зачем нужно постоянно проверять наличие персоны в списке?

    Возникновение дубликатов возможно по многим причинам:




    1. Отцовство достоверно неизвестно. Как, например, в случае со Святополком Окаянным, отцом которого является либо Ярополк Святославич, либо Владимир Святославич

    2. Оба родителя – потомки Рюрика от разных ветвей. Пример: Глеб Всеславич — потомок Рюрика в 8-м поколении был женат на Анастасии Ярополковне — тоже потомком Рюрика (они четвероюродные брат с сестрой).

    3. Ошибки на странице: вызывает сомнение, что Всеволод Мстиславич имел сына Володаря Глебовича, родителями которого записаны другие люди, тоже принадлежащие династии Рюриковичей. Вероятнее всего, это просто опечатка в Wikipedia



    Если эти дубликаты не устранить, то они породят новые повторения, т.к. по всем потомкам дубликатов обход будет производится два раза, а то и три (в случае с Володарем Глебовичем).



    Теперь рассмотрим удаление персоны из списка, когда она является дубликатом. Удаляемая персона может быть в списке детей члена родословного древа. Например, когда оба родителя являются представителями одной и той же династии, у одного родителя ссылка на одну страницу «ребенка», а у второго — на другую, которая затем редиректится на первую. Получается, что если «просто» удалить дубликат, то у второго родителя будет ссылка на несуществующую персону.



    Поэтому перед удалением текущей персоны нужно заменить в списке идентификаторов детей всех «посещенных» персон её идентификатор на идентификатор найденного совпадения (у «непосещенных» детей нет).



    После удаления текущая персона помечается удаленной.



    private void removePerson(int indexDuplicate) {
    int idRemovedPerson = allPersons.get(indexCurrentUnvisitedPerson).getId();
    int idDuplicate = allPersons.get(indexDuplicate).getId();
    for (int i = 0; i < indexCurrentUnvisitedPerson; i++) {
    Person person = allPersons.get(i);
    person.replaceChild(idRemovedPerson, idDuplicate);
    }
    allPersons.remove(indexCurrentUnvisitedPerson);
    isCurrentPersonDeleted = true;
    }


    В классе Person добавляем метод замены «ребенка»:



    public void replaceChild(int oldId, int newId) {
    if (oldId == newId) {
    return;
    }
    if (!children.contains(oldId)) {
    return;
    }
    children.remove((Object) oldId);
    setChild(newId);
    }


    Рассмотрим добавление детей текущей персоне.



    На вход мы получаем список персон, которых надо установить текущей в качестве детей.

    Главное отличие в поиске дубликатов состоит в том, что теперь мы будем их искать не только среди «посещенных» персон, но и среди «непосещенных», т.е. внутри всего родословного древа.

    Если текущая персона удалена, то выдается исключение, т.к. по сути устанавливать детей некому.



    Если не удалена, то пробегаемся по списку, переданному в качестве параметра. Если ребенок уже встречается в родословном древе, то в список детей добавляется идентификатор найденного дубликата. Если ребенок не встречается в родословном древе, то в список детей добавляется его идентификатор, кроме того, сам ребенок добавляется в конец родословного древа, в список «непосещенных» персон.



    Таким образом через метод setChildren() происходит «наполнение» списка.



    public void setChildren(List children) {
    if (isCurrentPersonDeleted) {
    throw new IllegalArgumentException(
    "Нельзя установить детей удаленной персоне. Текущая персона уже другая");
    }

    for (Person person : children) {
    int index = allPersons.indexOf(person);
    int id;
    if (index >= 0) {
    id = allPersons.get(index).getId();
    } else {
    allPersons.add(person);
    id = person.getId();
    }
    allPersons.get(indexCurrentUnvisitedPerson).setChild(id);
    }
    }


    Счетчик текущей персоны нужно обновлять, иначе родословное древо никогда не построится. Происходит это так: если текущая персона удалена, то на «её месте» уже находится следующая «непосещенная» персона, поэтому достаточно просто «снять» признак удаленной персоны с текущей. Если текущая персона не удалена, то считаем её «заполненной» всеми данными и переходим к следующей «непосещенной» персоне.



    public void updatingCurrentPerson() {
    if (isCurrentPersonDeleted) {
    isCurrentPersonDeleted = false;
    } else {
    indexCurrentUnvisitedPerson++;
    }
    }


    Обход осуществляется по поколениям: вначале основатель династии (0-е поколение), затем все его дети (1-е поколение) от старшего к младшему (подразумеваем, что именно в таком порядке располагаются урлы в Wikipedia), затем внуки (2-е поколение) (дети старшего сына по старшинству, затем — 2-го сына, и так до самого младшего), правнуки (3-е поколение) и так до самого последнего представителя династии.



    Естественно, не забываем довести покрытие кода тестами до 100%, чтобы удостовериться, что все работает именно так, как и задумывалось. Описание тестов доступно в javadoc.



    Отдельно стоит упомянуть вот о чём: класс GenealogicalTree является очень небезопасным и его легко заставить работать некорректно, если использовать вне алгоритма генерации родословного древа (вне GenerateGenealogicalTree). Единственно правильное решение в данной ситуации — перенос данного класса в качестве внутреннего приватного класса для GenerateGenealogicalTree. Но это пока не сделано для удобства тестирования алгоритма.

    Запускаем программу.



    Логирование результатов в БД



    Первый запуск показывает, что мы имеем огромное количество данных, которые надо как-то анализировать, чтобы отсеять заведомо неверные результаты. Забегая вперед сообщу, что на 17 сентября 2017 в Wikipedia нашлось 3448 страниц прямых потомков Рюрика. Легче всего подобный объем информации обрабатывать в БД.



    В первую очередь развернем локальную базу данных, которую назовем genealogicaltree. Со стандартным пользователем root без пароля. Для взаимодействия с БД будем использовать стандартную библиотеку MySQL JDBC Type 4 driver.



    А дальше создаем новый класс для взаимодействия с БД и метод для сохранения родословного древа в таблице с заданным именем:



    public class MySqlHelper {
    private static final String url = "jdbc:mysql://localhost:3306/genealogicaltree"
    + "?serverTimezone=UTC&useUnicode=yes&characterEncoding=UTF-8";
    private static final String user = "root";
    private static final String password = "";

    private static Connection connection;
    private static Statement statement;
    private static ResultSet resultSet;

    public static void saveTree(String tableName, List tree) throws MalformedURLException {
    try {
    connection = DriverManager.getConnection(url, user, password);
    statement = connection.createStatement();

    String table = createTable(tableName);
    statement.executeUpdate(table);

    for (Person person : tree) {
    String insert = insertPerson(tableName, person);
    statement.executeUpdate(insert);
    }
    } catch (SQLException sqlEx) {
    sqlEx.printStackTrace();
    } finally {
    try {
    connection.close();
    } catch (SQLException se) {
    }
    try {
    statement.close();
    } catch (SQLException se) {
    }
    }
    }

    private static String createTable(String tableName) {
    StringBuilder sql = new StringBuilder();
    sql.append("CREATE TABLE " + tableName + " (");
    sql.append("id INTEGER not NULL, ");
    sql.append("name VARCHAR(255), ");
    sql.append("url VARCHAR(2048), ");
    sql.append("children VARCHAR(255), ");
    sql.append("PRIMARY KEY ( id ))");
    return sql.toString();
    }

    private static String insertPerson(String tableName, Person person) {
    StringBuilder sql = new StringBuilder();
    sql.append("INSERT INTO genealogicaltree." + tableName);
    sql.append("(id, name, url, nameUrl, children, parents, numberGeneration) \n VALUES (");
    sql.append(person.getId() + ",");
    sql.append("'" + person.getName() + "',");
    sql.append("'" + person.getUrl() + "',");
    sql.append("'" + person.getChildren() + "',");
    sql.append(");");
    return sql.toString();
    }
    }


    Дорабатываем сохранение результатов генерации:



    private static void saveResultAndQuit(GenealogicalTree tree) throws Exception {
    Timestamp timestamp = new Timestamp(System.currentTimeMillis());
    String tableName = "generate" + timestamp.getTime();
    MySqlHelper.saveTree(tableName, tree.getGenealogicalTree());
    }


    Разбор первых результатов



    Первый прогон GenerateGenealogicalTree.main() выдал много записей, беглый осмотр которых показывает наличие несуществующих и ошибочных страниц.



    Разложим ошибки по категориям:




    1. В список детей попал год (например, 1153 со страницы Ярослава Святославовича)


    2. Нерусскоязычная статья: Аделаида Французская, дочь короля Франции Людовика VII

    3. Страница «Внебрачный ребенок», появившаяся от того же Людовика VII

    4. Внешние страницы наподобие этой, которые попали в список, например, от Галерана IV де Бомона

    5. «Создание страницы». Например, Анна Юрьевна, дочь туровского князя Юрия Ярославича



    Доработаем метод getChildrenUrl() определения страниц детей, чтобы исключить заведомо ошибочные. Чтобы не попадала 1 категория, нужно убрать те ссылки, текстовое содержимое которых начинается на цифру. Чтобы не попадала 2 категория, нужно убрать те ссылки, класс которых равен extiw. Чтобы не попадали 3-4 категории, необходимо исключить ссылки, родительский тег которых равен sup (уточняющие ссылки). Чтобы убрать из списка 5 категорию необходимо исключить ссылки, класс которых равен new (создание страницы).



    Для начала доработаем тест testChildrenSize(), добавив в него проверку всех категории кривых ссылок:



    driver.navigate().to("https://ru.wikipedia.org/wiki/Ярослав_Святославич");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 3);

    driver.navigate().to("https://ru.wikipedia.org/wiki/Людовик_VII");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 5);

    driver.navigate().to("https://ru.wikipedia.org/wiki/Галеран_IV_де_Бомон,_граф_де_Мёлан");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 0);

    driver.navigate().to("https://ru.wikipedia.org/wiki/Юрий_Ярославич_(князь_туровский)");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 5);


    Тест предсказуемо красный.



    Теперь доработаем метод getChildrenUrl():



    public List getChildrenUrl() throws MalformedURLException {
    waitLoadPage();
    List childrenLinks = getChildrenLinks();
    List children = new ArrayList();
    for (WebElement link : childrenLinks) {
    if (DriverHelper.isSup(link)) {
    continue;
    }
    Person person = new Person(link.getAttribute("href"));
    person.setNameUrl(link.getText());
    if (person.isCorrectNameUrl()) {
    children.add(person);
    }
    }
    return children;
    }

    private List getChildrenLinks() {
    List childrenLinks = DriverHelper.getElements(driver,
    By.xpath("//table[contains(@class, 'infobox')]//tr[th[.='Дети:']]" +
    "//a[not(@class='new' or @class='extiw')]"));
    return childrenLinks;
    }

    private void waitLoadPage() {
    this.driver.findElement(By.cssSelector("#firstHeading"));
    }

    public final class DriverHelper {
    /**
    * Возвращает список элементов без ожидания их появления.

    * По умолчанию установлено неявное ожидание - это значит, что если на
    * странице нет заданных элементов, то пустой результат будет выведен не
    * сразу, а через таймаут, что приведет к потере времени. Чтобы не терять
    * время создан этот метод, где неявное ожидание обнуляется, а после поиска
    * восстанавливается.
    */
    public static List getElements(WebDriver driver, By by) {
    driver.manage().timeouts().implicitlyWait(0, TimeUnit.SECONDS);
    List result = driver.findElements(by);
    driver.manage().timeouts().implicitlyWait(DriverHelper.TIMEOUT, TimeUnit.SECONDS);
    return result;
    }

    public static boolean isSup(WebElement element) {
    String parentTagName = element.findElement(By.xpath(".//..")).getTagName();
    return parentTagName.equals("sup");
    }
    }

    public class Person {
    private String nameUrl;

    public boolean isCorrectNameUrl() {
    Pattern p = Pattern.compile("^[\\D]+.+");
    Matcher m = p.matcher(nameUrl);
    return m.matches();
    }
    }


    nameUrl — это наименование ссылки персоны, которое она имеет на странице родителя.

    Перепрогоняем весь комплект тестов — позеленели.



    У Рюрика очень много потомков, которым посвящены русскоязычные страницы в Wikipedia, поэтому вначале прогоним программу для Михаила Фёдоровича — первого царя из рода Романовых. Запускаем, ждём окончания и анализируем результаты.



    Романовы



    Прогон выдал 383 русскоязычные страницы потомков Михаила Федоровича (потомков с генетической точки зрения, а не с точки зрения принадлежности к роду Романовых, определяемой по мужской линии, которая прервалась ещё в 18 веке на Петре II), среди которых королева Дании, король Испании, король Нидерландов, король Швеции, и все потомки королевы Великобритании Елизаветы II, начиная с наследника британского престола принца Чарлза. Но эта информация, конечно, имеет второстепенное значение к исходной задаче.



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




    1. Две персоны с именем Владимир Александрович и две персоны с именем Фризо Оранско-Нассауский

    2. Три персоны с необычным именем Дети Алексея Михайловича, две с — Дети Ивана V, один с — Дети Петра I и ещё три- с Дети Михаила Фёдоровича



    Эти ошибочные страницы — следствие урлов с якорями, когда у ребенка нет отдельной страницы, а информация о нём хранится либо на странице родителя, как в первом случае, либо на отдельной странице для всех детей — как во втором.



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

    Поэтому можно смело дорабатывать метод getChildrenUrl(), возвращая пустой список, если текущий url имеет якорь. Это необходимо сделать, чтобы персоне с «якорем» в качестве детей не установились дети её родителя, т.е. собственные братья и сестры, как в первом случае ошибочных записей.



    public List getChildrenUrl() {
    waitLoadPage();
    if (DriverHelper.hasAnchor(driver)) {
    return new ArrayList();
    }
    ...
    }

    public final class DriverHelper {
    ...
    public static boolean hasAnchor(WebDriver driver) throws MalformedURLException {
    URL url = new URL(driver.getCurrentUrl());
    return url.getRef() != null;
    }
    ...
    }


    Добавляем новый тест, проверяющий, что персона с урлом, содержащим якорь, не имеет детей:



    @Test
    public void testEmptyChildrenInPersonWithAnchor() throws Exception {
    driver.navigate().to("https://ru.wikipedia.org/wiki/Владимир_Александрович");
    PersonPage page = new PersonPage(driver);
    List children = page.getChildrenUrl();
    assertTrue(children.size() == 5);

    driver.navigate().to(
    "https://ru.wikipedia.org/wiki/Владимир_Александрович#.D0.A1.D0.B5.D0.BC.D1.8C.D1.8F");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 0);
    }


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



    Если не вычисляется потомство, то какой вообще смысл в переходе по урлам с «якорем»? Потомство, конечно, не определяем, но можно получить другую информацию: имя персоны или, например, годы жизни. Поэтому лучше «сохранить» такие урлы для будущего расширения функциональности.



    Вычисление имени по «якорю»



    В большинстве подобных случаев имя персоны можно вычислить по «якорю»: имя — это текстовое содержимое тэга с идентификатором, равным значению «якоря».

    Доработаем метод getName():



    private String getName() throws MalformedURLException {
    waitLoadPage();
    String namePage = driver.findElement(By.cssSelector("#firstHeading")).getText();

    if (!DriverHelper.hasAnchor(driver)) {
    return namePage;
    }

    String anchor = DriverHelper.getAnchor(driver);
    List list = DriverHelper.getElements(driver, By.id(anchor));

    if (list.size() == 0) {
    return namePage;
    }

    String name = list.get(0).getText().trim();
    return name.isEmpty() ? namePage : name;
    }

    public final class DriverHelper {
    ...
    public static String getAnchor(WebDriver driver) throws MalformedURLException {
    URL url = new URL(driver.getCurrentUrl());
    return url.getRef();
    }
    ...
    }


    Если текущий url содержит «якорь», то необходимо проверить существование на странице элемента с идентификатором, равным «якорю». Его может не существовать, как в случае с Натальей — дочерью Петра I. На странице Петра ссылка содержит уже несуществующий «якорь», который не соответствует «якорю» Натальи.



    Также необходимо убедиться, что тэг с идентификатором «якоря» содержит непустой текст и вернуть наименование страницы в противном случае. Иначе, как, например, в ситуации с Демьяном Глебовичем, определится пустое имя и программа вылетит с исключением.

    Тесты опять позеленели.



    Добавление наименования ссылки, родителей и номера поколения



    Осталось проблема: имя Александра, старшего сына Владимира Александровича, определяется как «Семья». Что с этим делать?!



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



    Конечно, не забываем покрыть тестами весь доработанный код.



    Результатом доработки является то, что теперь у персоны есть два «имени», одно из которых уж точно «должно быть информативным». Исключением, по понятным причинам, является родоначальник династии, для которого nameUrl может быть любым (присвоим значение "" для определённости).



    Перепрогоняем программу для Романовых и сверяем данные с теми, что были собраны до рефакторинга.



    Вот так теперь выглядят урлы с якорями:






















































































    id name children url urlName
    8 Пелагея [] ссылка Пелагея
    9 Марфа [] ссылка Марфа
    10 Софья [] ссылка Софья
    15 Анна [] ссылка Анна
    23 Евдокия (младшая) [] ссылка Евдокия
    26 Феодора [] ссылка Феодора
    28 Мария [] ссылка Мария
    29 Феодосия [] ссылка Феодосия
    36 Дети Петра I [] ссылка Наталья
    133 Семья [] ссылка Александр
    360 Брак и дети [] ссылка Луана Оранско-Нассауская


    Добавление наименования ссылки не прошло бесследно. Прогон программы для Рюрика неожиданно вылетел с исключением о нарушении инструкции insert на Генрихе II (короле Наварры) из-за того, что nameUrl содержит значение с апострофом — «Генрих II д'Альбре». Доработаем методы setName и setNameUrl в классе Person, сохраняя заданное значение без апострофов.



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



    Чтобы легче было реализовывать эту новую функциональность, добавим в класс Person поля для номера поколения и списка родителей (чтобы легче было построить возрастающую связь):



    private List parents = new ArrayList();
    private int numberGeneration = 0;

    public void setParent(int parent) {
    parents.add(parent);
    }

    public void setNumberGeneration(int numberGeneration) {
    if (this.numberGeneration == 0) {
    this.numberGeneration = numberGeneration;
    }
    }


    Родитель в большинстве случаев будет один, но возможны ситуации, когда оба родителя потомки родоначальника династии от разных ветвей и тогда их будет двое. Выше даже был приведен пример ошибки, когда сразу трое «являются» родителями одного и того же человека (первый, второй, третий, их «общий» ребенок — и все Рюриковичи). Конечно, физиологически это невозможно, получается, как в анектоде, но, к сожалению, автоматически определить, кто их них «лишний» невозможно, поэтому придется сохранять всех.



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



    Что касается номера колена, то оно устанавливается только один раз от первого родителя. В тот момент, когда появляется второй родитель, ссылающийся на ребенка, номер поколения уже не обновляется. Т.к. обход родословного древа происходит по поколениям, то, очевидно, что номер поколения НЕпервого родителя будет равен или больше, чем номер колена первого родителя, а значит быстрее всего построить связь через «первых родителей».



    Устанавливать номер поколения и идентификатор родителя будем в методе setChildren(List children) класса GenerateGenealogicalTree:



    public void setChildren(List children) {
    if (isCurrentPersonDeleted) {
    throw new IllegalArgumentException(
    "Нельзя установить детей удаленной персоне. Текущая персона уже другая");
    }

    Person currentPerson = allPersons.get(indexCurrentUnvisitedPerson);
    int numberGeneration = currentPerson.getNumberGeneration();
    numberGeneration++;
    int idParent = currentPerson.getId();
    for (Person person : children) {
    int index = allPersons.indexOf(person);
    int id;
    if (index >= 0) { // Непервый родитель, номер поколения не трогаем
    allPersons.get(index).setParent(idParent);
    id = allPersons.get(index).getId();
    } else { // Первый родитель
    person.setNumberGeneration(numberGeneration);
    person.setParent(idParent);
    allPersons.add(person);
    id = person.getId();
    }
    currentPerson.setChild(id);
    }
    }


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



    Итоговые результаты



    Пришло время сформировать несколько родословных деревьев и посмотреть результаты:

    Адам — первый человек на Земле

    Чингисхан — величайший завоеватель в истории

    Романовы

    Рюриковичи (долго открывается — 3452 персоны).



    Пояснение к страницам:



    а) при нажатии на имя открывается страница персоны на Wikipedia

    б) при нажатии на № открывается страница связи заданной персоны с родоначальником. Например, вот страница, доказывающая, что королева Великобритании Елизавета II является потомком Рюрика в 29 поколении.

    в) при нажатии на идентификаторы в полях родителей и детей страница прокручивается на строку с этой персоной.



    Результаты показывают, что, например, последний российский император Николай II был потомком Рюрика в 28 поколении. Более того, все российские императоры, начиная с Петра III и Екатерины II были потомками Рюрика от разных ветвей.



    Исходный код проекта


    Original source: habrahabr.ru (comments, light).

    https://habrahabr.ru/post/338190/

    Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
    rss_rss_hh_new

    Kaggle: как наши сеточки считали морских львов на Алеутских островах

    Понедельник, 18 Сентября 2017 г. 14:19 (ссылка)




    temakone


    сегодня в 14:19

    Разработка





    Kaggle: как наши сеточки считали морских львов на Алеутских островах










      header_im



      Привет, Коллеги!

      27 июня закончилось соревнование на Kaggle по подсчёту морских львов (сивучей) на аэрофотоснимках NOAA Fisheries Steller Sea Lions Population Count. В нем состязались 385 команд. Хочу поделиться с вами историей нашего участия в челлендже и (почти) победой в нём.



      Небольшое лирическое отступление.



      Как многие уже знают, Kaggle – это платформа для проведения онлайн соревнований по Data Science. И в последнее время там стало появляться всё больше и больше задач из области компьютерного зрения. Для меня этот тип задач наиболее увлекателен. И соревнование Steller Sea Lions Population Count — одно из них. Я буду повествовать с расчётом на читателя, который знает основы глубокого обучения применительно к картинкам, поэтому многие вещи я не буду детально объяснять.



      Пару слов о себе. Я учусь в аспирантуре в университете города Хайдельберг в Германии. Занимаюсь исследованиями в области глубокого обучения и компьютерного зрения. Страничка нашей группы CompVis.



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



      На тот момент у меня был некий опыт участия в соревнованиях на Kaggle, но только в нерейтинговых, за которые не дают ни медалей, ни очков опыта (Ranking Points). Но у меня был довольно обширный опыт работы с изображениями с помощью глубокого обучения. У Димы же был опыт на Kaggle в рейтинговых соревнованиях, и была 1 бронзовая медаль, но работать с компьютерным зрением он только начинал.



      Перед нами встал нелёгкий выбор из 3 соревнований: предсказание рака матки на медицинских изображениях, классификация спутниковых изображений из лесов Амазонии и подсчёт сивучей на аэрофотоснимках. Первое было отброшено из-за визуально не очень приятных картинок, а между вторым и третьим было выбрано третье из-за более раннего дедлайна.



      Постановка задачи



      В связи со значительным уменьшением популяции сивучей на западных Алеутских островах (принадлежащих США) за последние 30 лет ученые из NOAA Fisheries Alaska Fisheries Science Center ведут постоянный учет количества особей с помощью аэрофотоснимков с дронов. До этого времени подсчет особей производился на фотоснимках вручную. Биологам требовалось до 4 месяцев, чтобы посчитать количество сивучей на тысячах фотографий, получаемых NOAA Fisheries каждый год. Задача этого соревнования — разработать алгоритм для автоматического подсчета сивучей на аэрофотоснимках.



      Все сивучи разделены на 5 классов:




      1. adult_males — взрослые самцы (),

      2. subadult_males – молодые самцы (),

      3. adult_females – взрослые самки (),

      4. juveniles – подростки (),

      5. pups – детёныши ().



      Дано 948 тренировочных картинок, для каждой из которых известно Ground Truth число особей каждого класса. Требуется предсказать число особей по классам на каждой из 18641 тестовых картинок. Вот пример некоторых частей из датасета.



      Картинки разных разрешений: 4608x3456 до 5760x3840. Качество и масштаб очень разнообразный, как видно из примера выше.

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



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



      image

      (image credits to bestfitting)



      Самые частые классы сивучей — это самки (), подростки () и детеныши ().





      Проблемы



      Здесь я кратко перечислю, какие были проблемы с данными, да и с задачей в целом.




      • Зашумленность разметки. Не на всех тренировочных картинках были размечены все сивучи (часто биологи пропускали тех, что плавают в воде).

      • Нет чёткого разделение между парами классов adult_males и subadult_males, adult_females и juveniles. Мы не всегда даже глазами можем понять где самка, а где подросток. Та же проблема со взрослыми и молодыми самцами. На вопрос “как вы их размечали?” биолог из NOAA ответил на форуме, что часто отличать классы приходилось только по поведенческим признакам. Например, взрослые самцы часто окружены множеством самок (сивучи живут гаремами), а молодые, еще не успешные, вынуждены одиноко ютиться в отдалении от всех.

      • Детенышей бывает затруднительно отличить от мокрого камня. Они в разы меньше, чем другие особи.

      • Нет segmentation масок — только грубая позиция животных. Лобовой подход на сегментацию объектов не применим.

      • Разные масштабы изображений в целом. В том числе, на глаз, масштаб на тренировочных изображениях меньше чем в тестовых.

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

      • Огромное количество тестовых картинок (18641) большого разрешения. Предсказание занимало от 10 до 30 часов на одном Titan X.

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



      Как мы решали



      В Германии, как и в России, в этом году выпали большие выходные на 1 Мая. Свободные дни с субботы по понедельник оказались как никогда кстати для того, чтобы начать погружаться в задачу. Соревнование длилось уже больше месяца. Всё началось с того, что мы с Димой Котовенко в субботу прочитали условие.



      Первое впечатление было противоречивым. Много данных, нету устоявшегося способа, как решать такие задачи. Но это подогревало интерес. Не всё ж "стакать xgboost-ы”. Цель я поставил себе довольно скромную — просто попасть в топ-100 и получить бронзовую медальку. Хотя потом цели поменялись.



      Первых 3 дня ушло на обработку данных и написание первой версии пайплайна. Один добрый человек, Radu Stoicescu, выложил кернел, который преобразовывал точки на тренировочных изображениях в координаты и класс сивуча. Здорово, что на это не пришлось тратить своё время. Первый сабмит я сделал только через неделю после начала.



      Очевидно, решать эту задачу в лоб с помощью semantic segmentation нельзя, так как нет Ground Truth масок. Нужно либо генерить грубые маски самому либо обучать в духе weak supervision. Хотелось начать с чего-то попроще.

      Задача подсчёта числа объектов/людей не является новой, и мы начали искать похожие статьи. Было найдено несколько релевантных работ, но все про подсчёт людей CrowdNet, Fully Convolutional Crowd Counting, Cross-scene Crowd Counting via Deep Convolutional Neural Networks. Все они имели одну общую идею, основанную на Fully Convolutional Networks и регрессии. Я начал с чего-то похожего.



      Идея crowd counting на пальцах



      Хотим научиться предсказывать хитмапы (2D матрицы) для каждого класса, да такие, что бы можно было просуммировать значения в каждом из них и получить число объектов класса.



      Для этого генерируем Grount Truth хитмапы следующим образом: в центре каждого объекта рисуем гауссиану. Это удобно, потому что интеграл гауссианы равен 1. Получаем 5 хитмапов (по одному на каждый из 5 классов) для каждой картинки из тренировочной выборки. Выглядит это так.



      Увеличить



      Среднеквадратичное отклонение гауссиан для разных классов выставил на глазок. Для самцов – побольше, для детенышей – поменьше. Нейронная сеть (тут и далее по тексту я имею в виду сверточную нейронную сеть) принимает на вход изображения, нарезанные на куски (тайлы) по 256x256 пикселей, и выплёвывает 5 хитмапов для каждого тайла. Функция потерь – норма Фробениуса разности предсказанных хитмапов и Ground Truth хитмапов, что эквивалентно L2 норме вектора, полученного векторизацией разности хитмапов. Такой подход иногда называют Density Map Regression. Чтобы получить итоговое число особей в каждом классе, мы суммируем значения в каждом хитмапе на выходе.
























      Метод Public Leaderboard RMSE
      Baseline 1: предсказать везде 0 29.08704
      Baseline 2: предсказать везде среднее по train 26.83658
      Мой Density Map Regression 25.51889


      Моё решение, основанное на Density Map Regression, было немного лучше бейзлайна и давало 25.5. Вышло как-то не очень.







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



      Оригинальная задача, которая решалась в статьях — это подсчет количества людей в толпе, т. е. был только один класс объектов. Вероятно, Density Map Regression не очень хороший выбор для задачи с несколькими классами. Да и всё усугубляет огромная вариация плотности и масштаба объектов. Пробовал менять L2 на L1 функцию потерь и взвешивать классы, всё это не сильно влияло на результат.



      Было ощущение, что L2 и L1 функции потерь делают что-то не так в случае взаимоисключающих классов, и что попиксельная cross-entropy функция потерь может работать лучше. Это натолкнуло меня на идею натренировать сеть сегментировать особей с попиксельной cross-entropy функцией потерь. В качестве Ground Truth масок я нарисовал квадратики с центром в ранее полученных координатах объектов.



      Но тут появилась новая проблема. Как получить количество особей из сегментации? В чатике ODS Константин Лопухин признался, что использует xgboost для регрессии числа сивучей по набору фич, посчитанных по маскам. Мы же хотели придумать как сделать всё end-to-end с помощью нейронных сетей.



      Тем временем, пока я занимался crowd counting и сегментацией, у Димы заработал простой как апельсин подход. Он взял VGG-19, натренированную на классификации Imagenet, и зафайнтьюнил ее предсказывать количество сивучей по тайлу. Он использовал обычную L2 функцию потерь. Получилось как всегда — чем проще метод, тем лучше результат.



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

      Я резко вышел в топ-20 c RMSE 20.5 на паблик лидерборде.



      К этому моменту целеполагание претерпело небольшие изменения. Стало понятно, что целиться имеет смысл не в топ-100, а как минимум в топ-10. Это уже не казалось чем-то недостижимым.



      Выяснилось, что на test выборке многие снимки были другого масштаба, сивучи на них выглядели крупнее, чем на train. Костя Лопухин (отдельное ему за это спасибо) написал в слаке ODS, что уменьшение тестовых картинок по каждой размерности в 2 раза давало существенный прирост на паблик лидерборде.



      Но Дима тоже не лыком шит, он подкрутил что-то в своей VGG-19, уменьшил картинки и вышел на 2-e место со скором ~16.



      Подбор архитектуры и гиперпараметров сети





      (image credits to Konstantin Lopuhin)



      С функцией потерь у нас всё понятно. Время начинать экспериментировать с более глубокими сетями. В ход пошли VGG-19, ResnetV2-101, ResnetV2-121, ResnetV2-152 и тяжелая артиллерия — Inception-Resnet-V2.



      Inception-Resnet-V2 — это архитектура придуманная Google, которая представляет собой комбинацию трюков от Inception архитектур (inception блоки) и от ResNet архитектур (residual соединения). Эта сеть изрядно глубже предыдущих и выглядит этот монстр вот так.





      (image from research.googleblog.com)



      В статье "Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning" ребята из Google показывают, что эта архитектура давала на тот момент state of the art на Imagenet без использования ансамблей.



      Кроме самих архитектур мне пришлось перебрать:




      • различные размеры входного тайла: от 224x224 до 512x512 пикселей;

      • тип пулинга после свёрточных слоёв: sum-pooling или average-pooling;

      • количество дополнительных FC-слоёв перед финальным: 0, 1 или 2;

      • количество нейронов в дополнительных FC-слоях: 128 или 256.



      Лучшей комбинацией оказались: Inception-Resnet-V2-BASE + average-pooling + FC-слой на 256 нейронов + Dropout + финальный FC-слой на 5 нейронов. Inception-Resnet-V2-BASE обозначает часть оригинальной сети от первого до последнего сверточного слоя.

      Лучшим размером входного тайла оказался 299x299 пикселей.



      Аугментации изображений



      Для тренировочных картинок мы делали типичный набор аугментаций для задач из CV.

      К каждому тайлу применялись:




      • Случайные флипы слева направо и сверху вниз;

      • случайные вращения на углы, кратные 90 градусов;

      • случайное масштабирование в 0.83 — 1.25 раза.

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



      Test time augmentation мы не делали. Потому что предсказание на всех тестовых картинках и так занимало полдня.



      Продолжение истории



      В какой-то момент, пока я перебирал гиперпараметры и архитектуры сетей, мы объединились в команду с Димой Котовенко. Я в тот момент был 2-м месте, Дима на 3-м. Для отвода китайцев в ложном направлении команду назвали "DL Sucks".



      Объединились, потому что было бы нечестно у кого-то забирать медальку, ведь с Димой мы активно обсуждали наши решения и обменивались идеями. Этому событию очень порадовался Костя, мы освободили ему призовое место. С 4-го он попал на 3-е.



      Последние 3-4 недели соревнования мы плотно держались на 2-м месте на паблик лидерборде, по одной десятой, по одной тысячной улучшая скор перебором гиперпараметров и стакая модели.



      Нам казалось, что уменьшение в 2 раза всех тестовых изображений — это пошло и грубо. Хотелось сделать всё красиво, чтобы сеть предсказала как нужно отмасштабировать каждое из изображений. Дима инвестировал в эту идею довольно много времени. Если вкратце, то он пытался по картинке предсказать масштаб сивучей, что равносильно предсказанию высоты полета дрона во время съемки. К сожалению, из-за недостатка времени и ряда проблем, с которыми мы столкнулись, это не было доведено до конца. Например, многие картинки содержат только одного сивуча и большая часть пространства — это море и камни. Поэтому, не всегда, глядя только на скалы или море, возможно понять с какой высоты был сделан снимок.



      За пару дней до дедлайна мы собрали все лучшие модели и сделали ансамбль из 24 нейронных сетей. Все модели имели лучшую архитектуру Inception-Resnet-V2, которую я описал ранее. Отличались модели только тем, насколько агрессивно мы аугментировали картинки, на каком масштабе тестовых изображений делались предсказания. Выходы с разных сетей усреднялись.



      Команда "DL Sucks" закончила соревнование на 2-м месте на паблик лидерборде, что не могло не радовать, так как мы были "в деньгах". Мы понимали, что на прайвэт лидерборде всё может поменяться и нас вообще может выкинуть из первой десятки. У нас был приличный разрыв с 4-м и 5-м местом, и это добавляло нам уверенности. Вот так выглядело положение на лидерборде:



      1-е место 10.98445 outrunner (Китаец 1)

      2-е место 13.29065 Мы (DL Sucks)

      3-е место 13.36938 Костя Лопухин

      4-е место 14.03458 bestfitting (Китаец 2)

      5-е место 14.47301 LeiLei-WeiWei (Команда из двух китайцев)

      Оставалось дождаться финальных результатов…

      И что бы вы думали? Китаец нас обошел! Мы были сдвинуты со 2-го на 4-ое место. Ну ничего, зато получили по золотой медали ;)



      Первое место, как оказалось, занял другой китаец, альфа-гусь outrunner. И решение у него было почти как у нас. Обучил VGG-16 c дополнительным полносвязным слоем на 1024 нейрона предсказывать количество особей по классам. Что вывело его на первое место, так это ad-hoc увеличение количества подростков на 50% и уменьшение количества самок на такое же число, умножение количества детёнышей на 1.2. Такой трюк поднял бы нас на несколько позиций выше.



      Финальное положение мест:



      1-е место 10.85644 outrunner (Китаец 1)

      2-е место 12.50888 Костя Лопухин

      3-е место 13.03257 (Китаец 2)

      4-е место 13.18968 Мы (DL Sucks)

      5-е место 14.47301 Дмитро Поплавский (тоже в слаке ODS) в команде с 2 другими


      Пару слов о других решениях



      Резонный вопрос — а нельзя ли натренировать детектор и посчитать потом баундинг боксы каждого класса? Ответ — можно. Некоторые парни так и сделали. Александр Буслаев (13-ое место) натренировал SSD, а Владимир Игловиков (49-ое место) — Faster RCNN.

      Пример предсказания Владимира:



      (image credits to Vladimir Iglovikov)

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



      Решение, основанное на сегментации с помощью UNet, тоже имеет место быть и вывело Константина на 2 место. Он предсказывал маленькие квадратики, которые он нарисовал внутри каждого сивуча. Далее — танцы с бубном. По предсказанным хитмапам Костя вычислял различные фичи (площади выше заданных порогов, количество и вероятности блобов) и скармливал их в xgboost для предсказания числа особей.



      (image credits to Konstantin Lopuhin)

      Подробнее про его решение можно посмотреть на youtube.



      У 3-го места (bestfitting) тоже решение основано на UNet. Опишу его в двух словах. Парень разметил вручную сегментационные маски для 3 изображений, обучил UNet и предсказал маски на еще 100 изображениях. Поправил маски этих 100 изображений руками и заново обучил на них сеть. С его слов, это дало очень хороший результат. Вот пример его предсказания.



      (image credits to bestfitting)

      Для получения числа особей по маскам он использовал морфологические операции и детектор блобов.



      Заключение



      Итак, начальная цель была попасть хотя бы в топ-100. Цель мы выполнили и даже перевыполнили. Было перепробовано много всяких подходов, архитектур и аугментаций. Оказалось, проще метод – лучше. А для сетей, как ни странно, глубже — лучше. Inception-Resnet-V2 после допиливания, обученная предсказывать количество особей по классам, давала наилучший результат.

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



      В аспирантуре я исследую в основном Unsupervised Learning и Similarity Learning. И мне, хоть я и занимаюсь компьютерным зрением каждый день, было интересно поработать с какой-то новой задачей, не связанной с моим основным направлением. Kaggle дает возможность получше изучить разные Deep Learning фреймворки и попробовать их на практике, а также поимплементировать известные алгоритмы, посмотреть как они работают на других задачах. Мешает ли Kaggle ресерчу? Вряд ли он мешает, скорее помогает, расширяет кругозор. Хотя времени он отнимает достаточно. Могу сказать, что проводил за этим соревнованием по 40 часов в неделю (прямо как вторая работа), занимаясь каждый день по вечерам и на выходных. Но оно того стоило.



      Кто дочитал, тому спасибо за внимание и успехов в будущих соревнованиях!






      Мой профиль на Kaggle: Artem.Sanakoev

      Краткое техническое описание нашего решения на Kaggle: ссылка

      Код решения на github: ссылка



      Original source: habrahabr.ru (comments, light).

      https://habrahabr.ru/post/337548/

      Комментарии (0)КомментироватьВ цитатник или сообщество
      rss_rss_hh_new

      Проекции? Hет, спасибо

      Понедельник, 18 Сентября 2017 г. 07:02 (ссылка)




      zzeng


      сегодня в 07:02

      Разработка





      Проекции? Hет, спасибо












        Под катом будет небольшая заметка о применении пространственного индекса

        на основе zcurve для индексации точечных данных, расположенных на сфере.

        А так же bencmark-и для PostgreSQL и сравнение с таким же (но совсем другим)

        индексом на R-дереве.



        В развитие темы (1, 2, 3, 4, 5, 6).

        Собственно, возвращаемся к самому началу — идее индексировать географические координаты, размещая их на поверхности сферы. Обычная индексация пары широта/долгота приводит к искажениям вдали от экватора, работа с проекциями не универсальна. Поэтому мысль переводить географические координаты в трехмерное пространство выглядит довольно изящно.



        Сама по себе идея эта не нова, аналогично работает, например, расширение PostgreSQL — PGSphere, которое использует для индексации 3-мерное R-дерево. С ним и будем сравнивать.



        Подготовка данных.



        PGSphere




        • Для начала придётся выкачать, собрать и инсталлировать расширение (автор использовал текущую версию 1.1.5)
          gmake USE_PGXS=1 PG_CONFIG=/usr/bin/pg_config
          sudo gmake USE_PGXS=1 PG_CONFIG=/usr/bin/pg_config install

        • Далее загрузить его (psql)
          CREATE EXTENSION pg_sphere;

        • Создадим таблицу для тестовых данных
          CREATE TABLE spoint_data (sp spoint);

        • Нам потребуется источник случайных данных.

          Первый параметр программы — радиус, второй — число результатов.

          Единственная тонкость — данные равномерно распределены внутри шара с заданным радиусом, иначе не получится равномерного распределения на сфере

        • Случайные данные пропустим через скрипт awk чтобы превратить в геокоординаты
          # --- gendata.awk ------
          BEGIN{
          pi=3.1415926535897932;
          degra=pi/180.0;
          rad=180.0/pi;
          Grad = 1000000.;
          }
          {
          x = $1; y = $2; z = $3;
          r3 = sqrt(x*x + y*y + z*z);
          x *= Grad / r3;
          y *= Grad / r3;
          z *= Grad / r3;

          r2 = sqrt(x*x + y*y);
          lat = atan2(z, r2) * rad;
          lon = 180. + atan2(y, x) * rad;

          printf ("(%14.10fd, %14.10fd)\n", lon, lat);
          }

        • Собственно создание данных, здесь радиус не важен, важно чтобы и pgsphere и zcurve получили одни и те же данные. Сортировка весьма желательна для ускорения индексации.
          ./random 1000000 100000000 | gawk -f gendata.awk | sort > pgsphere.txt

        • Заливаем данные в нашу таблицу
          COPY spoint_data (sp) FROM  '/home/.../pgsphere.txt';

        • Индексируем
          CREATE INDEX sp_idx ON spoint_data USING gist (sp);



        ZORDER




        • Для начала придётся выкачать, собрать и инсталлировать расширение
          gmake USE_PGXS=1 PG_CONFIG=/usr/bin/pg_config
          sudo gmake USE_PGXS=1 PG_CONFIG=/usr/bin/pg_config install

        • Создадим таблицу для тестовых данных
          create table test_points_3d (x integer,y integer, z integer);

        • Нам потребуется тот же источник случайных данных.

        • Случайные данные пропустим через скрипт awk чтобы разместить их внутри куба со стороной в 2 000 000
          #--- gendata2.awk ------
          BEGIN{
          pi=3.1415926535897932;
          degra=pi/180.0;
          rad=180.0/pi;
          Grad = 1000000.;
          }
          {
          x = $1; y = $2; z = $3;
          r3 = sqrt(x*x + y*y + z*z);
          x *= Grad / r3;
          y *= Grad / r3;
          z *= Grad / r3;

          ix = int(x+0.5+Grad);
          iy = int(y+0.5+Grad);
          iz = int(z+0.5+Grad);
          print ix"\t"iy"\t"iz;
          }

        • Собственно создание данных, здесь радиус важен. Сортировка не обязательна.
          ./random 1000000 100000000 | gawk -f gendata2.awk > zcurve.txt

        • Заливаем данные в нашу таблицу
          COPY test_points_3d FROM '/home/.../zcurve.txt';

        • Индексируем
          create index zcurve_test_points_3d on test_points_3d(zcurve_num_from_xyz(x,y,z));



        Подготовка тестов



        PGSphere



        Для тестирования потребуется вот такой awk скрипт

        #--- gentest.awk -------
        BEGIN{
        pi=3.1415926535897932;
        degra=pi/180.0;
        rad=180.0/pi;
        Grad = 1000000.;
        }
        {
        x = $1; y = $2; z = $3;
        r3 = sqrt(x*x + y*y + z*z);
        x *= Grad / r3;
        y *= Grad / r3;
        z *= Grad / r3;

        r2 = sqrt(x*x + y*y);

        lat = atan2(z, r2) * rad;
        lon = 180. + atan2(y, x) * rad;

        # EXPLAIN (ANALYZE,BUFFERS)
        printf ("select count(1) from spoint_data where sp @'<(%14.10fd,%14.10fd),.316d>'::scircle;\n", lon, lat);
        }


        Этот скрипт вполне симметричен тому, с помощью которого мы подготавливали данные. Стоит обратить внимание на число .316, это радиус сферы с центром в вычисленной случайной точке, в которой мы ищем данные

        Подготовка серии запросов делается так:

        ./random 1000000 100 1023 | gawk -f gentest.awk >tests1.sql


        Здесь 100 — размер тестовой серии, 1023 — seed рандомизатора.

        ZCURVE



        Для тестирования тоже потребуется awk скрипт

        #--- gentest2.awk -------
        BEGIN{
        pi=3.1415926535897932;
        degra=pi/180.0;
        rad=180.0/pi;
        Grad = 1000000.;
        }
        {
        x = $1; y = $2; z = $3;
        r3 = sqrt(x*x + y*y + z*z);
        x *= Grad / r3;
        y *= Grad / r3;
        z *= Grad / r3;

        ix = int(x+0.5+Grad);
        iy = int(y+0.5+Grad);
        iz = int(z+0.5+Grad);
        # EXPLAIN (ANALYZE,BUFFERS)
        lrad = int(0.5 + Grad * sin(.316 * degra));
        print "select count(1) from zcurve_3d_lookup_tidonly('zcurve_test_points_3d', "ix-lrad","iy-lrad","iz-lrad","ix+lrad","iy+lrad","iz+lrad");";
        }


        Этот скрипт вполне симметричен тому, с помощью которого мы подготавливали данные. Опять же, обращаем внимание на число .316, это половина стороны куба с центром в вычисленной случайной точке, в котором мы ищем данные.



        Подготовка серии запросов делается так:

        ./random 1000000 100 1023 | gawk -f gentest2.awk >tests2.sql


        Здесь 100 — размер тестовой серии, 1023 — seed рандомизатора, лучше, если он совпадает с оным от pgsphere.



        Benchmark



        Как и раньше, замеры проводились на скромной виртуальной машине с двумя ядрами и 4 Гб ОЗУ, поэтому времена не имеют абсолютной ценности, а вот числам прочитанных страниц по прежнему можно доверять.

        Времена показаны на вторых прогонах, на разогретом сервере и виртуальной машине. Количества прочитанных буферов — на свеже-поднятом сервере.
























































        Radius AVG NPoints Nreq Type Time(ms) Reads Hits
        .01° 1.17

        0.7631

        (0.7615)
        10 000 zcurve

        rtree
        .37

        .46
        1.4397

        2.1165
        9.5647

        3.087
        .0316° 11.6

        7.6392

        (7.6045)
        10 000 zcurve

        rtree
        .39

        .67
        2.0466

        3.0944
        20.9707

        2.7769
        .1° 115.22

        76.193

        (76.15)
        1 000 zcurve

        rtree
        .44

        2.75 *
        4.4184

        6.073
        82.8572

        2.469
        .316° 1145.3

        758.37

        (760.45)
        1 000 zcurve

        rtree
        .59

        18.3 *
        15.2719

        21.706
        401.791

        1.62
        1.° 11310

        7602

        (7615)
        100 zcurve

        rtree
        7.2

        94.5 *
        74.9544

        132.15
        1651.45

        1.12

        где

            Radius — размер поисковой области в градусах

            Npoints — среднее число точек в выдаче, в скобках — теоретически ожидаемое число

             (в сфере 41252.96 кв. градусов, 100 000 000 точек, ~2424 точки на кв. градус)


            Nreq — число запросов в серии

            Type

              ‘zcurve’ — оно и есть

              ’rtree’- PGSphere

            Time(ms) — среднее время выполнения запроса

            Reads — среднее число чтений на запрос

            Hits — число обращений к буферам



            * в какой-то момент производительность R-tree начинает резко

            проседать, связано это с тем, это дерево читает заметно больше

            страниц и его рабочий набор перестаёт помещаться в кэше (по-видимому).



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



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


        • Предположим, что наш куб в среднем вырезает из сферы ту же площадь, что и сфера равного объема

        • Объем единичной сферы 1.33*3.14=4.19

        • Объем куба со стороной 2 = 8.

        • Тогда корень третьей степени из 8/4.19 = 1.24 — это отношение радиусов мнимой сферы к настоящей

        • соотношение площадей мнимой сферы к настоящей 1.24*1.24=1.54

        • имеем из экспериментальных данных 1.17/0.7631= 1.5332

          Bingo!



        Original source: habrahabr.ru (comments, light).

        https://habrahabr.ru/post/338088/

        Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
        rss_rss_hh_new

        Как я проходил собеседования на позицию Junior .Net Developer

        Воскресенье, 17 Сентября 2017 г. 14:21 (ссылка)






        JosefDzeranov


        сегодня в 14:21

        Разработка





        Как я проходил собеседования на позицию Junior .Net Developer










          Приветствую всех. Сегодня расскажу вам как я проходил собеседования в Москве на позицию .Net Developer. Усиленно готовился к собеседованиям месяц, целыми днями сидел и смотрел вопросы и пытался отвечать на них, а также читал книжки по С#. В статье привожу интересные задачки и вопросы, которые мне задавали в разных компаниях в Москве. Заранее скажу, что я попал в ту компанию, в которой хотел. Я прошел 4 собеседования в этой компании и меня наконец то взяли! Много статей было прочитано в частности здесь и надеюсь, что эту статью тоже будут читать начинающие Net разработчики и спрашивать все в комментариях.Кому интересна тема прохождения собеседований, прошу под кат! При поиске работы я пользовался Head Hunter. Там очень много вакансий с подробным изложением того, что хотят фирмы от кандидата. Решил откликнутся практически на все вакансии «C# разработчик», потому что для меня главное было пройти как можно больше собеседований, набраться опыта, а также во время таких собеседованиях найти интересную работу в интересной компании (забегая вперед скажу, что я нашел очень интересную работу). Некоторые компании (всего 2), для того, чтобы откликнуться на предложенную ими вакансию, хотели, чтобы кандидат решил предложенные ими задачи (напоминаю это при отклике). На мой взгляд это даже правильно, ведь это показывает, что компания очень ценит свое время и хочет, чтобы кандидат на собеседовании умел решать простые задачи. Обычно на таких собеседованиях спрашивают более «узкие» вопросы. Практически во всех компаниях есть несколько этапов собеседований. На первом обычно собеседует hr, на второй — старший разработчик, на третьем — технический директор. Бывали компании, в которых на первом же приходили и старший разработчик, и Team Lead и технический директор, что конечно чуть заставляет нервничать. Пройдя 5 собеседований, я выяснил такую вещь: чем позитивнее и свободнее ведешь себя на собеседовании, тем легче и быстрее она проходит.А теперь хочу поделиться с вами тем, какие вопросы мне задавали на очных собеседованиях. Поехали.Я не ожидал так много вопросов по базам данных, мне пришлось быстро осваивать (точнее вспоминать) sql язык. Вот какие вопросы и задания мне задавали:

          1. Что такое кластеризованный и некластеризованный индекс? Когда какое надо использовать?

          2. Что такое Join? Чем он отличается от Left Join, Right Join? Inner Join? Outer Join?

          3. Есть три таблицы: CUSTOMERS (ID, NAME, MANAGER_ID); MANAGERS (ID, NAME); ORDERS (ID, DATE, AMOUNT, CUSTOMER_ID). Написать запрос, который выведет имена Customers и их SalesManagers, которые сделали покупок на общую сумму больше 10000 с 01.01.2013.

          4. Делаем электронный справочник по книгам. Ищем:А) В каком магазине купить данную книгу.Б) В каких магазинах купить книги этого автора (авторов)В) Кто автор книгиГ) Какие книги написал авторНарисовать БД. Написать запрос Б. (Не забыть учесть, что у одной книжки — может быть несколько авторов)

          5. Что такое агрегирующие функции? Операторы Group By, Having? Приведите примеры их использования.

          6. Table «PC» (id, cpu(MHz), memory(Mb), hdd(Gb))1) Тактовые частоты CPU тех компьютеров, у которых объем памяти 3000 Мб. Вывод: id, cpu, memory2) Минимальный объём жесткого диска, установленного в компьютере на складе. Вывод: hdd3) Количество компьютеров с минимальным объемом жесткого диска, доступного на складе. Вывод: count, hdd

          7. Дана следующая структура базы данных в MS SQL: Departments (Id, Name), Employees(Id, DepartmentId, Name, Salary)Необходимо:• Написать запрос получения имени одного сотрудника, имеющего максимальную зарплату в компании, и название его отдела• Получить список отделов, средняя зарплата в которых больше 1000$

          8. Ado Net – что за технология? и как и когда она используется?

          9. Что такое Entity Framework? Какие подходы проектирования БД знаете? Расскажите про Code First.

          Конечно вопросы про ООП

          1. Назовите и объясните основные парадигмы ООП.

          2. Назовите преимущества объектно-ориентированного подхода к программированию перед структурным программированием

          3. Перечислите недостатки ООП парадигмы.

          4. Что такое раннее и позднее связывание?

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

          Вопросы про паттерны проектирования

          1. Расскажите про SOLID и примеры его использования

          2. В чем отличие паттерна «Стратегия» от паттерна «Шаблонный метод»?

          3. Паттерн Адаптер и его применение

          4. Расскажите про паттерн «Фасад»

          Ну и конечно огромное количество вопросов по С#

          1. using (SomeClass sc = new SomeClass()){} Что делает данная конструкция?

          2. int i = 1; Console.WriteLine(«i = {0}», ++i); Что выведет данный код?

          3. Различие класса и структуры? И что будет если их передать в метод в виде параметров?

          4. Задача: есть нули и единицы в массиве. Надо для каждого нуля посчитать сколько единиц правее него и вывести сумму таких чисел. Сделать за один проход.

          5. Различие абстрактного класса и интерфейса? Можно ли отказаться от интерфейсов и использовать только абстрактный класс, ведь мы можем в абстрактном классе просто указать сигнатуры методов?

          6. Что такое интернирование строк ?

          7. Расскажите про интерфейс IEnumerable? Зачем он используется?

          8. Когда мы можем пройтись по собственной коллекции foreach- ом? Что для этого надо сделать и почему? (Рассказать про утиную типизацию)

          9. Различие между IEnumerable and IQueryable ?

          10. Как устроен Dictionary внутри? Как борются с коллизиями?

          11. Есть обычный пользовательский класс. Нужно его использовать как ключ в Dictionary. Что для этого надо поменять (добавить) в классе ?

          12. Какова алгоритмическая сложность для операций чтения и записи для коллекции Dictionary?

          13. В чем различие между ключевыми словами «ref» и «out»?

          14. Расскажите как работает try, catch, finally? Когда вызывается каждый

          15. Чем отличаются друг от друга классы String и StringBuilder? Зачем нужно такое разделение?

          16. Какие отличие между значимыми и ссылочными типами? Зачем придумали такое разделение? Нельзя было придумать только либо значимые либо ссылочные?

          17. В чем отличие использования Finalize и Dispose?

          18. Что такое управляемый код и CLR? Основные требования к управляемому коду?

          19. Что такое assembly manifest (манифест сборки)?

          20. Что такое Boxing и Unboxing?

          21. В чем суть полиморфизма?

          22. Чем отличается event от delegate?

          23. Может ли класс реализовать два интерфейса, у которых объявлены одинаковые методы? Если да, то каким образом?

          24. Что такое абстрактный класс? В каком случае вы обязаны объявить класс абстрактным?

          25. В чем разница инкапсуляции и сокрытия?

          26. Что такое частные и общие сборки?

          27. Что такое .Net Framework?

          28. LINQ lazy loading, eager loading в чем разница?

          29. Можно ли запретить наследование от своего собственного класса?

          30. Определение паттерна синглтон

          31. Что такое интеграционные тесты и unit-тесты?

          32. Что такое MVC, MVVM, WEB API?

          33. Каким образом можно присвоить значения полям, которые помечены ключевым словом readonly?

          34. Когда вызывается статический конструктор класса?

          35. Чем отличаются константы и поля, доступные только для чтения?

          36. Чем отличаются константы и поля, доступные только для чтения?

          37. Разница между асинхронностью и параллельностью?

          38. У вас есть сайт, вы заметили что он долго отвечает, как вы будете искать причину?

          Ну и как же без логических задач

          1. Вы находитесь в пустом поезде. Это даже не поезд, а просто вагоны, они сцеплены друг с другом. Все вагоны внутри одинаковы, двери на выход из вагона закрыты, через окна ничего не видно. Вы можете включать и выключать свет в вагоне, в котором находитесь, можете сходить в соседний вагон, там тоже можно включать или выключать свет. Вам известно, что вагоны стоят на кольце и сами сцеплены в кольцо, первый вагон сцеплен с последним, ходить по кругу можно сколько угодно. В момент начала решения задачи в каких-то вагонах свет уже горит, в каких-то — не горит.Ваша задача при помощи управления светом в вагонах и перемещения по ним узнать сколько в этом кольце вагонов.

          2. У вас есть 100 монет по одному рублю. Они все лежат на столе. У вас также есть два носка. Вам нужно распределить все монеты по 2 носкам, так чтобы в одной из них было в два раза больше монет, чем во второй, при этом

            • не разрешается ломать их (они должны остаться целыми)

            • надо использовать все 100 монет (прятать нельзя)

            • они все одинаковые (по весу, по виду)


          Также в одной компании дали готовый пользовательский класс. Мне нужно было найти логические и синтаксические ошибки. К сожалению, это задание мне не дали с собой взять после собеседования и из-за этого не могу опубликовать, но я помню, что там можно было докопаться практически к каждой строчке!В другой компании, попросили спроектировать базу данных для приложения вроде «Инстаграмм». Потом попросили написать сигнатуру метода «Upload», который отправляет фото на сервер. Прозвучал также вопрос что, если бы руководство изменило вот «это», то как бы вы «переспроектировали» эту базу. Ну так как у меня нет опыта в проектировании, мне пришлось на ходу думать и генерировать идеи, как оказалось, я прошел это собеседование).Другая компания решила дать интересную задачу. Я думаю, что это часть задачи, которую решают внутри компании. Решили проверить, как решают другие. Вот как она звучит: Реализовать программу анализа текста. Входной текст произвольный и может быть большим по объему. Количество и содержание метрик определяется самостоятельно. Требования к алгоритму: Программа должна быть расширяема к изменению списку метрик. Масштабируемость. На что обращаем внимание и что анализируем:

          1. Какие метрики предложены кандидатом и их смысл — аналитическое мышление

          2. SOLID анализ предложенного решения — навыки проектирования

          3. Какие шаблоны применены для масштабируемости и расширяемости — архитектурные скилы кандидата. повод при общении затронуть более глубоко вопрос проектирования

          4. Какие синтаксические конструкции языка применены и какая технология используется — использование сахара и средств упрощения кода

          5. Написаны ли unit тесты — что и как тестирует, какие фреймворки и стили тестов использует

          6. Сравнение с когнитивными сервисами — знание трендов применения технологий в реальных проектах

          7. Время, сложность решения, активность дополнительных вопросов выполнения — заинтересованность к решаемым задача/получению оффера

          Так же хочется отметить тот факт, что в своем резюме я указал, что занимаюсь олимпиадным программированием и это очень положительно повлияло на ход многих собеседований. Меня просили рассказать, что это такое. Меня удивило, что большинство интервьюверов не знали про такое движение в программировании. Те, кто знали, просили меня реализовать какие- нибудь сортировки (пузырьковая, вставками, qsort), задачи с олимпиадного программирования. Я считаю, что алгоритмы и структуры данных дают огромный плюс в жизни программиста и теперь как оказалось еще и при трудоустройстве.Также положительным фактом оказалось преподавание информатики в ВЦНМО. Расспрашивали каково преподавать и трудно ли объяснять сложные вещи на пальцах.Для меня было неожиданностью, что меня пригласили работать практически все компании (80%), в которых я проходил собеседование. Может это чувство из-за моей низкой самооценки?! После прохождения собеседований, с уверенностью могу сказать, что это несложно, а даже легко и интересно. Так что друзья, не бойтесь собеседований и крупных компаний, будьте самоуверенными, верьте в свои силы и все будет на 5!Для тех, кто будет готовится или уже готовится к собеседованиям, ниже перечислю ссылки, которые помогут вам (по моему мнению) подготовится к собеседованию на должность Junior C# Developer, .Net Developer.

          1. metanit.com/sharp. Здесь собран большой материал по C#, А также есть специальный раздел «Вопросы к собеседованию». Рекомендую пока пройти теоретический материал, а потом попробовать тесты. Тесты находятся здесь (https://metanit.com/sharp/interview/).

          2. www.quizful.net/test. Сайт направлен именно на собеседования по разным направлениям разработки, где вы также сможете найти и C#. Там есть очень много «острых» и хитрых вопросов.

          3. CLR via C#. Программирование на платформе Microsoft.NET Framework 4.5 на языке C#. Джефри Рихтер. Эта классическая книга по освоению .Net. Там очень хорошо написано про CLR, про сборки и манифесты. Книга написано на довольно простом языке.

          4. metanit.com/sql. Здесь довольно хорошо и просто описывается язык запросов SQL.

          5. www.w3schools.com/sql/default.asp Здесь также можете пройти туториал по SQL. В конце будет тест, который очень легко сдать(опять- таки, это лично субъективное мнение).

          6. tproger.ru/articles/problems Здесь собраны наиболее интересные логические задачи с ответами.

          7. ivinsky.livejournal.com/3266.html здесь собраны задачи по C#, которые часто бывают на собеседованиях

          8. oignatov.blogspot.ru/2015/10/net-developer.html здесь собраны задачи по C#, которые часто бывают на собеседованиях

          9. jopr.org/blog/detail/voprosy-na-sobesedovanii-po-c здесь собраны задачи по C#, которые часто бывают на собеседованиях



          Original source: habrahabr.ru (comments, light).

          https://habrahabr.ru/post/338102/

          Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
          rss_rss_hh_new

          О смарт-контрактах простыми словами

          Пятница, 15 Сентября 2017 г. 11:55 (ссылка)




          Ramon


          сегодня в 11:55

          Разработка





          О смарт-контрактах простыми словами










            Добрый день! Ранее у нас в блоге были посты на блокчейн темы, в которых нередко возникали дискуссии о распределенных вычислениях в блокчейне. По мотивам этих дискуссий и возник этот пост.



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



            О концепте смарт-контрактов



            Термин «смарт-контракт» уже устоялся и по сути обозначает определенный код, который выполняется на какой-либо блокчейн-платформе таким образом, что его выполнение проверяется независимыми сторонами.



            Что это значит? Это распределенные вычисления? В привычном нам понимании все же нет.



            image



            Когда мы говорим о распределенных вычислениях, обычно подразумевается распределение нагрузки. Скажем, у нас есть задача посчитать в огромном текстовом файле вхождения определенного слова. Мы режем файл на несколько частей, раздаем эти части на разные ноды (например, используя Hadoop), каждая выполняет подсчет и выдает ответ. Мы суммируем ответы и получаем результат. Таким образом мы значительно ускоряем выполнение задачи.



            Если же говорить о смарт-контрактах, то тут совсем другая ситуация. Тут мы не режем файл на отдельные части, мы каждой ноде отдаем весь файл целиком, и каждая нода выдает нам один и тот же результат (в идеале). Вернемся к нашему вопросу: попадает ли такое действие под определение распределенных вычислений? Ну в целом почему нет? Они же распределены и они же вычисления? Только в данном случае мы говорим не о распределении нагрузки, а о распределении доверия.



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



            Классический пример подобного контракта, описанный еще в 1996 году Ником Сабо, — вендинг-машина. Она работает всегда автоматически по строгому набору правил: вы вносите деньги, делаете выбор — машина отдает товар. Внеся деньги, вы не можете передумать и попросить их вернуть. В случае с умным контрактом код становится своего рода законом, его нельзя оспорить, и он всегда будет выполняться при наступлении необходимых условий.



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



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



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



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



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



            Техническая сторона вопроса



            Теперь попробуем поговорить о технической стороне реализации смарт-контрактов на примере блокчейн Ethereum. Как выглядит процесс написания, публикации и выполнения смарт-контракта?



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



            Сам код выполняется в так называемом Ethereum Virtual Machine (EVM). Надо обратить внимание, что код выполняется и проверяется всеми участниками системы, потому необходим некий механизм, который как-то ограничит потребление ресурсов каждым смарт-контрактом (иначе можно бесконечный цикл написать). Потому в Ethereum введена сущность gas (топливо). Контракт в Ethereum может выполнять любые инструкции, вызывать другие контракты, писать и читать данные и так далее. Все эти операции потребляют топливо, топливо оплачивается криптовалютой (Ether). Цена на топливо криптовалюты Ethеr формируется динамически рынком. Триггером выполнения контракта является транзакция. Стоимость топлива, которое сжигается в определенной транзакции, снимается с аккаунта, который транзакцию запустил. Кроме того, есть лимит потребления топлива, сделан он для того, чтобы защитить аккаунт от ошибок в написании контракта, которые могут привести к бесконтрольному сгоранию всей криптовалюты на данном аккаунте.



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


            Original source: habrahabr.ru (comments, light).

            https://habrahabr.ru/post/337984/

            Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
            rss_rss_hh_new

            Ежемесячная рубрика «Читаем статьи за Вас». Август 2017

            Четверг, 14 Сентября 2017 г. 14:09 (ссылка)




            grisme


            сегодня в 14:09

            Разработка





            Ежемесячная рубрика «Читаем статьи за Вас». Август 2017










              image



              Привет, Хабр!

              С этого выпуска мы начинаем хорошую традицию: каждый месяц будет выходить набор рецензий на некоторые научные статьи от членов сообщества Open Data Science из канала #article_essence. Хотите получать их раньше всех — вступайте в сообщество ODS!

              Статьи выбираются либо из личного интереса, либо из-за близости к проходящим сейчас соревнованиям. Если вы хотите предложить свою статью или у вас есть какие-то пожелания — просто напишите в комментариях и мы постараемся всё учесть в дальнейшем.



              Статьи на сегодня:




              1. Fitting to Noise or Nothing At All: Machine Learning in Markets

              2. Learned in Translation: Contextualized Word Vectors

              3. Create Anime Characters with A.I. !

              4. LiveMaps: Converting Map Images into Interactive Maps

              5. Random Erasing Data Augmentation

              6. YellowFin and the Art of Momentum Tuning

              7. The Devil is in the Decoder

              8. Improving Deep Learning using Generic Data Augmentation

              9. Learning both Weights and Connections for Efficient Neural Networks

              10. Focal Loss for Dense Object Detection

              11. Borrowing Treasures from the Wealthy: Deep Transfer Learning through Selective Joint Fine-tuning

              12. Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks



              1. Fitting to Noise or Nothing At All: Machine Learning in Markets



              Оригинал статьи

              Автор: kt{at}ut{dot}ee



              Это рецензия на статью, в которой диплернингом предсказываются финансовые рынки. Автор поста (далее — ZHD) указывает на следующие очевидные глупости данной и схожих статей:




              • Притягивание за уши показателя accuracy методом взятия максимума из всех экспериментов. Медиана, наоборот, как раз соответствует случайному предсказанию.

              • Хвастовство "хорошими результатами", которые получены на инструментах, которые сейчас вообще не торгуются (т.е. у них константная цена). В целом, ZHD рекомендует сравнивать трейдинговые модели не со случайным предсказателем, а со стратегией buy and hold.

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

              • Авторы не учитывают время работы бирж (в том числе, очные сессии для сделок (trading pits)) и по мнению ZHD это неправильно.



              2. Learned in Translation: Contextualized Word Vectors



              Оригинал статьи

              Код

              Автор: kt{at}ut{dot}ee



              Трансфер лернинг в наше время — стандартный прием. Взять сетку, натренированную на породах болонок из ImageNet, и прикрутить её куда-то для распознавания типов соплей — это уже стандартная программа для всех мамкиных диплёрнеров. В контексте обработки текста, трансфер лернинг обычно менее глубокий и упирается в использование заготовленных векторов слов типа Word2Vec, GloVe итд.



              Авторы статьи предлагают углубить текстовый трансфер лернинг на один уровень следующим образом:




              • Натренируем LSTM-based seq2seq модель (вида encoder + decoder with attention over encoder hidden states) для перевода, скажем, с английского на немецкий.

              • Возьмем из неё только encoder (он будет простенького вида LSTM(Embedding(word_idxs)). Этот энкодер умеет превращать последовательность слов в последовательность LSTM hidden states. Т.к. эти hidden states взяты не случайно (их переводческая модель использует в своём аттеншене), то однозначно в них будет полезный сигнал.

              • Ну и всё, давайте теперь строить любые другие текстовые модели, которым мы на вход будем скармливать не только GloVe векторы слов, но и приклеенные к ним соответствующие LSTM hidden векторы из нашего переводческого энкодера (их мы будем называть Context Vectors, CoVe).



              Далее авторы наворачивают какую-то нетривиальную модель c biattention и maxout (видимо, завалялась с их прошлой работы) и сравнивают, как она работает в разных задачах, если ей на входе скормить случайный эмбеддинг, GloVe, GloVe+CoVe, GloVe+CoVe+CharNGramEmbeddings.



              По результатам кажется, что добавление CoVe повышает точность голого GloVe примерно на 1%. Иногда эффект меньше, иногда отрицательный, иногда добавление вместо CoVe в модель CharNGrams работает так же или даже лучше. В любом случае, совмещение GloVe+CoVe+CharNGrams работает точно лучше всех других методов.



              image



              На мой взгляд, из-за того, что авторы навернули нехилую модель с аттеншеном поверх сравниваемых типов эмбеддинга (GloVe vs CoVe), замер эффекта полезности CoVe получился излишне зашумленным и не очень убедительным. Я бы предпочел увидеть более "лабораторный" замер.



              3. Create Anime Characters with A.I. !



              Оригинал статьи

              Сайт

              Автор: kt{at}ut{dot}ee



              Существует сайт Getchu, на котором собраны "профили" анимешных героев различных японских игр с картинками-иллюстрациями. Эти картинки можно скачать.



              Для нахождения лица на картинке можно использовать некую тулзу "lbpcascade animeface". Таким образом авторы получили 42к анимешных лиц, которые они потом ручками пересмотрели и выкинули 4% плохих примеров.



              Имеется некая уже готовая CNN-модель Illustration2Vec, которая умеет распознавать на анимешных картинках свойства типа "улыбка", "цвет волос", итд. Авторы использовали её для того, чтобы отлейблить картинки и выбрали 34 интересующих их тэга.

              Авторы запихнули это всё в DRAGAN (Kodali et al, где это отличается от обычных GAN авторы не углубляются, видимо, непринципиально).

              Чтобы уметь генерировать картинки с заданными атрибутами, авторы делают как в ACGAN:




              • Кормят генератору вектор атрибутов.

              • Заставляют дискриминатор этот вектор предсказывать.

              • Дополнительно штрафуют генератор пропорционально тому, насколько дискриминатор не угадал верный класс.



              И генератор, и дискриминатор — довольно замороченные конволюционные SRResNet-ы (у генератора 16-блоковый, у дискриминатора 10-блоковый). У дискриминатора авторы убрали батчнорм-слои "since it would bring correlations within the mini-batch, which is undesired for the computation of the gradient norm." Я не очень понял эту проблему, поясните если вдруг кому ясно.

              Тренировалось всё Адамом с уменьшающимся lr начиная от 0.0002, не очень понятно как долго.

              Для вебаппа авторы сконвертировали сеть под WebDNN (https://github.com/mil-tokyo/webdnn) и поэтому генерят все картинки прямо в браузере на клиенте (!).



              4. LiveMaps: Converting Map Images into Interactive Maps



              [Оригинал статьи](http://dl.acm.org/citation.cfm?id=3080673, https://doi.org/10.1145/3077136.3080673)

              Статья — победитель Best Short Paper Awart SIGIR 2017

              Автор: zevsone



              Предложена принципиально новая система (LiveMaps) для анализа изображений карт и извлечения релевантного viewport'a.



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



              LiveMaps работает в несколько приемов. Сперва проверяется является ли изображение картой.

              Если "да", система пытается определить геолокацию этого изображения. Для определения локации используется текстовая и визуальная информация извлеченная из изображения. В итоге, система создает интерактивную карту, отображающую географическую область, вычисленную для изображения.



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



              P.S. Совсем не ожидал получить best short paper award на такой маститой конфе (121 short paper в претендентах в этом году, все industry гиганты).



              5. Random Erasing Data Augmentation



              Оригинал статьи

              Автор: egor.v.panfilov{at}gmail{dot}com



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



              Аугментация параметризовалась 4-мя параметрами: (P_prob) вероятность применения к каждой картинке батча, (P_area) размер региона (area ratio), (P_aspect) соотношение сторон региона (aspect ratio), (P_value) заполняемое значением: случайные / среднее на ImageNet / 0 / 255.



              image



              Авторы провели оценку влияния данного метода аугментации на 3-х задачах: (A) object classification, (B) object detection, © person re-identification.



              (A): Использовались 6 архитектур, начиная с AlexNet, заканчивая ResNeXt. Датасет — CIFAR10/100. Оптимальное значение параметров: P_prob = 0.5, P_aspect = в широком диапазоне, но желательно не 1(квадрат), P_area = 0.02-0.4 (2-40% изображения), P_value = random или среднее на ImageNet, для 0 и 255 результаты существенно хуже. Сравнили также с другими методами и аугментации (random cropping, random flipping), и регуляризации (dropout, random noise): в порядке снижения эффективности — всё вместе, random cropping, random flipping, random erasing. Drouput и random noise данный метод уделывет "в щепки". В целом, метод не самый мощный, но при оптимальных параметрах стабильно даёт 1% точности (5.5% -> 4.5%). Также пишут, что он повышает робастность классификатора к перекрытиям объектов :you-dont-say:.



              (B): Использовалась Fast-RCNN на PASCAL VOC 2007+2012. Реализовали 3 схемы: IRE (Image-aware Random Erasing, также выбираем регион для зануления вслепую), ORE (Object-aware, зануляем только части bounding box'ов), I+ORE (и там, и там). Существенной разницы по mAP между этими методами нет. По сравнению с чистым Fast-RCNN, дают порядка 5% (67->71 на VOC07, 70->75 на VOC07+12), столько же, сколько и A-Fast-RCNN. Оптимальные параметры — P_prob = 0.5, P_area = 0.02-0.2 (2-20%), P_aspect = 0.3-3.33 (от лежачей до стоячей полоски).



              ©: Использовались ID-discim.Embedding (IDE), Triplet Net, и SVD-Net (все на базе ResNet, предобученной на ImageNet) на Market-1501 / DukeMTMC-reID / CUHK03. На всех моделях и датасетах аугментация стабильно даёт не менее 2% (до 8%) для Rank@1, и не менее 3% (до 8%) для mAP. Параметры те же, что и для (B).



              В целом, несмотря на простоту метода, исследование и статья довольно аккуратные и подробные (10 страниц), с кучей графиков и таблиц. Порадовали китайцы, ничего не скажешь.



              6. YellowFin and the Art of Momentum Tuning



              Оригинал статьи

              Дополнительный материал про momentum

              Автор: Arech



              Давно я её читал, поэтому очень-очень поверхностно: после вдумчивого курения свойств классического моментума (он же моментум Бориса Поляка), на одномерных строго выпуклых квадратичных целях чуваки вывели (или нашли у кого-то?) неравенство, связывающее коэффициенты learning rate и моментума так, чтобы они попадали в некий "робастный" регион, гарантирующий наибыстрейшее схождение алгоритма SGD. Потом показали(?), что оное утверждение в принципе может как-то выполняться и для некоторых невыпуклых функций, по крайней мере в некоторой их локальной области, которую можно более-менее апроксимировать квадратичным приближением. После чего решили запилить свой тюнер YellowFin, который на основании знания предыдущей истории изменения градиента, апроксимировал бы нужные для неравенства характеристики поверхности функции ошибки (дисперсия градиента, некая "обощённая" кривизна поверхности и расстояние до локального минимума квадратичной апроксимации текущей точки) и, с помощью этих апроксимаций, выдавал бы подходящие значения learning rate и моментума для использования в SGD.



              Также, изучив вопрос асинхронной (распределённой) тренировки сетей, чуваки предложили обобщение своего метода (Closed-loop YellowFin), которое учитывает, что реальный моментум в таких условиях оказывается больше запланированного.



              Тестировали свёрточные 110- и 164-слойные ResNet на CIFAR10 и 100 соответственно, и какие-то LSTM на PTB, TS и WSJ. Результаты интересные (от х1.18 до х2.8 ускорения относительно Адама), но, как обычно, есть вопросы к постановке эксперимента — грубый подбор коэффициентов для компетиторов, + емнип, только один прогон на каждую архитектуру, + показаны результаты только тренировочного набора… Короче, есть к чему докопаться...



              Как-то так, надеюсь, по деталям не сильно наврал.



              Я подумывал запилить его к своей либине, но крепко влип в Self-Normalizing Neural Networks (SELU+AlphaDropout), которыми занялся чуть раньше и которые оказались мне крайне полезны, поэтому пока руки не дошли. Слежу за тем тредом в Lesagne (https://github.com/Lasagne/Lasagne/issues/856 — у человека возникли проблемы с воспроизводством результатов) и вообще, надеюсь, что будет больше инфы по воспроизводству их результатов. Так что если кто попробует — делитесь чокак.



              7. The Devil is in the Decoder



              Оригинал статьи

              Автор: ternaus



              Вопрос с тем, какой UpSampling лучше для различных архитектур, где есть Decoder, теребит умы многих, особенно тех, кто борется за пятый знак после запятой в задачах сегментации, super resolution, colorization, depth, boundary detection.



              Ребята из Гугла и UCL заморочились и написали статью, где эмпирическим путем решили проверить кто лучше и найти в этом логику.



              Проверили — выяснилось, что разница есть, но логика не очень просматривается.



              Для сегментации:



              [1] Transposed Conv = Upsampling + Conv и который все яростно используют в Unet норм.

              [2] добрасывание skiped connections, то есть, трансформация SegNet => Unet железобетонно добрасывает. Это интуитивно понятно, но тут есть циферки.

              [3] Такое ощущение, что Separable Transposed, которое Transposed, но с меньшим числом параметоров для сегментации, работает лучше. Хотелось бы, чтобы народ в #proj_cars это проверил.

              [4] Хитроумный Bilinear additive Upsampling, который они предложили, на сегментации работает примерно как [3]. Но это тоже в сторону коллектива из #proj_cars проверить

              [5] Они добрасывают residual connections куда-то, что тоже в теории может что-то добавить, но куда именно — не очень понятно, и добрасывает очень неуверенно и не всегда.



              Для задач сегментации они используют resnet 50 как base и потом сверху добавляют decoder.



              Для задачи instance boundary detection они решили выбрать метрику, при которой меньше оверфитишь на алгоритм разметки + циферки побольше получаются.

              То есть, During the evaluation, predicted contour pixels within three from ground truth pixels are assumed to be correct. Что сразу ставит вопрос о том, как это все переносится на задачи, где важен каждый пиксель. (Тут вспоминается Костин трюк со спутников для поиска заборов толщиной в один пиксель и то, как народ борется за +-1 пиксель на границах в задаче про машинки)



              [6] У всех сетей, что они тренируют, у весов используется L2 регуляризация порядка 0.0002

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



              Summary:

              [1] Вопрос о том, кто и когда лучше они подняли, но не ответили.

              [2] Они предложили еще один метод делать Upsampling, который работает не хуже других.

              [3] Подтвердили, что skipped connection однозначно помогают, а residual — в зависимости от фазы луны.



              Ждем месяц, о том, что скажет человеческий GridSearch на #proj_cars.



              8. Improving Deep Learning using Generic Data Augmentation



              Оригинал статьи

              Автор: egor.v.panfilov{at}gmail{dot}com



              Эпиграф: Лавры китайцев не дают покоя никому, даже на чёрном континенте. Хороших компьютеров, правда, пока не завезли, но Тернаус велел писать, "и вот они продолжают".



              Авторы попытались провести бенчмарк методов аугментации изображений на задаче классификации изображений, и выработать рекомендации по их использованию для различных случаев. В первом приближении, данные методы разделить на 2 категории: Generic (общеприменимые) и Complex (использующие информацию о домене / генеративные). В данной статье рассматриваются только Generic.



              Все эксперименты в статье проводились на Caltech-101 (101 класс, 9144 изображения) с использованием ZFNet (половина информативной части статьи о том, как лучше всего обучить ванильную ZFNet). Обучали 30 эпох, используя DL4j. Рассматриваемые методы аугментации: (1) без аугмен-ции, (2-4) геометрические: horizontal flipping, rotating (-30deg и +30deg), cropping (4 угловых кропа), (5-7) фотометрические: color jittering, edge enhacement (добавляем к изображению результат фильтра Собеля), fancy PCA (усиливаем principal компоненты на изображениях).



              Результаты: к бейзлайну (top1/top5: 48.1%/64.5%) (a) flipping даёт +1/2%, но увеличивает разброс точности, (b) rotating даёт +2%, © cropping даёт +14%, (d) color jittering +1.5/2.5%, (d-e) edge enhancement и fancy PCA по +1/2%. Т.е. среди геометрических методов впереди cropping, среди фотометрических — color jittering. В заключении авторы пишут, что существенное улучшение точности при аугментации cropping'ом может быть связано с тем, что датасет получается в 4 раза больше исходного (сбалансировать-то не судьба). Из положительного — не забыли 5-fold кросс-валидацию при оценке точности моделей. Почему были выбраны конкретно эти методы аугментации среди других (в т.ч. более популярных) узнаем, видимо, в следующей статье.



              9. Learning both Weights and Connections for Efficient Neural Networks



              Оригинал статьи

              Автор: egor.v.panfilov{at}gmail{dot}com



              Статья рассматривает проблему выского потребления ресурсов современными архитектурами DNN (в частности, CNN). Самый главный бич — это обращение к динамической памяти. Например, инференс сети с 1 млрд связей на 20Гц потребляет ~13Вт.



              Авторы предлагают метод снижения числа активных нейронов и связей в сети — prunning. Работает следующим образом: (1) обучаем сеть на полном датасете, (2) маскируем связи с весами ниже определённого уровня, (3) дообучаем оставшиеся связи на полном датасете. Шаги (2) и (3) можно и нужно повторять несколько раз, так как агрессивный (за 1 подход) prunning показывает результаты немного хуже (для AlexNet на ImageNet, например, 5x против 9x). Хитрости: использовать L2-регуляризацию весов, при дообучении уменьшать dropout, уменьшать learning rate, прунить и дообучать CONV и FC слои раздельно, выкидывать мёртвые (non-connected) нейроны по результатам шага (2).



              Эксперименты производились в Caffe с сетями Lenet-300-100, Lenet-5 на MNIST, AlexNet, VGG-16 на ImageNet. На MNIST: уменьшили число весов и FLOP'ов в 12 раз, а также обнаружили, что prunning проявляет свойство механизма attention (по краям режет больше). На ImageNet: AlexNet обучали 75 часов и дообучали 173 часа, VGG-16 прунили и дообучали 5 раз. По весам удалось сжать в 9 и 13 раз соответственно, по FLOP'ам — в 3.3 и 5 раз. Интересен профиль того, как прунятся связи: первый CONV-слой ужимается меньше чем в 2 раза, следующие CONV — в 3 и более (до 12), скрытые FC — в 10-20 раз, последний FC слой — в 4 раза.



              В заключение, авторы приводят результаты сравнения различных методов prunning'а (с L1-, L2-регуляризацией, с дообучением и без, отдельно по CONV, отдельно по FC). Вкратце, есть лень прунить, то учите сеть с L1, и половину слоёв можно просто выкинуть. Если не лень — только L2, прунить и дообучать итеративно ~5 раз. И последнее, хранение весов в sparse виде у авторов давало overhead в ~16% — не то чтобы критично, когда у вас сеть в 10 раз меньше.

              image



              10. Focal Loss for Dense Object Detection



              Оригинал статьи

              Автор: kt{at}ut{dot}ee



              Как известно, процесс поиска моделей в машинном обучении упирается в оптимизацию некой целевой функции потерь. Самая простая функция потерь — процент ошибок на тренинг-сете, но её оптимизировать сложно и результат статистически плох, поэтому на практике используют разные суррогатные лоссы: квадрат ошибки, минус логарифм вероятности, экспонента от минус скора, hinge loss и т.д. Все суррогатные лоссы являются монотонными функциями, штрафующими ошибки тем больше, чем больше величина ошибки. Любой лосс можно интерпретировать как вид распределения целевой переменной (например, квадрат ошибок соответствует гауссовому распределению).



              Авторы работы обнаружили, что суррогатный лосс вида



              loss(p, y) := -(1-p)^gamma log(p) if y == 1 else -p^gamma log(1-p)



              ещё нигде не использовался и не публиковался. Зачем нужно использовать именно такой лосс, а не ещё какой-нибудь, и каков смысл подразумеваемого распределения, авторы не знают, но им он кажется прикольным, т.к. здесь есть лишний параметр gamma, с помощью которого можно как будто бы подкручивать величину штрафа "легким" примерам. Авторы назвали эту функцию "focal loss".



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



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



              Альтернативное мнение

              Следи за руками: чуваки взяли один из стандартных, довольно сложных датасетов, на которых меряются в детекции, взяли простенькую сеть без особых наворотов (то из чего все другие уже пробовали выжать сколько могли), приложили свой лосс и получили сходу результат single model без мультскейла и прочих трюков выше чем все остальные на этом датасете, включая все сети в одну стадию и более продвинутые двухстадийные. Чтобы убедиться, что дело в лоссе, а не чём-то ещё, они попробовали другие варианты, которые до этого были крутыми и модными техниками — балансирование кросс-энтропии, OHEM и получили результат стабильно выше на своём. Покрутили параметры своего и нашли вариант, который работает лучше всех и даже попробовали чуток объяснить почему (там есть график, где видно что гамма ниже 2 даёт довольно гладкое распределение, а больше двух уж очень резко штрафует (даже при двух там практически полка, удивительно что работает)).

              Конечно, можно было им начать сравнивать 40 вариантов сетей, с миллионом вариантов гиперпараметров и на всех известных датасетах, да ещё и кроссвалидацию 10 раз по 10 фолдов, но сколько бы это времени тогда заняло и когда была бы публикация готова и сколько бы там было разных идей?

              Тут всё просто — изменили один компонент, получили результат превосходящий SoTA на конкретном датасете. Убедились, что результат вызван изменением, а не чем-то ещё. Fin.



              Альтернативное мнение

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



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



              В любом случае, я для себя никак не могу вынести из этой статьи обещанный в заглавии и тексте тезис "вкручивайте такой лосс везде и будет вам счастье".



              Тезис "RetinaNet хорошо работает на COCO (с любым лоссом, причем!)" я, при этом, вынести вполне могу.



              11. Borrowing Treasures from the Wealthy: Deep Transfer Learning through Selective Joint Fine-tuning



              Оригинал статьи

              Код

              Автор: movchan74



              image



              Авторы сосредоточились на проблеме классификации изображений с небольшим датасетом. Типичный подход в таком случае следующий: взять предобученную CNN на ImageNet и дообучить на своем датасете (или даже дообучить только классификационные полносвязный слои). Но при этом сеть быстро переобучается и достигает не таких значений точности, каких хотелось бы. Авторы предлагают использовать не только целевой датасет (target dataset, мало данных, далее буду называть датасет T), но и дополнительный исходный датесет (source dataset, далее буду называть датасет S) с большим количеством изображений (обычно ImageNet) и обучать мультитаск на двух датасетах одновременно (делаем после CNN две головы по одной на датасет).



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



              Получаем следующий фреймворк:




              1. Берем два датасета: S и T. T — датасет с малым количеством примеров, для которого нам необходимо получить классификатор, S — большой вспомогательный датасет (обычно ImageNet).

              2. Выбираем подмножество изображений из датасета S, такое, что изображения из подмножества близки к изображениям из целевого датасета T. Как именно выбирать близкие рассмотрим далее.

              3. Учим мультитаск сеть на датасете T и выбранном подмножесте S.



              Рассмотрим как предлагается выбирать подмножество датасета S. Авторы предлагают для каждого семпла из датасета T находить некоторое количество соседей из S и учиться только на них. Близость определяется как расстояние между гистограммами низкоуровневых фильтров AlexNet или фильтров Габора. Гистограммы берутся, чтобы не учитывать пространственную составляющую.



              Объяснение, почему берутся низкоуровневые фильтры, приводится следующее:




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

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

                Мне, если честно, эти объяснения не очень нравятся, но в статье так. Может я конечно что-то не понял или понял не так. Это все описано на 2 странице после слов "The motivation behind selecting images according to their low-level characteristics is two fold".



              Еще из особенностей поиска близких изображений:




              1. Гистограммы строятся так, чтобы в среднем по всему датасету в один бин попадало примерно одинаковое количество.

              2. Расстояние между гистограммами считается с помошью KL-дивергенции.



              Авторы попробовали разные сверточные слои AlexNet и фильтры Габора для поиска близких семплов, лучше всего получилось если использовать 1+2 сверточные слои из AlexNet.



              Также авторы предложили итеративный способ подбора количества похожих семплов из датасета S для каджого семпла из T. Изначально берем некоторое заданое число ближайших соседей для каждого отдельного семпла из T. Затем прогоняем обучение, и если ошибка для семпла большая, то увеличиваем количество ближайших соседей для этого семпла. Как именно производится увеличение ближайших соседей понятно из уравнения 6.



              Из особенностей обучения. При формировании батча случайно выбираем семплы из датасета T, и для каждого выбранного семпла берем одного из его ближайших соседей.



              Проведены эксперименты на следующих датасетах: Stanford Dogs 120, Oxford Flowers 102, Caltech 256, MIT Indoor 67. На всех датасетах получены SOTA результаты. Получилось поднять точность классфикации от 2 до 10% в зависимости от датасета.



              12. Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks



              Оригинал статьи

              Код

              Автор: repyevsky{at}gmail{dot}com

              Статья про мета-обучение: авторы хотят научить модель объединять свой предыдущий опыт с малым количеством новой информации для решения новых заданий из некоторого общего класса.



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



              В качество бенчмарка для классификации используются два датасета: Omniglot и miniImagenet. В первом рукописные буквы из нескольких алфавитов — всего около 1600 классов, 20 примеров на класс. Во втором 100 классов из Imagenet — по 600 картинок на класс. Ещё есть раздел про RL, но его я не смотрел.



              Перед обучением все классы разбиваются на непересекающиеся множества train, validation и test. Для проверки, из test-классов (которые модель не видела при обучении) выбирается, например, 5 случайных классов (5-way learning). Для каждого из выбранных классов сэмплится несколько примеров, лейблы кодируются one-hot вектором длины 5. Дальше примеры для каждого класса делятся на две части A и B. Примеры из A показываются модели с ответами, а примеры из B используются для проверки точности классификации. Так формируется задание. Авторы смотрят на accuracy.



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



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



              Ключевая идея: обновлять веса модели так, чтобы она давала лучший результат на новых заданиях.

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



              Суть в следующем. Пусть мы хотим, чтобы наша модель F(x, p) обучалась новому заданию за 1 итерацию (1-shot learning). Тогда для обучения нужно из тренировочных классов подготовить такие же задания как на тесте. Дальше на примерах из части A мы считаем loss, его градиент и делаем одну итерацию обучения — в итоге получаем промежуточные обновленные веса p' = p - a*grad и новую версию модели — F(x, p'). Считаем loss для F(x, p') на B и минимизируем его относительно исходных весов p. Получаем настоящие новые веса — конец итерации. Когда считается градиент от градиента :xzibit:, появляются вторые производные.



              На самом деле, генерируется сразу несколько заданий, объединеных в metabatch. Для каждого находится свой p' и считается свой loss. Потом все эти loss суммируются в total_loss, который уже минимизируется относительно p.



              Авторы применили свой подход к базовым моделям из предыдущих работ (маленькие сверточная и полносвязная сети) и получили SOTA на обоих датасетах.



              При этом, итоговая модель получается без дополнительных параметров для мета-обучения. Зато используется большое количество вычислений, в том числе из-за вторых производных. Авторы пробовали отбросить вторые производные на miniImagenet. При этом accuracy осталась почти такой же, а вычисления ускорились на 33%. Предположительно это связано с тем, что ReLU — кусочно-линейная функция и вторая производная у неё почти всегда нулевая.



              Код авторов на Tensorflow: https://github.com/cbfinn/maml. Там внутренний градиентый шаг делается вручную, а внешний с помощью AdamOptimizer.



              За редактуру спасибо yuli_semenova.



              Original source: habrahabr.ru (comments, light).

              https://habrahabr.ru/post/336624/

              Комментарии (0)КомментироватьВ цитатник или сообщество

              Следующие 30  »

              <алгоритмы - Самое интересное в блогах

              Страницы: [1] 2 3 ..
              .. 10

              LiveInternet.Ru Ссылки: на главную|почта|знакомства|одноклассники|фото|открытки|тесты|чат
              О проекте: помощь|контакты|разместить рекламу|версия для pda