필립 클라인의 저서 코딩 더 매트릭스 3장 벡터.

상삼각시스템과 후진대입법을 알아봅니다.
도트곱을 활용해 미국 상원의원들의 투표기록을 간단히 분석해 봅니다.

상삼각시스템의 후진대입법

선형시스템 중 아래와 같은 시스템은 상삼각시스템이라고 불립니다.

\begin{bmatrix} a_{11} & a_{12} & a_{13} & ... & a_{1n-1} & a_{1n} \\ 0 & a_{22} & a_{23} & ... & a_{2n-1} & a_{2n} \\ 0 & 0 & a_{33} & ... & a_{3n-1} & a_{3n} \\ &&&. \\ &&&. \\ &&&. \\ 0 & 0 & 0 & ... & a_{n-1n-1} & a_{n-1n} \\ 0 & 0 & 0 & ... & 0 & a_{nn} \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ . \\ . \\ . \\ x_{n-1} \\ x_n \end{bmatrix} = \begin{bmatrix} \beta_1 \\ \beta_2 \\ \beta_3 \\ . \\ . \\ . \\ \beta_{n-1} \\ \beta_n \end{bmatrix}

상삼각시스템을 이용해 벡터 $x$ 의 엔트리들을 쉽게 구할 수 있습니다. 가장 아래 선형방정식을 이용해 $x_n$ 을 구하고 $x_n$ 의 값을 이용해 그 위의 방정식을 풀면 결국 모든 엔트리들을 구하게 됩니다. 이렇게 해를 구하는 방법을 후진대입법이라 합니다. 아래는 후진대입법을 Python코드로 작성한 예입니다.

from vecutil import Vec, zero_vec

def triangular_solve_n(rowlist, b):
    D = rowlist[0].D
    n = len(D)
    assert D == set(range(n))
    x = zero_vec(D)
    for i in reversed(range(n)):
        x[i] = (b[i] - x * rowlist[i]) / rowlist[i][i]
    return x

후진대입법의 핵심은 $x_i = \frac{\beta_i - x' \cdot a_i }{a_{ii}}$ 식을 이용하는 것입니다. 여기서 $x'$ 은 $0$ 만 포함한 벡터에서 시작해 엔트리해를 하나씩 구할 때 마다 채워가는 벡터입니다. 하지만 후진대입법이 모든 상삼각시스템의 경우에 적용되지는 않습니다. 예를 들어

\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ 0 & a_{22} & a_{23} \\ 0 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} \beta_1 \\ \beta_2 \\ \beta_3 \end{bmatrix}

의 경우는 $x_i = \frac{\beta_i - x' \cdot a_i }{a_{ii}}$ 의 분모가 $0$ 이 되어 하나의 자유변수 $x_3$ 를 둔 채 벡터 해를 구하게 됩니다. 이 경우 해는 유일하지 않습니다.

상원의원의 투표기록

이전에 도트곱을 이용해 간단한 벡터 유사성을 측정할 수 있었습니다. 이를 활용해 미국 상원의원들의 안건에 대한 투표들이 서로 얼마나 유사한지 측정해보겠습니다. 투표기록 파일은 US_Senate_voting_data_109.txt로 여기서 제공됩니다. 텍스트 파일은 한줄에 한명의 의원씩 다음과 같이 저장돼 있습니다.

Clinton D NY -1 1 1 1 0 0 -1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1
Obama D IL 1 -1 1 1 1 -1 -1 -1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 -1

1은 법안에 대한 찬성, 0은 기권 -1은 반대를 의미합니다. 의원 이름을 키값으로 투표기록 리스트에 매핑시키도록 파일을 한줄씩 끊어 문자열을 자르겠습니다.

def create_voting_dict(strlist):
    d = {}

    for s in strlist:
        name = s.split(' ')[0]
        nums = s.split(' ')[3:]
        d[name] = [ int(n) for n in nums ]
    return d

f = open('US_Senate_voting_data_109.txt')
l = list(f)
voting_dict = create_voting_dict(l)

# 변수 voting_dict는 다음과 같습니다.
{
	'Akaka': [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 0, 0, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1],
	'Alexander': [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
	...
}

의원들의 투표기록을 벡터로 갖고 있으니 도트곱을 이용해 유사성을 측정해 보겠습니다.

def policy_compare(a, b, voting_dict):
    return sum([
		a_vote * b_vote
		for a_vote, b_vote in zip(voting_dict[a], voting_dict[b])
	])

policy_compare('Clinton', 'Obama', voting_dict)
>>> 34

Clinton의원과 Obama의원의 유사성은 34입니다. 나중에 모든 의원 쌍의 유사성을 구해보면 알게되겠지만 이는 꽤 높은 수치입니다. policy_compare 프로시저를 이용해 어느 한 의원과 가장 유사성이 높은 또는 낮은 의원을 반환하는 프로시저를 만들어보겠습니다. 가장 높은 유사성을 보이는 의원을 반환하는 most_similar와 그 반대인 least_similar 프로시저는 비교 구문이 반대일 뿐 프로세스가 같기 때문에 프로시저 pick_one를 통해 코드 양을 줄였습니다.

def pick_one(name, voting_dict, compare):
    votes = voting_dict[name]

    others = list(voting_dict.keys())
    others.remove(name)
    pick = others[0]
    pick_sim = policy_compare(name, pick, voting_dict)
    for k in others:
        sim = policy_compare(name, k, voting_dict)
        if compare(sim, pick_sim):
            pick_sim = sim 
            pick = k 
    return pick

def most_similar(name, voting_dict):
    compare = lambda x, y: x > y 
    return pick_one(name, voting_dict, compare)

def least_similar(name, voting_dict):
    compare = lambda x, y: x < y
    return pick_one(name, voting_dict, compare)

most_similar('Chafee', voting_dict)
>>> 'Jeffords'

least_similar('Santorum', voting_dict)
>>> 'Feingold'

이번에는 민주당원들 중 가장 민주당원들과 의견이 일치하는 의원을 찾아보겠습니다. 먼저 민주당원들의 이름을 리스트로 추출합니다. 그리고 각각의 의원들에 대해 민주당원들과 유사성을 측정해 이를 합산하고 민주당원들의 수로 나누어 평균 유사성을 구할 수 있습니다. 벡터 도트곱들의 합에 대한 평균을 구하는 것과 같습니다. $\frac{a_1 \cdot x + a_2 \cdot x + a_3 \cdot x + ... + a_n \cdot x}{n}$ (단 각각의 의원들의 평균 유사성은 자기자신과의 유사성도 식에 합산됩니다. 이는 나중에 도트곱의 덧셈에 대해 결합했을 때의 결과와 비교하기 위함입니다.)

def get_democrats(strlist):
    d = {}

    for s in strlist:
        party = s.split(' ')[1]
        if party == 'D':
            name = s.split(' ')[0]
            nums = s.split(' ')[3:]
            d[name] = [ int(n) for n in nums ]
    return set(d.keys())

def find_avg_similarity(name, name_set, voting_dict):
    sims = []

    for n in name_set:
        sims.append(policy_compare(name, n, voting_dict))
    return sum(sims) / len(sims)

democrats = get_democrats(l)
find_avg_similarity('Clinton', democrats, voting_dict)
>>> 31.325581395348838

Clinton의원의 민주당원들과의 평균 유사성은 $31.32$ 입니다. 같은 민주당원인 Obama의원과의 유사성이 $34$ 인 것에 비해 낮은 수치입니다. 평균 유사성을 구하는 프로시저를 만들었으니 가장 높은 평균 유사성을 보이는 의원을 찾아보겠습니다.

def find_biggest_avg_similarity(name_set, voting_dict):
    average_sims = {
		name: find_avg_similarity(name, name_set, voting_dict)
		for name in name_set
	}
    name_big = list(name_set)[0]
    sim_big = average_sims[name_big]

    for n in name_set:
        if sim_big < average_sims[n]:
            sim_big = average_sims[n]
            name_big = n
	print(sim_big)
    return name_big

find_biggest_avg_similarity(democrats, voting_dict)
>>> 34.86046511627907
>>> 'Biden'

Biden의원은 $34.86$ 로 가장 높은 평균 유사성을 보입니다. 한편 평균 유사성을 구하기 위해 이용했던 식 $\frac{a_1 \cdot x + a_2 \cdot x + a_3 \cdot x + ... + a_n \cdot x}{n}$ 은 도트곱의 덧셈에 대한 분배성을 이용해 다음과 같이 쓸 수도 있습니다. $\frac{(a_1 + a_2 + a_3 + ... + a_n) \cdot x}{n}$ 먼저 벡터들의 덧셈을 한뒤 나중에 한번의 도트곱으로 원하는 값을 찾는 위 식을 구현하기 위해 프로시저 find_average_record를 만들어 보겠습니다.

def find_average_record(name_set, voting_dict):
    record_len = len(voting_dict[ list(name_set)[0] ])
    record_sum = [0] * record_len
	name_set_len = len(name_set)

    for n in name_set:
        record_sum = [ record_sum[i] + voting_dict[n][i] for i in range(record_len) ]
    return [ record_sum[i] / name_set_len for i in range(record_len) ]

average_democrat_record = find_average_record(democrats, voting_dict)
sum([
	average_democrat_record[i] * voting_dict['Biden'][i]
	for i in range(len(average_democrat_record))
])
>>> 34.860465116279066

Biden의원의 평균 유사성은 부동소수점의 정확도를 고려할때, 앞서 도트곱의 덧셈이 분배돼 있었을때와 같은 결과를 보여줍니다. 평균 유사성이 가장 큰 의원을 찾는 프로시저를 마저 작성해보겠습니다.

def most_similar_with_average_record(name_set, voting_dict):
    average_record = find_average_record(name_set, voting_dict)
    most_sim_name = list(name_set)[0]
    most_sim = sum([ average_record[i] * voting_dict[ most_sim_name ][i] for i in range(len(average_record)) ])

    for n in name_set:
        sim = sum([ average_record[i] * voting_dict[n][i] for i in range(len(average_record)) ])
        if most_sim < sim:
            most_sim = sim
            most_sim_name = n
    return most_sim_name

most_similar_with_average_record(democrats, voting_dict)
>>> 'Biden'

가장 의견 일치가 안되는 두 의원들은 누구일까요? 이를 구하기 위해서는 각각의 의원들의 쌍을 비교해야 합니다. 반복횟수를 줄이기 위해 이미 유사성을 측정한 쌍은 제외하도록 코드를 작성해보겠습니다.

def bitter_rivals(voting_dict):
    name_set = list(voting_dict.keys())
    rivals = tuple(name_set[:2])
    rivals_sim = policy_compare(rivals[0], rivals[1], voting_dict)

    for i, a in enumerate(name_set):
		# a와 유사성을 다시 측정할 필요 없으므로 name_set을 i+1 인덱스부터 슬라이스합니다
        for b in name_set[i+1:]:
            sim = policy_compare(a, b, voting_dict)
            if sim < rivals_sim:
                rivals_sim = sim 
                rivals = (a, b)
    print(rivals_sim)
    return rivals

bitter_rivals(voting_dict)
>>> -3
>>> ('Feingold', 'Inhofe')

코딩 더 매트릭스 - 3장 벡터 (3)

상삼각시스템, 후진대입법

2018년 11월 25일

상삼각시스템의 후진대입법

상원의원의 투표기록