> У меня получилось найти АКФ для фликкер-шума, но для ограниченного параметра "альфа". Спасибо справочнику по интегралам Градштейн, Рыжик.
Спасибо!!! А можете еще подсказать,
как я могу на это Ваше сообщение сослаться, если понадобится?
Я пока не знаю, как я смогу эту формулу использовать, но если смогу, то я бы хотел в дополнение к
ссылке на
Градштейн И.С., Рыжик И. М. Таблицы интегралов, сумм, рядов и произведений / Перераб. при участии Ю. В. Геронимуса и М. Ю. Цейтлина. — 5-е изд., стер. — М.: Наука, 1971. — 1108с.
добавить ссылку на "личное сообщение" (в журналах их обычно оформляют в виде подстраничных сносок). Но, в такой ссылке надо указать ФИО автора сообщения. Если Вы не против,
напишите мне данные в ЛС?
В научной публикации такая ссылка будет выглядеть примерно вот так (реальный пример:)
> Надо различать ось времени и ось амплитуд. То, что называют оптимальным приемом (корреляционный прием, согласованный фильтр) не является накоплением при обработке рядов. Это разные вещи.
А вот тут не понял.
Мы при зондировании земной коры пытались просвечивать очаг землетрясения электрическим током. Сперва была идея, что для повышения отношения сигнал/шум надо увеличить мощность источника тока. Для этого на Памир затащили МГД-генератор. Он давал ток в сотни ампер. Но, каждый пуск был праздником. Он требовал большой подготовки и происходил в лучшем случае раз в две недели. А последняя стадия подготовки землетрясения - это часы-сутки (как тогда думали).Т.е. сопротивление очаговой зоны надо измерять ежедневно, хотя бы.
И вот как раз мой многолетний шеф А.Я.Сидорин, насчитавшись книг по радиофизике, предложил вместо однократного жутко сильного импульса послать в породу гораздо более слабый (и поэтому легко генерируемый), но очень длинный знакопеременный сигнал из прямоугольных импульсов длительностью пару секунд каждый, но суммарно длиной в полчаса. А на приемной станции выполнялось измерение напряжения на положительной и отрицательной фазе питающего импульса. И высчитывалась разница между ними. И эта разница суммировалась по паре тысяч импульсов (получасовой цикл). Заодно такая схема решала проблему с поляризацией среды, переходными процессами (ток на выходе МГД-генератора меняется по очень хитрым законам, и такой сигнал не так просто пересчитать в напряжение на приемнике из-за индуктивности), и пр.
В общем, при многократном понижении стоимости и снижении силы тока в 100 раз мы улучшили отношение сигнал/шум на два порядка за счет накопления. Подробности раскиданы по разным работам, но если интересно, можно для начала вот тут посмотреть (текст выложен).
Так вот.
Разве эту схему измерений нельзя называть синхронным детектированием? Мы всегда думали, что можно. И что накопление и синхронное детектирование - это очень близкородственные понятия (хотя и разные, разумеется). Но в нашем случае описанная схема зондирования в каком-то смысле обобщает первое и второе в единый процесс (алгоритм).
Очень длинный коммент мне технически сложно запостить (спасибо, редактор Хабра!)
> При накоплении ведь складываются отсчеты, разнесенные достаточно длинным интервалом времени (...) Если так, то [1] шумовые значения некоррелированы (читай белый шум). Если при этом эти отсчеты [2] имеют нормальную плотность вероятностей, то они и независимы [цифры мои]
К сожалению, оба предположения не выполняются.
[1]. В моем случае корреляция с ростом лага уменьшается, но очень медленно. На самом деле эта скорость определяется значением степенного параметра спектра <альфа>. Пока он маленький (порядка 0.5), все более-менее норм. Корреляция и правда уменьшается настолько быстро, что это даже можно в расчетах использовать. Обосновать не могу, но численное моделирование подтверждает. Например, для метеопараметров такое приближение (в виде поправки к формулам для БШ) отлично работает.
Но вот в моем случае параметр <альфа> обычно
близок к 2.0
Если интересно, вот тут или вот тут есть таблички степенных параметров для сигналов из нашей вотчины. Почти всегда там что-то
от 1.7 до 2.0.
Только если правда туда в эти таблички полезете, то учитывайте, что мы там в считали не степенной параметр спектра мощности <альфа>, а степенной параметр амплитудного спектра к=<альфа>/2. Так как мне хотелось читать спектр в тех же размерных физических единицах, что и исходный сигнал (а не в квадратичных)
Это совершенно типично для большинства рядов в твердой Земле, магнитосфере и пр. Турбулентность тоже, кстати, дает 5/3 (спектр Колмогорова). Но, когда значение <альфа> близко к 2.0, корреляция остается неприемлемо высокой для любых разумных лагов.
Увы.
Я пытаюсь с этим бороться с помощью разных трюков. Например, отрезаю НЧ, оставляю только узкую полосу, потом пытаюсь работать в этой узкой полосе. Благо, после такой процедуры (выделение узкополосного сигнала) дальние корреляции действительно хорошо давятся
Но, с точки зрения здравого математического смыла отписанный трюк больше похож на какое-то надругательство над сигналом. Ведь в ФШ-сигнале нет никаких выделенных частотных полос! Когда я такие полосы искусственно вырезаю - то это же полный произвол! Так как никаких разумных аргументов для выбора этих частотных полос исходный сигнал не содержит.
Я, конечно, пытаюсь отталкиваться от физики изучаемых явлений (в физике-то частоты не равноправны)... но с точки зрения матаппарата это же просто кривая подпорка к неработающему легаси...
Но всем пофиг...
Я в прошлом году пару статей на основе этой идеи написал. Думал, отдам в журнал, там рецензенты прочтут и в ужас придут. А потом, глядишь, и что-нибудь посоветуют.
Однако же замечания и советы были о чем угодно, но только не про этот больной (для меня) вопрос. Обе статьи (в разных журналах!) уже напечатаны. Я уже не знаю, к кому теперь обращаться... Физики меня прокатили, а к математикам лезть - это дословно получится со свиным рылом в калашный ряд (с)
Ну и по пп.[2] все еще проще. Чем ближе степенной параметр [альфа] к 2.0, тем больше распределение
уходит от Гаусса в сторону равномерного
Вот для примера распределения для ФШ рядов с <альфа> = 1 и 2
Примеры ФШ рядов. Степенной параметр 1.0 для первых двух случаев и 2.0 для двух нижних рядов
Для ФШ со степенным параметром 1.0 функция распределения чем-то напоминает гауссиан ;-)
Для ФШ со степенным параметром 2.0 имеем нечто среднее между нормальным и равномерным распределением
Интуитивно это можно понять: чем больше <альфа>, тем сильнее персистентность, тем активнее самоподдерживается тенденция к росту или спаду. В результате сигнал начинает "гулять" от минимума до максимума. В пределе (при <альфа> порядка 4) это уже начинает напоминать линейный тренд, у которого, как известно, распределение равномерное. Ну а в нашем случае (когда <альфа> 1.5..2.0) - что-то промежуточное
А вот тут уже не совсем. Это при работе с искусственными сигналами можно выбрать подходящую полосу частот, приладить туда источник-приемник, и не париться обо всем, что правее-левее. С одной стороны защищаемся найквистом, с другой - ФНЧ, и поехали проходить через квест, имея уровень "бог".
При экспериментальном мониторинге мы чем дольше наблюдаем, тем больше знаем. А проблема ФШ в том, что на любом масштабе времени (при любой длине ряда) наибольшую амплитуду (мощность) имеют периоды, сопоставимые с этой длиной ряда. Поэтому ограничивать спектр со стороны минимальных частот (=максимальных периодов) неверно как философски, так и технически. Философски мы теряем главную ценность данных - продолжительность непрерывно наблюдаемого процесса, а технически - теряем наибольшую часть измеренного сигнала в плане его дисперсии (мощности).
Так что это не выбор. Это данность, с которой приходится жить...
> Мы можем регуляризовать модель, добавив туда малую константу
Я совсем плохой теоретик, поэтому мне непонятно: как добавление этой константы поможет упростить формулы/выкладки. Навскидку - я совсем не уверен, что упростит. Но в любом случае, за идею спасибо. Если когда-нибудь я смогу найти математика, который заинтересуется моими вопросами, то я ему обязательно эту переписку покажу. Возможно, он оценит и использует Вашу идею.
> В реальности имеется проблема оценить эту константу
Ну, для теоретических выкладок можно наверно просто приравнять ее неизвестному малому значению <дельта>.
;-)))
Что же касается практических случаев, то там будет за счастье даже не точные формулы, а хотя бы асимптотика. Возможно, там получится какой-то другой параметр прикрутить, который будет легко оцениваться и даст нужные поправки к решению.
> (и, вообще, подобрать корректную модель такого "плохого" шума).
Тут вопрос в том, что нам надо от эксперимента идти. Мы знаем, что СПМ реальных сигналов ведет себя определенным образом. Больше того, даже знаем некоторые модели процессов (их много!), которые к такой СПМ приводят. Только вот плясать конкретно от этих моделей нельзя, так как их целая куча, и следствия из них разные. Например, модель с независимыми случайными приращениями - это совершенно не то же самое, что модель с перемежаемостью по Тимашеву... Поэтому в идеале надо бы исходить из эмпирик-факта, и только лишь из него...
> И проблема найти интеграл аналитически для любого параметра "альфа".
Тут ничего не могу сказать: я не математик. Но вообще, сидя на берегу реки (с), кажется странным, что такая простая на вид задачка может представлять реальную трудность. Возможно, она просто была особо никому не нужна?
> Согласитесь, интегрировать константу N0 проще, чем витиеватую СПМ фликкер-шума?
Спасибо, но Вы мои способности явно переоцениваете ;-) Я даже во временной области с большим трудом могу ФШ из "примитивов" собрать. А уж в частотной...
> СПМ белого шума - константа, которую как правило обозначают N0, [Вт/Гц]. Это не мощность, это плотность мощности. Она конечна для любых реальных шумовых процессов;
Разумеется. Расходимость возникает в одной точке (на нулевом периоде). Однако, это лишает нас права написать неопределенный интеграл. И, видимо, как-то мешает перейти к общим формулам.
Точнее, в случае с БШ это как-то уже преодолено, а вот в случае с ФШ - поему-то нет. Я сам не слишком хорошо в этом разбираюсь. но по факту есть масса литературы, вышедшей в нормальных журналах, где авторы берут ФШ и путем элементарных и очевидных преобразований выписывают связь между его степенным спектральным параметром <бета>, фрактальной "размерностью" такого сигнала D и его показателем Херста H. Причем написано все настолько просто и очевидно, что только у дурака могут возникнуть сомнения в этих формулах. И авторы вроде бы неплохие - от Туркотта до Фосса и Федера. Беда только в том, что формулы (связывающие три эти величины) у разных авторов получаются разными. А главное, дают странные ответы в граничных случаях. Например, большинство авторов считает, что 2D+<бета>=5, а другая половина - что 2D+<бета>=4. Но, первая формула дает странный ответ для белого шума (если <бета>=0, то D=2.5, и это на плоскости!), а вторая дает аналогичный глюк для броуновского шума (у него <бета>=2, но тогда D=1.0, хотя на самом деле там D=1.5). Ссылки на публикации упомянутых авторов с этими формулами можно найти вот тут.
Да, эти работы достаточно древние, но с тех пор никто так и не удосужился уточнить: а как же на самом деле? Вот я и подозреваю, что общие формула не выводятся из-за расходимости с неопределенными интегралами. Если же брать конечные реализации, особенно модельные, то с ними и
у меня все более-менее норм
Связь-между-бета-D-H.png. Н посчитан в классическом определении Херста, без взятия приращений. По оси абсцисс отложен параметр Фосса Hf
Глядя на этакие картинки, я даже могу предположить, какие формулы к этому численному моделированию лучше подходят. Только вот теоретически сам их вывести не могу. И, соответственно, не могу обосновать асимптотику подавления ФШ накоплением...
> определяется качеством приема: приемником, антенной, каналом (например, есть или нет радиозасветки Солнца и др. космических объектов).
Вы уверены, что шум во всех этих случаях именно белый? Я вот в этом весьма сомневаюсь. Так как в случае БШ фон спектра должен становиться плоским, начиная с какого-то уровня, где сигнал исчезает, и дальше (на более высоких частотах) доминирует шум. Но при обработке реальных рядов и почти никогда не встречал подобные спектры. В моих данных они билогарифмически-линейно спадают с ростом частоты вниз вплоть до найквиста. Но тогда кто дал нам право экстраполировать выполаживание спектра левее доступного изучению диапазона частот (что эквивалентно допущению о "белости" шума)? По Оккаму, гораздо логичнее просто продолжить эту тенденцию в бесконечность. Да и здравый смысл намекает, что это правдоподобнее. Ведь дискретизация измеряемого сигнала - это наше над ним надругательство, а в действительности-то аналоговый сигнал всегда непрерывный. Поэтому гораздо логичнее взять в качестве "базовой модели" исходного (а не измеренного!) сигнала именно ФШ, у которого нет бесконечной мощности при интегрировании вплоть до нулевого периода.
Но, рассуждая аналогично, на другом (НЧ) конце спектра мы тогда тоже должны допустить аналогичную экстраполяцию "без новых сущностей". И тогда уже она приведет к бесконечной мощности на нулоевой частоте. практически всегда вижу спадающую кривую на билогарифмитческом графике. рядов
> Заметьте, тут про дискретизацию вообще нет речи, и она по сути не требуется. Это уже нюансы цифровой обработки сигналов и их лучше опустить.
Именно так - это наш способ работы с данными. Но когда мы хотим вывести теоретическую формулу, мы же работаем с абстракцией. И для БШ (который теоретически имеет бесконечную мощность, если не ограничивать диапазон частот) все эти формулы почему-то выписываются без проблем. Проблема "нулевого периода" никому не мешает. А вот в варианте с ФШ (где по сути все то же самое, только проблема на нулевой частоте вместо нулевого периода) формулы почему-то не пишутся. Я так и не могу понять - почему.
Вы меня правильно поймите: я сам не смогу вывести нужные формулы ни в одном случае, ни в другом. Но:
(1) я запросто использую те формулы, которые написаны для БШ. Они в любом учебнике есть, причем на все случаи жизни; они прекрасно работают, и никогда (если шум действительно белый) не вступают ни в какое в противоречие ни с здравым смыслом, ни с численными моделями.
(2) С другой стороны, я легко могу показать, что при замене БШ на ФШ все эти формулы работать перестают. И это нельзя исправить никакими "маленькими поправками". Там просто катастрофические расхождения возникают. В варианте ФШ формулы для БШ больше не работают ни в каком приближении.
(3) Ну и с третей стороны, подавляющее большинство временных рядов долговременного мониторинга - это либо строго ФШ, либо почти ФШ. Тут просто нет ни малейших сомнений - достаточно на спектр посмотреть.
А теперь вопрос: почему, несмотря на (2) и (3), у нас нигде нет разумных формул для варианта с ФШ? См., например, мой исходный вопрос про подавление ФШ накоплением. Ну ведь наболело же! Я рецензирую кучу статей в журналах, где авторы на полном серьезе применяют в подобных случаях формулы для БШ. Хотя бред очевидный. И в каждом конкретном случае его можно продемонстрировать элементарно. Вот ваши яблоки, берем из них два, складываем с другими двумя. Теперь видите, что в ответе НЕ 5?
А общей формулы нет!
Чтобы не разбирать в стопятсотый раз в точности одну и ту же ошибку, складывая чемоданы, груши и финики.
Вдогонку: кажется, я сообразил, в чем преимущество Vim! Отвечу сам же себе, т.к. время редактирования прошлого комментария истекает:
> Несмотря на все это, попытка нового знакомства с Vim в моем случае окончилась полным крахом. Прежде всего, "не зашла" концепция двух режимов работы. Зачем, если есть экран, где все видно, и работать "стрелочками" (плюс модификаторы) много проще?
Проще - это же только мне на десктопе!!! Где у меня под рукой два комплекта стрелочек на основной и правой клавиатуре, плюс всякие контролы-шифты и справа, и слева, не говоря уже про всякий синтаксический рукопальцевый сахар в виде кучи Fn и т.д. На ноуте такую роскошь еще поищи... Но если там для типичных команд надо сделать три последовательных нажатия вместо одного комбинированного, тогда ой! Тогда я бы и сам, вероятно предпочел двухрежимный редактор, только чтоб так не мучиться. Даже интересно: я угадал или мимо? Можно ли оценить, какой процент завсегдатаев VIM-а работает преимущественно на десктопе? Ну или точнее, сравнить относительную долю VIM-щиков среди тех. кто программирует: а) преимущественно на ноуте б) преимущественно на дестктопе?
Будет ли в этих группах статистически значимое различие?
@cupraer> Я перешел на vim после мучений с VisualStudio, Idea, Atom, VSCode (в этой последовательности) — примерно в 2017
Я тоже решил познакомиться с Vim примерно в 2017г. До этого (еще в DOS-эпоху) пользовался Omni и Multi-Edit-ом, а позже VisualStudio и Notepade++ (конечно, много других редакторов тоже, но эти были основой). Но поскольку моя сознательная жизнь (еще перед DOS) началась с PDP-11 (=СМ-4), где, вроде бы, стояло что-то из vi-семейства, то решил, так сказать, попробовать
вернуться к истокам
Хотя уже ничего про эти "истоки" не помню. Вроде, сперва на СМ-4 у нас стоял какой-то строчный редактор, но уже при мне он как-то научился имитировать многострочность. Эх, давно это было (где-то 1986г).
Так вот. Несмотря на все это, попытка нового знакомства с Vim в моем случае окончилась полным крахом. Прежде всего, "не зашла" концепция двух режимов работы. Зачем, если есть экран, где все видно, и работать "стрелочками" (плюс модификаторы) много проще?
Нет, я совсем не считаю, что Vim - отстой. Наоборот, я сразу же я оценил наиболее убойную (на взгляд чайника) фичу: для меня это
кратность команд
Только вот в реальной жизни она мне бывает нужна нечасто. Если требуется 2-3-кратный повтор, то мне проще нажать команду два раза, чем искать цифру "3". А если не пару раз, а 15, то это же надо еще сперва посчитать, сколько именно. А мне лень... И лишь в некоторых специфических (но вполне регулярных) случаях мне бывает нужен 5-ти, 7-и т.д.-кратный повтор отдельных команд, чередуя их с разными другими командами. Специально для таких случаев я наплодил себе макросов в Notepade++, благо общий набор таких ситуаций и шаблонов действий у меня ограничен.
А еще у меня не возникло проблемы с выходом
которой тут всех пугают ;-)
т.к. я заранее, еще перед входом в Vim, разузнал о противоядии ;-)
Тем не менее, после пары дней тренировок у меня не возникло чувство, что с уверенным освоением Vim я существенно в чем-то выиграю. Возможно, проблема в том, что меня не особо напрягают ограничения уже освоенных редакторов?
Но вопрос я хотел задать не об этом.
Моим первым "рабочим" редактором в DOS был так называемый Omni. Полноэкранный! И тоже, кстати,
с нетривиальным выходом из него ;-))
Там стояла "защита от дурака": чтобы выйти без сохранения, надо было в специальном окошке ввести имя файла ;-) Ну или символ "*", если имя файлу еще не присвоено. Что как бы намекает на уровень компьютерной грамотности предполагаемых пользователей...
Кстати, он у меня до сих пор
запускается под DosBox-ом
,
А вопрос вот такой. Если тут еще кто-то помнит про Omni (не важно, хорошее или плохое), сможете рассказать про историю его зарождения/смерти? И в каких отношениях он находился с vi-семейством? Я, к сожалению, не умею в антимонгольский, а русскоязычным поиском ничего особенно не находится. Буду благодарен за ссылки по теме,
включая англоязычные
так как прочитать рекомендованную страницу при наличии переводчика - не проблема. А вот искать на незнакомом языке, особенно когда не умеешь, проблематично
Во-первых, статистику будем брать от целевого распределения.
А во-вторых, Вы зря думаете, что статистика фамилий радикально отличается для разных социальных групп и профессий. В частности, в обоих упомянутых группах будет гораздо больше фамилий на К или С, чем на Ю или Щ. Думаю, что более точные данные легко можно найти при необходимости.
На мой непросвещенный взгляд (из самых общих соображений), гораздо более сильные различия в частотности фамилий - не профессиональные, а национальные (и, вследствие этого, региональные). Поэтому если мы хотим написать на базе сабжевого принципа более-менее универсальный алгоритм (который будет пригоден для принципиально разных наборов фамилий), то функция коррекции распределения должна вводиться отдельно как настраиваемый параметр алгоритма. Попросту говоря, она должна вычисляться с учетом частотного распределения фамилий в целевой группе.
Таким образом, получается настраиваемый алгоритм: мы один раз анализируем фактическое распределение сортируемых объектов (и это не обязательно фамилии, хотя именно для фамилий выигрыш должен быть очень хорошим), потом строим к нему обратную частотную функцию (приближающую распределение к равномерному), ну а потом можно очень быстро сортировать поступающие списки.
Еще можно время от времени проводить реанализ распределения с учетом обновляющихся данных, и уточнять обратную частотную функцию.
Второй вариант:
Если. к примеру, к нам могут поочередно поступать списки то из Китая, то из Египта, то из Исландии, то тогда заготовим несколько таких корректирующих функций (для каждого региона), а потом применяем соответствующую функцию в зависимости
от источника данных
Если регион заранее неизвестен, но их ограниченное количество, и известно, что смешанных списков почти не бывает, то можно сперва надергать немного (=n-малое) случайных фамилий из поступившего списка, и по ним с хорошей точностью определить регион за O(n-малое)
Короче говоря: вопрос про статистику поставлен правильно, но решается он гораздо проще, чем может показаться на первый взгляд. Если, конечно, нам действительно критична скорость сортировки, и мы готовы заплатить за это усложнением алгоритмов. И, главное, если задача попадает в тот довольно узкий список задач, для которых вся эта оптимизация: а) эффективна и б) выигрыш стоит того, чтобы этим всем заморочиться
>> Для unsigned long long int (64 bit) - ексабайт. > Нет, конечно. Буфер выбирается из тех ресурсов, которые вы можете позволить.
Я что-то туплю: а за что заминусовали ответ про буфер? Вроде бы, там все верно: если у Вас 64-битный ключ, то сперва можно отсортировать по первым 16 (либо 8) битам (т.е. потребуется 65536 либо 256 ящиков=уровней). Потом внутри каждого такого "ящика" - по следующим 16/8 битам. И так далее.
Другой вопрос, что в пределе это и будет та же самая N * logN -сортировка. Ну так никто и не обещал, что предложенный алгоритм годится на все случаи жизни. Это специфическая (но иногда очень выгодная!) оптимизация для специфических случаев.
Например, если у вас 64-битный ключ, но данные по этой шкале раскиданы очень редко (подавляющая часть ключей не используется), то уже после сортировки по первым 16 битам в каждом ящике может оказаться так мало записей, что они за ничтожное время отсортируются другим алгоритмом.
А у меня в реальной жизни (геофизические временные ряды) часто встречаются 64-битные данные (на самом деле обычно 32-битгные, но сейчас это не принципиально), но подавляющая часть из этих значений лежит в середине диапазона, и только малая часть - на краях (= выбросы). А я их хочу упаковать в 16 бит без чрезмерной потери точности (выбросы надо сохранить!). Я для этого делаю log-преобразование, которое приближает распределение к равномерному, после чего трюк с равномерными уровнями прекрасно работает.
> Фамилии людей распределены весьма не равномерно.
Если мы заранее знаем, что это будут фамилии, то можно учесть неравномерность распределения, разбив алфавит на
неравные интервалы верхнего уровня
т.е. корректируем "алфавит" так, чтобы распределение фамилий по новым "буквам" стало равномерным. А на этапе распихивания фамилий по "ящикам" (когда нам нужно, чтобы "номер ящика" вычислялся в одно действие) применяем обратную функцию перехода от реального алфавита к вымышленному (на котором распределение равномерное). Для ускорения процедуры эта корректирующая функция может быть максимально простой, т.к. строгая равномерность интервалов не нужна.
P.S. Спасибо автору, что напомнил про этот алгоритм! Я его применял в глубокой древности, генерируя однобайтовые ключи для сравниваемых объектов, и потом распихивая их по 256 значениям ключей. Но сейчас при столкновении с подобной задачкой - уже не факт, что вспомнил бы про такой алгоритм. Теперь не забуду ;-)
Про ветер пока что слишком дешевый развод ;-). На таком уровне я и сам могу вместо нейросети поиграть ;-))
Лучше попросите нейросеть объяснить то же самое условному "пожизненному" моряку (т.е. никогда не сходившему на берег) или жителю пустыни, где деревьев нет в принципе. А еще уточните, что этот модельный моряк или житель южной/полярной пустыни вообще никогда деревьев не видел, и просто не знает, что это такое. Вот когда она: 1) сначала объяснит ему про деревья - что это за такая приблуда, и как они устроены, и почему у них иногда стволы/ветки качаются (причем все это всерьез!), а потом 2) чуть ниже в том же самом ответе снова напишет про ветер и ветки (но уже согласно игре!!), то читать станет значительно интереснее ;-))
Как Вы думаете, есть шанс, что получится?
Если да, то было бы очень интересно, чтобы этот текст потом специалист по шизофрении прокомментировал ;-))))
> Пример 3: Поиск максимального элемента в массиве
Простите великодушно, но этот пример я тоже не понял. В чем выигрыш от разбиения массива на части -то? Я вижу только накладные расходы.
Или такой код лучше распараллеливается в некоторых языках? Но тогда хотя бы намекните, в каких. В фортране например, так писать совершенно точно не надо.
.
UPD: И, соответственно, я не могу врубиться в рекомендацию:
> Метод "разделяй и властвуй" используется для задач (...) нахождение минимального/максимального элемента в массиве.
Можете пояснить, что имеется в виду?
Или это рекомендация для языков, где массивы реализованы каким-то экзотическим способом? Но такие языки, вероятно, изначально не преследуют цели быть эффективными при работе с такой структурой. И, соответственно, для решения таких задач лучше взять язык попроще, где самый тупой подход гарантирует О(n), и для этого не надо изобретать какие-то ухищрения...
Простите за глупый вопрос. Я только с очень специфическими алгоритмами сталкивался, а от списков, графов и пр. крайне далек. Да и язык для меня непонятный (я его читаю, как псевдокод). Но:
> Пример: Найти цикл в связном списке
разве приведенный код не дойдет до конца вот такого списка:
1(4), 2(3), 3(2), 4(none)
Тут есть цикл 2-3, но последовательное применение (next) ведет к none. Так же ведь нельзя найти никакой цикл, недостижимый от head-а?
Или слово "связный" в условии означает что в списке нет недостижимых от head-а элементов?
> А может быть у вас полезный сигнал - гармонический неизвестной амплитуды, частоты и фазы?
Да, такие сигналы есть ;-) Например, приливные волны. Но для них все давным-давно построено и посчитано. Частота известна априори, причем абсолютно точно. Амплитуда и фаза - оцениваются, причем борьба идет за пятый-шестой знак в зависимости от качества данных. Основная сложность там даже не в шуме, а в том, что этих волн много, и они не ортогональны. Поэтому процедура оценивания опирается на некоторые трюки. Но в целом эта задача уже решена.
> Тогда задачу можно решить, правда при условии, что корреляционную матрицу остаточной компоненты (фликкер шума) Вам удастся как-то правдоподобно оценить.
Для приливных волн все немного проще: мы там точно знаем частоты, поэтому начинается все с узкополосной фильтрации, после чего наиболее неприятная НЧ-составляющая шума уходит, и все значительно упрощается.
> В этом случае можно поставить банк параллельных фильтров для заданной сетки частот (...)
;-)
Сейчас главная проблема с другими сигналами, которые описанной выше модели не соответствуют. И про которые мы мало что знаем. Поэтому работа с ними строится в "инвертированной" логике: вместо нормальной фильтрации мы хотим сперва подавить шум (про который заранее предположили, что это ФШ), а потом посмотреть - а что там останется?
И уже на основании впечатлений от этого "остатка"абсолютно неформальным образом строить гипотезы про сигнал.
В теории, фликкер-шумом называют целое семейство процессов со степенным параметром от 0.5 до 2. Получается, что интеграл в любом случае разойдется... Не в нуле, так на бесконечности. Хотя, глядя на БШ, чего же тут удивительного. Он же тоже при бесконечной ширине полосы дает
бесконечную мощность...
Даже интересно стало - почему в варианте с БШ теория не замечает вообще никаких проблем? Т.е. для сигналов с наложенным белым шумом абсолютно любые фильтры запросто строятся и работают? Для дискретного сигнала - понятно, там найквист и бесконечностей нет. А для аналогового (если его теоретически рассмотреть) почему бесконечности исчезают? Или там тоже полосу частот при расчетах ограничивают каким-то способом? Подскажете книжку "для чайников", где это разжевано?
> Для ограниченных по времени фрагментов их надо центрировать по фактическому среднему значению.
Это само собой.. но с точки зрения поставленного вопроса о глубине подавления ФШ при накоплении (=избыточности кодирования) такое центрирование ни на что не влияет. Увы.
> И перед накоплением выравнивать по сезонам, то есть синхронизировать по периодам. И, фактически, если вы взяли, например, за один месяц, то будут месячные оценки: модель сигнала периодическая с основным периодом T = 1 месяц.
Тут я не очень понял мысль. Допустим, я считаю месячную периодичность (я ее реально считаю, только годовую). Я беру данные за 100 месяцев и накладываю эпохи (=суммирую), потом делю на 100. Т.е. что-то вроде синхронного детектирования.
Если у меня в сигнале имеется строго периодическая составляющая с периодом 1 мес, то после такой процедуры она никак не изменится (амплитуда "сигнала" после суммирования 100 периодов и деления на 100 = амплитуде исходной периодичности).
А вот с шумом сложнее. Если он некоррелированный, и удовлетворяет условиям ЦПТ, то он должен подавиться (по амплитуде) в корень из N = 100 раз. Дисперсия, соответственно, в 100 раз. А во сколько раз подавится дисперсия ФШ? Чую, что ответ (формула) должен быть совсем простой и вытекать из корреляционных свойств этого самого ФШ. Но вот как именно? АКФ-то у него бесконечная...
Кстати, о предварительном центрировании фрагментов
Тут есть такой нюанс, что если нас интересует только амплитуда/дисперсия шума, то центрирование фрагментов вообще пофиг. Так как после наложения (суммирования) эпох оно (или его отсутствие) выразится в добавлении некой константы к накопленному среднему сигналу.
> Тогда статистики будут конечные.
По идее, реальные сигналы всегда имеют конечную амплитуду и длительность. Проблемы начинаются, когда мы хотим построить для них теоретическую модель. И вот тогда появляется странность: на конечных интервалах времени ограниченные по амплитуде сигналы лучше всего аппроксимируются теоретическим моделями, в которых из каждого угла выглядывают расходимости.
Кстати, очень похожую фичу обнаружил М.Родкин с колегами: ущерб от стихийных бедствий (реальные данные!) лучше всего описывается распределениями с бесконечной дисперсией. Там, между прочим,
целая куча нетривиальных следствий из этого вытекает
Например, несмотря на стационарность процесса, средний ущерб в расчете на одно событие растет по мере увеличения длины ряда. Любой нормальный человек, который в данных этот рост обнаружит, сразу же заподозрит нестационарность процесса,
правда?
А уж с какой безмерной радостью бросаются на этот результат алармисты! "Природа пошла в разнос" и т.д..
Однако же на самом деле для распределений с такими свойствами из описанного (доказанного!) факта, что средний ущерб растет, процесса совершенно не следует. вывод о нестационарности.
Как, впрочем, не следует и обратное (что вывод о нестационарности некорректный ;-)
Но... это мы далеко от темы ушли. Если интересно, можно в отдельной ветке обсудить поподробнее. И ссылок при желании накидаю.
> У Б. Скляра кажется есть такие модели: энергетический сигнал (непериодическая модель, одиночный импульс) и мощностной сигнал (конечный период T, либо бесконечный случайный процесс).
Книжку скачал, буду курить. Только надо нормальную
djvu-читалку поставить
у меня такой формат в экзотике до сих пор - мы, научники, как-то все больше на PDF нажимаем...
> Сдается мне, что длинные хвосты АКФ - влияние полезного сигнала.
Хорошая попытка "хакнуть" Природу, но нет. ФШ по определению дает именно такие хвосты. Если простыми словами, у ФШ-процессов бесконечная память. То есть, автокорреляция не равна нулю на сколь угодно больших лагах.
А насчет полезного сигнала еще веселее. Мы даже этого (какая ПРИМЕРНО у него АКФ) не знаем. Не исключено, что у него то же самое. По крайней мере на доступных для измерения временах...
> Вам надо как-то измерить чистый шум полноценно работающей аппаратуры, когда полезного сигнала нет априори (либо датчики экранированы или как там у вас).
Идея понятная и логичная, у нас даже об этом (про приборные эффекты и соответствие результата измерений фактическим процессам в геосреде) только что была
дискуссия на два номера журнала
Вот эти номера (N3 и N4 за 2024г), там можно скачать постатейно. Ну или можно взять макеты номеров в целом вот тут
Но это не меняет картину принципиально. Так как ФШ идет не от приборных шумов и других подобных эффектов, а непосредственно из изучаемого объекта (планета Земля).
> В Вики для фликкер-шума ничего про нестационарность нет.
Ну так там много чего нет ;-)
Но по определению, ФШ это процесс со степенным спектром при показателе степени от 0.5 до 2.0. Отсюда следует, что в нуле он ВСЕГДА расходится (мощность уходит в бесконечность). Поэтому нестационарность по среднему в любом ФШ будет на абсолютно любом масштабе времени. Можно сказать, что для ФШ-процесса X(t) матожидание E(X(t)) /= E((X(t+dt)) при любом сколь угодно малом dt .
А вот насколько сильно они не равны (точнее, асимптотика по dt), зависит уже от степенного параметра спектра ФШ.
Но на самом деле все еще гораздо хуже. Логическое противоречие начинается уже на этапе определения. Ведь понятие спектра мы изначально вводим для стационарных (периодических) процессов. А потом через него (sic!) определяем ФШ. Который по определению нестационарен. Не удивительно, что в Вики этого нету ;-)
Впрочем, для реализаций конечной длины (которые "не дотягиваются" до нулевой частоты) все это прекрасно работает. Могу показать идеально прямолинейные (в билогарифмических координатах, конечно) спектры реальных (измеренных экспериментально) процессов. Которые твердо лежат на этой прямой на протяжении 4-5 порядков масштаба. ВЧ граница проходит по Найквисту, НЧ - по длине ряда.
И что прикажете с ними делать?
> Со стороны области времени надо всё-таки оценивать АКФ до момента, когда она начнет существенно падать по уровню.
Ну вот увы. По мере стремления частоты к нулю амплитуда спектра у нас уходит на бесконечность. И это не просто заумная абстракция (ведь бесконечной мощности не бывает!), а определение. А самое ужасное в том, что целая куча экспериментальных сигналов (в геофизике - так вообще практически все) в точности ложится на эту модель. Хотя мы точно знаем, что
бесконечных амплитуд не бывает
Даже просто очень больших не бывает (физически невозможно). Но - за время наблюдений (100 лет) мы до таких амплитуд (где ФШ закон нарушается) мы пока еще нигде не дошли. Кстати, есть надежда, что уже скоро (надо еще лет 100) к ним по крайней мере приблизимся. Очень интересно, как тогда тогда поведут себя наши сигналы...
> Чтобы создать алгоритм (метод), надо четко оформить мат. модель сигнала и шума, сделать постановку задачи. Я пока что не понял чем полезный сигнал отличается от шума. Формой? Полосой частот? АКФ? Средним значением?
Отличный вопрос! И ответы под стать вопросу: нет, нет, нет и нет! Прекрасная стартовая позиция для создания оптимального фильтра ;-)))
Для начала я бы сформулировал более простую задачку: у нас есть случайные сигналы и известным спектром. Он степенной. Больше про эти сигналы ничего не известно.
Можем ли мы что-то сказать про разные статистики (функции) этих сигналов?
В общем случае - я подозреваю, что нет. Так как есть расходимость спектра в нуле и все вытекающие из этого бесконечности.
Ну а если у нас есть лишь ограниченные по времени фрагменты реализаций таких процессов?
В контексте статьи это наверное даже смешно ;-) Но мир настолько разнообразен, что даже в такой ситуации обработка рядов порой приносит ощутимую пользу с точки зрения научного знания... Попросту говоря, "искали то не знаю что", а там и правда что-то интересное обнаружилось ;-)
> У меня получилось найти АКФ для фликкер-шума, но для ограниченного параметра "альфа". Спасибо справочнику по интегралам Градштейн, Рыжик.
Спасибо!!! А можете еще подсказать,
как я могу на это Ваше сообщение сослаться, если понадобится?
Я пока не знаю, как я смогу эту формулу использовать, но если смогу, то я бы хотел в дополнение к
ссылке на
Градштейн И.С., Рыжик И. М. Таблицы интегралов, сумм, рядов и произведений / Перераб. при участии Ю. В. Геронимуса и М. Ю. Цейтлина. — 5-е изд., стер. — М.: Наука, 1971. — 1108с.
добавить ссылку на "личное сообщение" (в журналах их обычно оформляют в виде подстраничных сносок). Но, в такой ссылке надо указать ФИО автора сообщения. Если Вы не против,
напишите мне данные в ЛС?
В научной публикации такая ссылка будет выглядеть примерно вот так (реальный пример:)
Глухов В.Е. [https://www.elibrary.ru/author_items.asp?authorid=1072618], личное сообщение
> Только что это даст?
Это интересный вопрос, так как мне на самом деле нужны значения <альфа> от 1.5 до 2.0. Но и соседний случай полезен для сравнения!
Единственное, я с хода не смог разобраться: какая там будет асимптотика по тау, когда <альфа> снизу приближается к 1?
(....)
> (..) Поэтому для БШ формулы очень простые.
Да, видимо это и есть ключевое отличие между БШ и ФШ.
> Надо различать ось времени и ось амплитуд. То, что называют оптимальным приемом (корреляционный прием, согласованный фильтр) не является накоплением при обработке рядов. Это разные вещи.
А вот тут не понял.
Мы при зондировании земной коры пытались просвечивать очаг землетрясения электрическим током. Сперва была идея, что для повышения отношения сигнал/шум надо увеличить мощность источника тока. Для этого на Памир затащили МГД-генератор. Он давал ток в сотни ампер. Но, каждый пуск был праздником. Он требовал большой подготовки и происходил в лучшем случае раз в две недели. А последняя стадия подготовки землетрясения - это часы-сутки (как тогда думали).Т.е. сопротивление очаговой зоны надо измерять ежедневно, хотя бы.
И вот как раз мой многолетний шеф А.Я.Сидорин, насчитавшись книг по радиофизике, предложил вместо однократного жутко сильного импульса послать в породу гораздо более слабый (и поэтому легко генерируемый), но очень длинный знакопеременный сигнал из прямоугольных импульсов длительностью пару секунд каждый, но суммарно длиной в полчаса. А на приемной станции выполнялось измерение напряжения на положительной и отрицательной фазе питающего импульса. И высчитывалась разница между ними. И эта разница суммировалась по паре тысяч импульсов (получасовой цикл). Заодно такая схема решала проблему с поляризацией среды, переходными процессами (ток на выходе МГД-генератора меняется по очень хитрым законам, и такой сигнал не так просто пересчитать в напряжение на приемнике из-за индуктивности), и пр.
В общем, при многократном понижении стоимости и снижении силы тока в 100 раз мы улучшили отношение сигнал/шум на два порядка за счет накопления. Подробности раскиданы по разным работам, но если интересно, можно для начала вот тут посмотреть (текст выложен).
Так вот.
Разве эту схему измерений нельзя называть синхронным детектированием? Мы всегда думали, что можно. И что накопление и синхронное детектирование - это очень близкородственные понятия (хотя и разные, разумеется). Но в нашем случае описанная схема зондирования в каком-то смысле обобщает первое и второе в единый процесс (алгоритм).
Или это только у нас такая специфика?
Прошу прощения, но
буду отвечать по частям
Очень длинный коммент мне технически сложно запостить (спасибо, редактор Хабра!)
> При накоплении ведь складываются отсчеты, разнесенные достаточно длинным интервалом времени (...) Если так, то [1] шумовые значения некоррелированы (читай белый шум). Если при этом эти отсчеты [2] имеют нормальную плотность вероятностей, то они и независимы [цифры мои]
К сожалению, оба предположения не выполняются.
[1]. В моем случае корреляция с ростом лага уменьшается, но очень медленно. На самом деле эта скорость определяется значением степенного параметра спектра <альфа>. Пока он маленький (порядка 0.5), все более-менее норм. Корреляция и правда уменьшается настолько быстро, что это даже можно в расчетах использовать. Обосновать не могу, но численное моделирование подтверждает. Например, для метеопараметров такое приближение (в виде поправки к формулам для БШ) отлично работает.
Но вот в моем случае параметр <альфа> обычно
близок к 2.0
Если интересно, вот тут или вот тут есть таблички степенных параметров для сигналов из нашей вотчины. Почти всегда там что-то
от 1.7 до 2.0.
Только если правда туда в эти таблички полезете, то учитывайте, что мы там в считали не степенной параметр спектра мощности <альфа>, а степенной параметр амплитудного спектра к=<альфа>/2. Так как мне хотелось читать спектр в тех же размерных физических единицах, что и исходный сигнал (а не в квадратичных)
Это совершенно типично для большинства рядов в твердой Земле, магнитосфере и пр. Турбулентность тоже, кстати, дает 5/3 (спектр Колмогорова). Но, когда значение <альфа> близко к 2.0, корреляция остается неприемлемо высокой для любых разумных лагов.
Увы.
Я пытаюсь с этим бороться с помощью разных трюков. Например, отрезаю НЧ, оставляю только узкую полосу, потом пытаюсь работать в этой узкой полосе. Благо, после такой процедуры (выделение узкополосного сигнала) дальние корреляции действительно хорошо давятся
Но, с точки зрения здравого математического смыла отписанный трюк больше похож на какое-то надругательство над сигналом. Ведь в ФШ-сигнале нет никаких выделенных частотных полос! Когда я такие полосы искусственно вырезаю - то это же полный произвол! Так как никаких разумных аргументов для выбора этих частотных полос исходный сигнал не содержит.
Я, конечно, пытаюсь отталкиваться от физики изучаемых явлений (в физике-то частоты не равноправны)... но с точки зрения матаппарата это же просто кривая подпорка к неработающему легаси...
Но всем пофиг...
Я в прошлом году пару статей на основе этой идеи написал. Думал, отдам в журнал, там рецензенты прочтут и в ужас придут. А потом, глядишь, и что-нибудь посоветуют.
Однако же замечания и советы были о чем угодно, но только не про этот больной (для меня) вопрос. Обе статьи (в разных журналах!) уже напечатаны. Я уже не знаю, к кому теперь обращаться... Физики меня прокатили, а к математикам лезть - это дословно получится со свиным рылом в калашный ряд (с)
Ну и по пп.[2] все еще проще. Чем ближе степенной параметр [альфа] к 2.0, тем больше распределение
уходит от Гаусса в сторону равномерного
Вот для примера распределения для ФШ рядов с <альфа> = 1 и 2
Интуитивно это можно понять: чем больше <альфа>, тем сильнее персистентность, тем активнее самоподдерживается тенденция к росту или спаду. В результате сигнал начинает "гулять" от минимума до максимума. В пределе (при <альфа> порядка 4) это уже начинает напоминать линейный тренд, у которого, как известно, распределение равномерное. Ну а в нашем случае (когда <альфа> 1.5..2.0) - что-то промежуточное
Вдогонку:
Ой!
Прошу прощения за опечатки и глюки в комменте :-(( Время редактирования истекло, не успел сохранить исправленный вариант :-(((
> СПМ фликкер-шума, допустим, степенная функция
Она конечная всюду, кроме полюса f = 0.
Именно так!
> Этот полюс - наш выбор.
А вот тут уже не совсем. Это при работе с искусственными сигналами можно выбрать подходящую полосу частот, приладить туда источник-приемник, и не париться обо всем, что правее-левее. С одной стороны защищаемся найквистом, с другой - ФНЧ, и поехали проходить через квест, имея уровень "бог".
При экспериментальном мониторинге мы чем дольше наблюдаем, тем больше знаем. А проблема ФШ в том, что на любом масштабе времени (при любой длине ряда) наибольшую амплитуду (мощность) имеют периоды, сопоставимые с этой длиной ряда. Поэтому ограничивать спектр со стороны минимальных частот (=максимальных периодов) неверно как философски, так и технически. Философски мы теряем главную ценность данных - продолжительность непрерывно наблюдаемого процесса, а технически - теряем наибольшую часть измеренного сигнала в плане его дисперсии (мощности).
Так что это не выбор. Это данность, с которой приходится жить...
> Мы можем регуляризовать модель, добавив туда малую константу
Я совсем плохой теоретик, поэтому мне непонятно: как добавление этой константы поможет упростить формулы/выкладки. Навскидку - я совсем не уверен, что упростит. Но в любом случае, за идею спасибо. Если когда-нибудь я смогу найти математика, который заинтересуется моими вопросами, то я ему обязательно эту переписку покажу. Возможно, он оценит и использует Вашу идею.
> В реальности имеется проблема оценить эту константу
Ну, для теоретических выкладок можно наверно просто приравнять ее неизвестному малому значению <дельта>.
;-)))
Что же касается практических случаев, то там будет за счастье даже не точные формулы, а хотя бы асимптотика. Возможно, там получится какой-то другой параметр прикрутить, который будет легко оцениваться и даст нужные поправки к решению.
> (и, вообще, подобрать корректную модель такого "плохого" шума).
Тут вопрос в том, что нам надо от эксперимента идти. Мы знаем, что СПМ реальных сигналов ведет себя определенным образом. Больше того, даже знаем некоторые модели процессов (их много!), которые к такой СПМ приводят. Только вот плясать конкретно от этих моделей нельзя, так как их целая куча, и следствия из них разные. Например, модель с независимыми случайными приращениями - это совершенно не то же самое, что модель с перемежаемостью по Тимашеву... Поэтому в идеале надо бы исходить из эмпирик-факта, и только лишь из него...
> И проблема найти интеграл аналитически для любого параметра "альфа".
Тут ничего не могу сказать: я не математик. Но вообще, сидя на берегу реки (с), кажется странным, что такая простая на вид задачка может представлять реальную трудность. Возможно, она просто была особо никому не нужна?
> Согласитесь, интегрировать константу N0 проще, чем витиеватую СПМ фликкер-шума?
Спасибо, но Вы мои способности явно переоцениваете ;-) Я даже во временной области с большим трудом могу ФШ из "примитивов" собрать. А уж в частотной...
> СПМ белого шума - константа, которую как правило обозначают N0, [Вт/Гц]. Это не мощность, это плотность мощности. Она конечна для любых реальных шумовых процессов;
Разумеется. Расходимость возникает в одной точке (на нулевом периоде). Однако, это лишает нас права написать неопределенный интеграл. И, видимо, как-то мешает перейти к общим формулам.
Точнее, в случае с БШ это как-то уже преодолено, а вот в случае с ФШ - поему-то нет. Я сам не слишком хорошо в этом разбираюсь. но по факту есть масса литературы, вышедшей в нормальных журналах, где авторы берут ФШ и путем элементарных и очевидных преобразований выписывают связь между его степенным спектральным параметром <бета>, фрактальной "размерностью" такого сигнала D и его показателем Херста H. Причем написано все настолько просто и очевидно, что только у дурака могут возникнуть сомнения в этих формулах. И авторы вроде бы неплохие - от Туркотта до Фосса и Федера. Беда только в том, что формулы (связывающие три эти величины) у разных авторов получаются разными. А главное, дают странные ответы в граничных случаях. Например, большинство авторов считает, что 2D+<бета>=5, а другая половина - что 2D+<бета>=4. Но, первая формула дает странный ответ для белого шума (если <бета>=0, то D=2.5, и это на плоскости!), а вторая дает аналогичный глюк для броуновского шума (у него <бета>=2, но тогда D=1.0, хотя на самом деле там D=1.5). Ссылки на публикации упомянутых авторов с этими формулами можно найти вот тут.
Да, эти работы достаточно древние, но с тех пор никто так и не удосужился уточнить: а как же на самом деле? Вот я и подозреваю, что общие формула не выводятся из-за расходимости с неопределенными интегралами. Если же брать конечные реализации, особенно модельные, то с ними и
у меня все более-менее норм
Глядя на этакие картинки, я даже могу предположить, какие формулы к этому численному моделированию лучше подходят. Только вот теоретически сам их вывести не могу. И, соответственно, не могу обосновать асимптотику подавления ФШ накоплением...
> определяется качеством приема: приемником, антенной, каналом (например, есть или нет радиозасветки Солнца и др. космических объектов).
Вы уверены, что шум во всех этих случаях именно белый? Я вот в этом весьма сомневаюсь. Так как в случае БШ фон спектра должен становиться плоским, начиная с какого-то уровня, где сигнал исчезает, и дальше (на более высоких частотах) доминирует шум. Но при обработке реальных рядов и почти никогда не встречал подобные спектры. В моих данных они билогарифмически-линейно спадают с ростом частоты вниз вплоть до найквиста. Но тогда кто дал нам право экстраполировать выполаживание спектра левее доступного изучению диапазона частот (что эквивалентно допущению о "белости" шума)? По Оккаму, гораздо логичнее просто продолжить эту тенденцию в бесконечность. Да и здравый смысл намекает, что это правдоподобнее. Ведь дискретизация измеряемого сигнала - это наше над ним надругательство, а в действительности-то аналоговый сигнал всегда непрерывный. Поэтому гораздо логичнее взять в качестве "базовой модели" исходного (а не измеренного!) сигнала именно ФШ, у которого нет бесконечной мощности при интегрировании вплоть до нулевого периода.
Но, рассуждая аналогично, на другом (НЧ) конце спектра мы тогда тоже должны допустить аналогичную экстраполяцию "без новых сущностей". И тогда уже она приведет к бесконечной мощности на нулоевой частоте. практически всегда вижу спадающую кривую на билогарифмитческом графике. рядов
> Заметьте, тут про дискретизацию вообще нет речи, и она по сути не требуется. Это уже нюансы цифровой обработки сигналов и их лучше опустить.
Именно так - это наш способ работы с данными. Но когда мы хотим вывести теоретическую формулу, мы же работаем с абстракцией. И для БШ (который теоретически имеет бесконечную мощность, если не ограничивать диапазон частот) все эти формулы почему-то выписываются без проблем. Проблема "нулевого периода" никому не мешает. А вот в варианте с ФШ (где по сути все то же самое, только проблема на нулевой частоте вместо нулевого периода) формулы почему-то не пишутся. Я так и не могу понять - почему.
Вы меня правильно поймите: я сам не смогу вывести нужные формулы ни в одном случае, ни в другом. Но:
(1) я запросто использую те формулы, которые написаны для БШ. Они в любом учебнике есть, причем на все случаи жизни; они прекрасно работают, и никогда (если шум действительно белый) не вступают ни в какое в противоречие ни с здравым смыслом, ни с численными моделями.
(2) С другой стороны, я легко могу показать, что при замене БШ на ФШ все эти формулы работать перестают. И это нельзя исправить никакими "маленькими поправками". Там просто катастрофические расхождения возникают. В варианте ФШ формулы для БШ больше не работают ни в каком приближении.
(3) Ну и с третей стороны, подавляющее большинство временных рядов долговременного мониторинга - это либо строго ФШ, либо почти ФШ. Тут просто нет ни малейших сомнений - достаточно на спектр посмотреть.
А теперь вопрос: почему, несмотря на (2) и (3), у нас нигде нет разумных формул для варианта с ФШ? См., например, мой исходный вопрос про подавление ФШ накоплением. Ну ведь наболело же! Я рецензирую кучу статей в журналах, где авторы на полном серьезе применяют в подобных случаях формулы для БШ. Хотя бред очевидный. И в каждом конкретном случае его можно продемонстрировать элементарно. Вот ваши яблоки, берем из них два, складываем с другими двумя. Теперь видите, что в ответе НЕ 5?
А общей формулы нет!
Чтобы не разбирать в стопятсотый раз в точности одну и ту же ошибку, складывая чемоданы, груши и финики.
Да, аналогия между ФШ и статистическим самоподобием очевидна
Вдогонку: кажется, я сообразил, в чем преимущество Vim! Отвечу сам же себе, т.к. время редактирования прошлого комментария истекает:
> Несмотря на все это, попытка нового знакомства с Vim в моем случае окончилась полным крахом. Прежде всего, "не зашла" концепция двух режимов работы. Зачем, если есть экран, где все видно, и работать "стрелочками" (плюс модификаторы) много проще?
Проще - это же только мне на десктопе!!! Где у меня под рукой два комплекта стрелочек на основной и правой клавиатуре, плюс всякие контролы-шифты и справа, и слева, не говоря уже про всякий
синтаксическийрукопальцевый сахар в виде кучи Fn и т.д. На ноуте такую роскошь еще поищи... Но если там для типичных команд надо сделать три последовательных нажатия вместо одного комбинированного, тогда ой! Тогда я бы и сам, вероятно предпочел двухрежимный редактор, только чтоб так не мучиться. Даже интересно: я угадал или мимо? Можно ли оценить, какой процент завсегдатаев VIM-а работает преимущественно на десктопе? Ну или точнее, сравнить относительную долю VIM-щиков среди тех. кто программирует:а) преимущественно на ноуте
б) преимущественно на дестктопе?
Будет ли в этих группах статистически значимое различие?
@cupraer> Я перешел на vim после мучений с VisualStudio, Idea, Atom, VSCode (в этой последовательности) — примерно в 2017
Я тоже решил познакомиться с Vim примерно в 2017г. До этого (еще в DOS-эпоху) пользовался Omni и Multi-Edit-ом, а позже VisualStudio и Notepade++ (конечно, много других редакторов тоже, но эти были основой). Но поскольку моя сознательная жизнь (еще перед DOS) началась с PDP-11 (=СМ-4), где, вроде бы, стояло что-то из vi-семейства, то решил, так сказать, попробовать
вернуться к истокам
Хотя уже ничего про эти "истоки" не помню. Вроде, сперва на СМ-4 у нас стоял какой-то строчный редактор, но уже при мне он как-то научился имитировать многострочность. Эх, давно это было (где-то 1986г).
Так вот. Несмотря на все это, попытка нового знакомства с Vim в моем случае окончилась полным крахом. Прежде всего, "не зашла" концепция двух режимов работы. Зачем, если есть экран, где все видно, и работать "стрелочками" (плюс модификаторы) много проще?
Нет, я совсем не считаю, что Vim - отстой. Наоборот, я сразу же я оценил наиболее убойную (на взгляд чайника) фичу: для меня это
кратность команд
Только вот в реальной жизни она мне бывает нужна нечасто. Если требуется 2-3-кратный повтор, то мне проще нажать команду два раза, чем искать цифру "3". А если не пару раз, а 15, то это же надо еще сперва посчитать, сколько именно. А мне лень... И лишь в некоторых специфических (но вполне регулярных) случаях мне бывает нужен 5-ти, 7-и т.д.-кратный повтор отдельных команд, чередуя их с разными другими командами. Специально для таких случаев я наплодил себе макросов в Notepade++, благо общий набор таких ситуаций и шаблонов действий у меня ограничен.
А еще у меня не возникло проблемы с выходом
которой тут всех пугают ;-)
т.к. я заранее, еще перед входом в Vim, разузнал о противоядии ;-)
Тем не менее, после пары дней тренировок у меня не возникло чувство, что с уверенным освоением Vim я существенно в чем-то выиграю. Возможно, проблема в том, что меня не особо напрягают ограничения уже освоенных редакторов?
Но вопрос я хотел задать не об этом.
Моим первым "рабочим" редактором в DOS был так называемый Omni. Полноэкранный! И тоже, кстати,
с нетривиальным выходом из него ;-))
Там стояла "защита от дурака": чтобы выйти без сохранения, надо было в специальном окошке ввести имя файла ;-) Ну или символ "*", если имя файлу еще не присвоено. Что как бы намекает на уровень компьютерной грамотности предполагаемых пользователей...
Кстати, он у меня до сих пор
запускается под DosBox-ом
А вопрос вот такой. Если тут еще кто-то помнит про Omni (не важно, хорошее или плохое), сможете рассказать про историю его зарождения/смерти? И в каких отношениях он находился с vi-семейством? Я, к сожалению, не умею в антимонгольский, а русскоязычным поиском ничего особенно не находится. Буду благодарен за ссылки по теме,
включая англоязычные
так как прочитать рекомендованную страницу при наличии переводчика - не проблема. А вот искать на незнакомом языке, особенно когда не умеешь, проблематично
> А статистику какую будем для этого брать?
Во-первых, статистику будем брать от целевого распределения.
А во-вторых, Вы зря думаете, что статистика фамилий радикально отличается для разных социальных групп и профессий. В частности, в обоих упомянутых группах будет гораздо больше фамилий на К или С, чем на Ю или Щ. Думаю, что более точные данные легко можно найти при необходимости.
На мой непросвещенный взгляд (из самых общих соображений), гораздо более сильные различия в частотности фамилий - не профессиональные, а национальные (и, вследствие этого, региональные). Поэтому если мы хотим написать на базе сабжевого принципа более-менее универсальный алгоритм (который будет пригоден для принципиально разных наборов фамилий), то функция коррекции распределения должна вводиться отдельно как настраиваемый параметр алгоритма. Попросту говоря, она должна вычисляться с учетом частотного распределения фамилий в целевой группе.
Таким образом, получается настраиваемый алгоритм: мы один раз анализируем фактическое распределение сортируемых объектов (и это не обязательно фамилии, хотя именно для фамилий выигрыш должен быть очень хорошим), потом строим к нему обратную частотную функцию (приближающую распределение к равномерному), ну а потом можно очень быстро сортировать поступающие списки.
Еще можно время от времени проводить реанализ распределения с учетом обновляющихся данных, и уточнять обратную частотную функцию.
Второй вариант:
Если. к примеру, к нам могут поочередно поступать списки то из Китая, то из Египта, то из Исландии, то тогда заготовим несколько таких корректирующих функций (для каждого региона), а потом применяем соответствующую функцию в зависимости
от источника данных
Если регион заранее неизвестен, но их ограниченное количество, и известно, что смешанных списков почти не бывает, то можно сперва надергать немного (=n-малое) случайных фамилий из поступившего списка, и по ним с хорошей точностью определить регион за O(n-малое)
Короче говоря: вопрос про статистику поставлен правильно, но решается он гораздо проще, чем может показаться на первый взгляд. Если, конечно, нам действительно критична скорость сортировки, и мы готовы заплатить за это усложнением алгоритмов. И, главное, если задача попадает в тот довольно узкий список задач, для которых вся эта оптимизация:
а) эффективна и
б) выигрыш стоит того, чтобы этим всем заморочиться
>> Для unsigned long long int (64 bit) - ексабайт.
> Нет, конечно. Буфер выбирается из тех ресурсов, которые вы можете позволить.
Я что-то туплю: а за что заминусовали ответ про буфер? Вроде бы, там все верно: если у Вас 64-битный ключ, то сперва можно отсортировать по первым 16 (либо 8) битам (т.е. потребуется 65536 либо 256 ящиков=уровней). Потом внутри каждого такого "ящика" - по следующим 16/8 битам. И так далее.
Другой вопрос, что в пределе это и будет та же самая N * logN -сортировка. Ну так никто и не обещал, что предложенный алгоритм годится на все случаи жизни. Это специфическая (но иногда очень выгодная!) оптимизация для специфических случаев.
Например, если у вас 64-битный ключ, но данные по этой шкале раскиданы очень редко (подавляющая часть ключей не используется), то уже после сортировки по первым 16 битам в каждом ящике может оказаться так мало записей, что они за ничтожное время отсортируются другим алгоритмом.
А у меня в реальной жизни (геофизические временные ряды) часто встречаются 64-битные данные (на самом деле обычно 32-битгные, но сейчас это не принципиально), но подавляющая часть из этих значений лежит в середине диапазона, и только малая часть - на краях (= выбросы). А я их хочу упаковать в 16 бит без чрезмерной потери точности (выбросы надо сохранить!). Я для этого делаю log-преобразование, которое приближает распределение к равномерному, после чего трюк с равномерными уровнями прекрасно работает.
Ответить
> Фамилии людей распределены весьма не равномерно.
Если мы заранее знаем, что это будут фамилии, то можно учесть неравномерность распределения, разбив алфавит на
неравные интервалы верхнего уровня
т.е. корректируем "алфавит" так, чтобы распределение фамилий по новым "буквам" стало равномерным. А на этапе распихивания фамилий по "ящикам" (когда нам нужно, чтобы "номер ящика" вычислялся в одно действие) применяем обратную функцию перехода от реального алфавита к вымышленному (на котором распределение равномерное). Для ускорения процедуры эта корректирующая функция может быть максимально простой, т.к. строгая равномерность интервалов не нужна.
P.S. Спасибо автору, что напомнил про этот алгоритм! Я его применял в глубокой древности, генерируя однобайтовые ключи для сравниваемых объектов, и потом распихивая их по 256 значениям ключей. Но сейчас при столкновении с подобной задачкой - уже не факт, что вспомнил бы про такой алгоритм. Теперь не забуду ;-)
Про ветер пока что слишком дешевый развод ;-).
На таком уровне я и сам могу вместо нейросети поиграть ;-))
Лучше попросите нейросеть объяснить то же самое условному "пожизненному" моряку (т.е. никогда не сходившему на берег) или жителю пустыни, где деревьев нет в принципе. А еще уточните, что этот модельный моряк или житель южной/полярной пустыни вообще никогда деревьев не видел, и просто не знает, что это такое. Вот когда она:
1) сначала объяснит ему про деревья - что это за такая приблуда, и как они устроены, и почему у них иногда стволы/ветки качаются (причем все это всерьез!), а потом
2) чуть ниже в том же самом ответе снова напишет про ветер и ветки (но уже согласно игре!!),
то читать станет значительно интереснее ;-))
Как Вы думаете, есть шанс, что получится?
Если да, то было бы очень интересно, чтобы этот текст потом специалист по шизофрении прокомментировал ;-))))
> Пример 3: Поиск максимального элемента в массиве
Простите великодушно, но этот пример я тоже не понял. В чем выигрыш от разбиения массива на части -то? Я вижу только накладные расходы.
Или такой код лучше распараллеливается в некоторых языках? Но тогда хотя бы намекните, в каких. В фортране например, так писать совершенно точно не надо.
.
UPD: И, соответственно, я не могу врубиться в рекомендацию:
> Метод "разделяй и властвуй" используется для задач (...) нахождение минимального/максимального элемента в массиве.
Можете пояснить, что имеется в виду?
Или это рекомендация для языков, где массивы реализованы каким-то экзотическим способом? Но такие языки, вероятно, изначально не преследуют цели быть эффективными при работе с такой структурой. И, соответственно, для решения таких задач лучше взять язык попроще, где самый тупой подход гарантирует О(n), и для этого не надо изобретать какие-то ухищрения...
Простите за глупый вопрос. Я только с очень специфическими алгоритмами сталкивался, а от списков, графов и пр. крайне далек. Да и язык для меня непонятный (я его читаю, как псевдокод). Но:
> Пример: Найти цикл в связном списке
разве приведенный код не дойдет до конца вот такого списка:
1(4), 2(3), 3(2), 4(none)
Тут есть цикл 2-3, но последовательное применение (next) ведет к none. Так же ведь нельзя найти никакой цикл, недостижимый от head-а?
Или слово "связный" в условии означает что в списке нет недостижимых от head-а элементов?
> А может быть у вас полезный сигнал - гармонический неизвестной амплитуды, частоты и фазы?
Да, такие сигналы есть ;-) Например, приливные волны. Но для них все давным-давно построено и посчитано. Частота известна априори, причем абсолютно точно. Амплитуда и фаза - оцениваются, причем борьба идет за пятый-шестой знак в зависимости от качества данных. Основная сложность там даже не в шуме, а в том, что этих волн много, и они не ортогональны. Поэтому процедура оценивания опирается на некоторые трюки. Но в целом эта задача уже решена.
> Тогда задачу можно решить, правда при условии, что корреляционную матрицу остаточной компоненты (фликкер шума) Вам удастся как-то правдоподобно оценить.
Для приливных волн все немного проще: мы там точно знаем частоты, поэтому начинается все с узкополосной фильтрации, после чего наиболее неприятная НЧ-составляющая шума уходит, и все значительно упрощается.
> В этом случае можно поставить банк параллельных фильтров для заданной сетки частот (...)
;-)
Сейчас главная проблема с другими сигналами, которые описанной выше модели не соответствуют. И про которые мы мало что знаем. Поэтому работа с ними строится в "инвертированной" логике: вместо нормальной фильтрации мы хотим сперва подавить шум (про который заранее предположили, что это ФШ), а потом посмотреть - а что там останется?
И уже на основании впечатлений от этого "остатка" абсолютно неформальным образом строить гипотезы про сигнал.
> Тогда тут ключ - существование интеграла
В теории, фликкер-шумом называют целое семейство процессов со степенным параметром от 0.5 до 2. Получается, что интеграл в любом случае разойдется... Не в нуле, так на бесконечности. Хотя, глядя на БШ, чего же тут удивительного. Он же тоже при бесконечной ширине полосы дает
бесконечную мощность...
Даже интересно стало - почему в варианте с БШ теория не замечает вообще никаких проблем? Т.е. для сигналов с наложенным белым шумом абсолютно любые фильтры запросто строятся и работают? Для дискретного сигнала - понятно, там найквист и бесконечностей нет. А для аналогового (если его теоретически рассмотреть) почему бесконечности исчезают? Или там тоже полосу частот при расчетах ограничивают каким-то способом? Подскажете книжку "для чайников", где это разжевано?
> Для ограниченных по времени фрагментов их надо центрировать по фактическому среднему значению.
Это само собой.. но с точки зрения поставленного вопроса о глубине подавления ФШ при накоплении (=избыточности кодирования) такое центрирование ни на что не влияет. Увы.
> И перед накоплением выравнивать по сезонам, то есть синхронизировать по периодам. И, фактически, если вы взяли, например, за один месяц, то будут месячные оценки: модель сигнала периодическая с основным периодом T = 1 месяц.
Тут я не очень понял мысль. Допустим, я считаю месячную периодичность (я ее реально считаю, только годовую). Я беру данные за 100 месяцев и накладываю эпохи (=суммирую), потом делю на 100. Т.е. что-то вроде синхронного детектирования.
Если у меня в сигнале имеется строго периодическая составляющая с периодом 1 мес, то после такой процедуры она никак не изменится (амплитуда "сигнала" после суммирования 100 периодов и деления на 100 = амплитуде исходной периодичности).
А вот с шумом сложнее. Если он некоррелированный, и удовлетворяет условиям ЦПТ, то он должен подавиться (по амплитуде) в корень из N = 100 раз. Дисперсия, соответственно, в 100 раз. А во сколько раз подавится дисперсия ФШ? Чую, что ответ (формула) должен быть совсем простой и вытекать из корреляционных свойств этого самого ФШ. Но вот как именно? АКФ-то у него бесконечная...
Кстати, о предварительном центрировании фрагментов
Тут есть такой нюанс, что если нас интересует только амплитуда/дисперсия шума, то центрирование фрагментов вообще пофиг. Так как после наложения (суммирования) эпох оно (или его отсутствие) выразится в добавлении некой константы к накопленному среднему сигналу.
> Тогда статистики будут конечные.
По идее, реальные сигналы всегда имеют конечную амплитуду и длительность. Проблемы начинаются, когда мы хотим построить для них теоретическую модель. И вот тогда появляется странность: на конечных интервалах времени ограниченные по амплитуде сигналы лучше всего аппроксимируются теоретическим моделями, в которых из каждого угла выглядывают расходимости.
Кстати, очень похожую фичу обнаружил М.Родкин с колегами: ущерб от стихийных бедствий (реальные данные!) лучше всего описывается распределениями с бесконечной дисперсией. Там, между прочим,
целая куча нетривиальных следствий из этого вытекает
Например, несмотря на стационарность процесса, средний ущерб в расчете на одно событие растет по мере увеличения длины ряда. Любой нормальный человек, который в данных этот рост обнаружит, сразу же заподозрит нестационарность процесса,
правда?
А уж с какой безмерной радостью бросаются на этот результат алармисты! "Природа пошла в разнос" и т.д..
Однако же на самом деле для распределений с такими свойствами из описанного (доказанного!) факта, что средний ущерб растет, процесса совершенно не следует. вывод о нестационарности.
Как, впрочем, не следует и обратное (что вывод о нестационарности некорректный ;-)
Но... это мы далеко от темы ушли. Если интересно, можно в отдельной ветке обсудить поподробнее. И ссылок при желании накидаю.
> У Б. Скляра кажется есть такие модели: энергетический сигнал (непериодическая модель, одиночный импульс) и мощностной сигнал (конечный период T, либо бесконечный случайный процесс).
Книжку скачал, буду курить. Только надо нормальную
djvu-читалку поставить
у меня такой формат в экзотике до сих пор - мы, научники, как-то все больше на PDF нажимаем...
> Сдается мне, что длинные хвосты АКФ - влияние полезного сигнала.
Хорошая попытка "хакнуть" Природу, но нет. ФШ по определению дает именно такие хвосты. Если простыми словами, у ФШ-процессов бесконечная память. То есть, автокорреляция не равна нулю на сколь угодно больших лагах.
А насчет полезного сигнала еще веселее. Мы даже этого (какая ПРИМЕРНО у него АКФ) не знаем. Не исключено, что у него то же самое. По крайней мере на доступных для измерения временах...
> Вам надо как-то измерить чистый шум полноценно работающей аппаратуры, когда полезного сигнала нет априори (либо датчики экранированы или как там у вас).
Идея понятная и логичная, у нас даже об этом (про приборные эффекты и соответствие результата измерений фактическим процессам в геосреде) только что была
дискуссия на два номера журнала
Вот эти номера (N3 и N4 за 2024г), там можно скачать постатейно. Ну или можно взять макеты номеров в целом вот тут
Но это не меняет картину принципиально. Так как ФШ идет не от приборных шумов и других подобных эффектов, а непосредственно из изучаемого объекта (планета Земля).
> В Вики для фликкер-шума ничего про нестационарность нет.
Ну так там много чего нет ;-)
Но по определению, ФШ это процесс со степенным спектром при показателе степени от 0.5 до 2.0. Отсюда следует, что в нуле он ВСЕГДА расходится (мощность уходит в бесконечность). Поэтому нестационарность по среднему в любом ФШ будет на абсолютно любом масштабе времени. Можно сказать, что для ФШ-процесса X(t) матожидание E(X(t)) /= E((X(t+dt)) при любом сколь угодно малом dt .
А вот насколько сильно они не равны (точнее, асимптотика по dt), зависит уже от степенного параметра спектра ФШ.
Но на самом деле все еще гораздо хуже. Логическое противоречие начинается уже на этапе определения. Ведь понятие спектра мы изначально вводим для стационарных (периодических) процессов. А потом через него (sic!) определяем ФШ. Который по определению нестационарен. Не удивительно, что в Вики этого нету ;-)
Впрочем, для реализаций конечной длины (которые "не дотягиваются" до нулевой частоты) все это прекрасно работает. Могу показать идеально прямолинейные (в билогарифмических координатах, конечно) спектры реальных (измеренных экспериментально) процессов. Которые твердо лежат на этой прямой на протяжении 4-5 порядков масштаба. ВЧ граница проходит по Найквисту, НЧ - по длине ряда.
И что прикажете с ними делать?
> Со стороны области времени надо всё-таки оценивать АКФ до момента, когда она начнет существенно падать по уровню.
Ну вот увы. По мере стремления частоты к нулю амплитуда спектра у нас уходит на бесконечность. И это не просто заумная абстракция (ведь бесконечной мощности не бывает!), а определение. А самое ужасное в том, что целая куча экспериментальных сигналов (в геофизике - так вообще практически все) в точности ложится на эту модель. Хотя мы точно знаем, что
бесконечных амплитуд не бывает
Даже просто очень больших не бывает (физически невозможно). Но - за время наблюдений (100 лет) мы до таких амплитуд (где ФШ закон нарушается) мы пока еще нигде не дошли. Кстати, есть надежда, что уже скоро (надо еще лет 100) к ним по крайней мере приблизимся. Очень интересно, как тогда тогда поведут себя наши сигналы...
> Чтобы создать алгоритм (метод), надо четко оформить мат. модель сигнала и шума, сделать постановку задачи. Я пока что не понял чем полезный сигнал отличается от шума. Формой? Полосой частот? АКФ? Средним значением?
Отличный вопрос! И ответы под стать вопросу: нет, нет, нет и нет! Прекрасная стартовая позиция для создания оптимального фильтра ;-)))
Для начала я бы сформулировал более простую задачку: у нас есть случайные сигналы и известным спектром. Он степенной. Больше про эти сигналы ничего не известно.
Можем ли мы что-то сказать про разные статистики (функции) этих сигналов?
В общем случае - я подозреваю, что нет. Так как есть расходимость спектра в нуле и все вытекающие из этого бесконечности.
Ну а если у нас есть лишь ограниченные по времени фрагменты реализаций таких процессов?
Тогда - можем?
> У вас тяжелый случай... сигнал неизвестен.
Спасибо за понимание ;-)
В контексте статьи это наверное даже смешно ;-) Но мир настолько разнообразен, что даже в такой ситуации обработка рядов порой приносит ощутимую пользу с точки зрения научного знания... Попросту говоря, "искали то не знаю что", а там и правда что-то интересное обнаружилось ;-)