Псевдообратный расчет в Python - PullRequest
Новая
       12

Псевдообратный расчет в Python

0 голосов
/ 02 июля 2018

Задача

Я работал над проблемой, описанной здесь . У меня две цели.

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

Например, в следующем наборе уравнений 

X = a + b
Y = a + b + c
Z = a + b + c + d

Соответствующим выводом должны быть c и d, где X и Y определяют c, а Y и Z определяют d.

Параметры

У меня есть два столбца панд DataFrame с названием InputDataSet , где два столбца: Уравнение и Переменная . Каждая строка представляет членство переменной в данном уравнении. Например, вышеуказанный набор уравнений будет представлен как 

InputDataSet = pd.DataFrame([['X','a'],['X','b'],['Y','a'],['Y','b'],['Y','c'], 
['Z','a'],['Z','b'],['Z','c'],['Z','d']],columns=['Equation','Variable'])

Вывод будет сохранен в DataFrame с двумя столбцами с именем OutputDataSet , где первый содержит переменные, которые имеют уникальное решение, а второй - строку с разделителями-запятыми минимального набора необходимых уравнений решить данную переменную. Например, правильный OutputDataSet будет выглядеть как 

OutputDataSet = pd.DataFrame([['c','X,Y'],['d','Y,Z']],columns=['Variable','EquationList'])

Текущее решение

Мое текущее решение берет InputDataSet и преобразует его в график NetworkX. После разбиения графа на связанные подграфы он преобразует его в матрицу двунаправленности (поскольку граф по своей природе является двудольным). После этого преобразования вычисляется SVD, а nullspace и pseudoinverse вычисляются из SVD (Чтобы узнать, как они рассчитываются, см. здесь и здесь : посмотрите на исходный код numpy.linalg.pinv и функцию cookbook для nullspace. Я объединил две функции, поскольку они обе используют SVD).

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

Вот код: 

import networkx as nx
import pandas as pd
import numpy as np
import numpy.core as cr
def svd_lite(a, tol=1e-2):
    wrap = getattr(a, "__array_prepare__", a.__array_wrap__)
    rcond = cr.asarray(tol)
    a = a.conjugate()
    u, s, vt = np.linalg.svd(a)
    nnz = (s >= tol).sum()
    ns = vt[nnz:].conj().T
    shape = a.shape
    if shape[0]>shape[1]:
        u = u[:,:shape[1]]
    elif shape[1]>shape[0]:
        vt = vt[:shape[0]]
    cutoff = rcond[..., cr.newaxis] * cr.amax(s, axis=-1, keepdims=True)
    large = s > cutoff
    s = cr.divide(1, s, where=large, out=s)
    s[~large] = 0
    res = cr.matmul(cr.swapaxes(vt, -1, -2), cr.multiply(s[..., cr.newaxis], 
cr.swapaxes(u, -1, -2)))
    return (wrap(res),ns)
cols = InputDataSet.columns
tolexp=2
graphs = nx.connected_component_subgraphs(nx.from_pandas_dataframe(InputDataSet,cols[0],
cols[1]))
OutputDataSet = []
Eqs = InputDataSet[cols[0]].unique()
Vars = InputDataSet[cols[1]].unique()
for i in graphs:
    EqList = np.array([val for val in np.array(i.nodes) if val in Eqs])
    VarList = [val for val in np.array(i.nodes) if val in Vars]
    pinv,nulls = svd_lite(nx.bipartite.biadjacency_matrix(i,EqList,VarList,format='csc')
    .astype(float).todense(),tol=10**-tolexp)
    df2 = np.where(~np.round(nulls,tolexp).any(axis=1))[0]
    df3 = np.round(np.array(pinv),tolexp)
    OutputDataSet.extend([[VarList[i],",".join(EqList[np.nonzero(df3[i])])] for i in df2])
OutputDataSet = pd.DataFrame(OutputDataSet)

Вопросы

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

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

Я пытался увеличить допуск (то есть, чтобы округлить коэффициенты в псевдообратном) до 0,1, но даже тогда почти 5000 уравнений имели ненулевые коэффициенты.

Я предположил, что, возможно, псевдообрат рушится на неоптимальном наборе коэффициентов, но псевдообрат Мура-Пенроуза уникален, так что это невозможно.

Я что-то здесь не так делаю? Или подход, который я использую, не даст мне того, чего я хочу?

Дополнительные примечания

  1. Все коэффициенты всех переменных равны 1
  2. Результаты, которые дает текущий алгоритм, являются надежными ... Когда я умножаю любой вектор итогов уравнения на псевдообрат, сгенерированный алгоритмом, я получаю значения, по существу равные тем, которые, как утверждается, имеют уникальное решение, которое является многообещающим.
  3. Здесь я хочу узнать, либо я делаю что-то не так в том, как я экстраполирую информацию из псевдообращенного, либо мой подход совершенно неправильный.
  4. Я прошу прощения за то, что не опубликовал какие-либо фактические результаты, но они не только достаточно велики, но они несколько не интуитивны, так как они переформатированы в XML, который, вероятно, в любом случае объяснит другой вопрос.

Спасибо, что уделили время!

...