[BOJ] 인공 신경망 - Compy's Blog

인공 신경망

TimeLimit	MemoryLimit	Condition	TAG
3s	1024MB	문제 참고(너무 많은 관계로)	Implementation

솔직히 처음에 이 문제 자체가 호감이었다. 일단 우리학교 문제였고, 인공지능 관련 문제였다. 또한 문제를 풀면서 굉장히 교육적으로 좋은 문제라는 것도 알게 되었는데 굉장히 잘 만든 문제처럼 보인다.

처음은 당연히 그냥 구현 문제인줄 알고 그대로 구현하였다. ps하면서 처음으로 class를 사용해서 구현하는데 꽤 재미있었다. 이런 문제들이 많아지면 좋을 듯!

그래서 Neural을 정의하고, 그걸 연산해서 사용하는 코드를 짰더니 당연히 O(N^3)으로 터지게 되었다. 그래서 어떻게 줄일까? 생각하다가 잠시 질문 게시판을 참고해서 아하 일차식으로 나타내서 한번 계산하면 다른 쿼리 처리를 빠르게 할 수 있구나! 라고 찾을 수 있습니다.

조금 인공지능 얘기를 좀 해보겠습니다.

신경망은 순수하게 선형 연산만을 합니다. 그래서 좀 보자면

은닉층 [input * weight] + bias
출력층 [hidden * weight] + bias

이렇게 순수 선형 연산으로 이루어져 있어서 여러개가 겹쳐져 있더라도 선형 연산을 압축 시킬 수 있다는 이런 특징을 알 수 있구요!

그래서 여러개의 층들을 하나의 입력으로 보자면 어떻게 되는가? 예시로 위의 은닉, 출력을 보자면

은닉층1: y = w1x + b1
출력층: z = w2y + b2

z = (w2*w1)x + (w2b1 + b2)

이렇게 표현 가능하죠?

근데 이렇게 문제를 풀 수 있는데 여기서 좀 더 생각하자면.. 이러한 선형성을 띈다.. 그러면 복잡한 패턴이나 추상적 특징들을 잡아낼 수가 없어요

좀 대표적인 예시를 들자면 XOR이 그때 구현이 안돼서 많이 인공지능 붐이 한번 다시 죽었을 때… 생각을 해봅시다.. 복잡한게 학습이 안되니까 이 선형성을 어떻게 죽일까… 이런 생각을 한거죠

그래서 우리가 activation function을 사용합니다. 왜냐 앞서 말했던 그 “선형적” 특징을 좀 비선형적으로 바꾸기 위해서 사용하는 거죠.

ReLU, Sigmoid를 보통 사용하구… 이 비선형성을 도입함으로써 복잡하고, 추상적인 특징들 패턴들을 알아볼 수 있게됩니다.

그래서 저는 이 문제가 굉장히 많은 것을 알려주고 있다고 생각합니다.

와 다시 생각해봐도 좋은 문제네요

사실 저도 이렇게 깊이 생각은 안 했는데.. 다른 사람들이 푼 것들 말하는 것들을 보면서 좀 더 넓은 시야를 얻을 수 있었던 것 같습니다. 고수님들 언제나 감사합니다!

(사실 밤새고 적었습니다.. 혹시나 오류가 존재하면 알려주셔요!)

정답 코드

#include <iostream>
#include <queue>
using namespace std;

using ll = long long;
int input_layer[2001];

class neural{
public:
    vector<pair<int, int>> inputs; // input, weight
    int bias;
    ll calc;
    neural(vector<pair<int, int>> &inputs, int bias){
        this->inputs = inputs;
        this->bias = bias;
        calc = -1;
    }
    neural(){
        calc = -1;
    }
    
    ll calculation(int *input_layer, bool check){
        if(!check) return calc;
        
        ll result = 0;
        for(pair<int, int> p : inputs){
            auto [input, weight] = p;
            
            int input_value = input_layer[input];
            result += input_value * weight;
        }
        calc = result + (ll) bias;
        return result + (ll) bias;
    }
    
    ll calculation(neural *hidden){
        ll result = 0;
        for(pair<int, int> p : inputs){
            auto [input, weight] = p;
            
            neural input_value = hidden[input];
            result += input_value.calculation(input_layer, false) * weight;
        }
        return result + (ll) bias;
    }
    
    
    
};

neural hidden_layer[2001];

void solution(){
    int n, m, q;
    cin >> n >> m >> q;
    
    vector<ll> final_coefficients(n + 1, 0);
    ll final_bias = 0;

    // hidden layer input
    int c;
    for(int i = 0; i < m; i++){
        cin >> c;
        vector<pair<int, int>> current(c);
        for(int j = 0; j < c; j++) cin >> current[j].first;
        for(int j = 0; j < c; j++) cin >> current[j].second;
        int bias;
        cin >> bias;
        
        neural current_neural = neural(current, bias);
        
        
        hidden_layer[i] = current_neural;
    }
    
    vector<pair<int, int>> current(m);
    for(int i = 0; i < m; i++) current[i].first = i;
    for(int i = 0; i < m; i++) cin >> current[i].second;
    int bias;
    cin >> bias;
    
    neural output = neural(current, bias);
    for(int h = 0; h < m; h++){
        for(auto [input_idx, weight] : hidden_layer[h].inputs) final_coefficients[input_idx] += (ll)weight * output.inputs[h].second;
        
        final_bias += (ll)hidden_layer[output.inputs[h].first].bias * output.inputs[h].second;
    }
    final_bias += (ll)output.bias;
    
    while(q--){
        ll result = final_bias;
        for(int i = 1; i <= n; i++){
            int input;
            cin >> input;
            result += input * final_coefficients[i];
        }
        cout << result << "\n";
    }
}

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    
    solution();
    return 0;
}