학교에서 페스티벌을 한다는 소식을 듣고 작품을 출품해서

 

12월 5일부터 6일까지 세종대학교에서 진행되는 SW인재 페스티벌에 참가했습니다! 

 

타지에 살아서 기차를 타고 세종대에 도착했답니다

아침부터 비몽사몽해서 왔는데 이 화면을 보고나서 페스티벌에 참가하는게 실감이 났어요

(부스 운영은 처음이라 너무너무 떨리고 은근 기대되었답니다?)

 

 

이번 행사는 세종대학교 광개토관 컨벤션홀에서 진행 되었고,

소프트웨어중심대학으로 선정된 58개의 학교가 부스를 운영하고 우수작품을 발표했습니다.

(전국에서 모인 58개 학교를 한 장소에서 볼 수 있기에 흔하지 않은 기회라고 생각하고 열심히 둘러보았어요)

 

 

 

부스가 다른 페스티벌과 달리 개방적인 형태여서 부스에 와주시는 분들도 더 많았고,

설명할 때도 위치나 방향에 제약이 없어서 자유롭게 더 자세하게 설명을 해드릴 수 있었습니다!

다른 학교 학생분들 작품을 구경하고 체험도 할 수 있어서 신기한 경험이었습니다.

 

 

 

 

인기상은 투표를 통해서 정해지는 방식이었는데

그 덕분에 더 열심히 즐기면서 부스를 운영할 수 있었습니다~

(인기상은 못받았지만 내년에도 오게 된다면 우수작품으로 선정될 수 있게 노력할거에요)

 

 

 


저희 학교가 소프트웨어 중심대학에 선정되어서 받는 혜택과 참여할 수 있는 행사가 많아져서 

학교 생활에 다양성과 새로운 경험들도 많이 할 수 있게 되었어요.

2일간 세종대에서 부스를 팀원분들과 교대로 운영하면서 

저희의 작품을 설명할 때 보러와주시는 분들이 다양한 질문을 해주셔서 

저도 더 다양하게 지식을 쌓아야 겠다고 생각하는 계기가 되었고,

저의 부족한 부분을 알고 더 노력을 할 수 있는 계기가 되었습니다.

 

(학교 부스를 운영한다는 생각에 괜히 자부심이 생기고

뭔가 뿌듯하고 자랑스러운 기분이 들었어요

괜히 뭐 된거같구..

나중에는 취업해서 기업 부스 운영으로 참가하고 싶다는 생각,,)

 

다른 부스들을 돌아보면서 신기한 아이디어도 많았고,

실생활에 쓰이면 많은 사람들에게 이로움이 되는 주제도 많았습니다.

 

가장 기억에 남는 체험은

NPC와 채팅으로 대화를 하며

숨겨진 비밀을 찾는 거였습니다

대화 횟수가 제한적이고, 쉽게 알려주지 않아서

어려움이 있었지만

집요하게 물어보고 약점을 공략해서

비밀을 알아낼 수 있었답니다 !!

 

부스 운영 인증사진으로 마무리 하겠습니다~ 

 

 

 


아래는 2024 인재 페스티벌 홈페이지 주소입니다.

행사에 관련된 상세 내용과, 출품작을 보실 수 있습니다.

https://swfestival2024.kr/

 

 

 

 

글 읽어주셔서 감사합니다 :)

오늘은 cifar10을 불러오고 출력해보는 실습을 해보려고 한다.

 

실습은 구글 코랩을 이용해서 진행하였다.

먼저 데이터셋을 불러오기 위한 코드를 작성해보았다.

 

그런데 다음과 같이 밑줄이 생겨서 TensorFlow의 버전이나 설치가 잘 되어있는지 확인하려고 한다.

먼저 버전을 확인해보았는데 2.17.0, 즉 최신 버전이 설치되어 있었다.

 

 

만약 숫자가 1.xxx이렇다면 다음의 코드를 실행하여 업데이트를 진행하면 된다.

 

그럼 버전문제는 아니어서 다른 해결방법을 시도해보았다.


코랩에서 런타임 유형변경을 클릭하여 GPU로 변경해주었다.

다시 실행해보면 잘 실행이 된다.

 

불러온 데이터셋을 간단하게 출력해보려고 한다.

 

 

이 코드를 작성하면 데이터셋을 출력해볼 수 있다.

label을 지정해서 출력할 수도 있고 위와 같이 랜덤으로 출력할수도있다.

통신을 먼저 알아보도록 하겠습니다.

 

통신 : 의사, 감정, 사고를 한쪽에서 다른 쪽으로 전달하는 것이고

다시 말하자면, 한쪽의 데이터를 다른 쪽으로 전달하는 것이라고 할 수 있습니다.

 

먼저 통신의 역사를 간단히 알아보도록 합시다.

 

1) 모스부호(유선)

최초로 전기를 이용한 통신 시스템은 모스부호(morse code) 입니다.

이는 현시대에는 주로 사용하진 않지만 컴퓨터에서 이진수를 사용하는 방식과 유사합니다.

길게 누르는 전송방식과 짧게 누르는 전송방식을 조합하여 데이터를 표현하기 때문입니다.

 

- 모스부호 vs 우편

  • 장점 : 실시간 통신 가능(전기가 연결된 경우)
  • 단점 : 변환이 필요함(인코딩, 디코딩), 양이 제한적임 (너무 긴 문장 전송 어려움)

 

2) 전화

여기서 말하는 전화는 유선전화입니다.

요즘에는 무선 전화를 많이 사용하고 유선 전화를 잘 볼수는 없지만 다들 아실거라고 생각합니다.

 

전선에 모스부호 대신에 사람의 목소리를 전달할 수 있게 된 것이 전화(telephone)입니다.

전선을 통해서 purse가 전송이 되며 아날로그 방식입니다.

telephone의 tele는 먼 거리를 말하고, phone은 음성을 말합니다.

먼 거리에서도 음성을 전하는 것이 가능하게 된 것이죠.

 

여담으로 어렸을 때 가지고 놀았던 실전화도 이 원리로 목소리가 들리는 것입니다.

 

3)무전기, 방송 시스템

최초의 무선통신 시스템은 무전기 입니다. (항상 최초..이런거는 시험에 나왔던 기억이...)

사람들에게 가장 친숙한 통신기기는 방송(broadcasting)시스템입니다.

방송 통신 시스템은 방송국에서 신호를 보내면 tv를 보던 안보던 방송이 송출 되고 있는,

불특정 다수가 신호를 받는 통신 시스템입니다.

 

가장 먼저 보급된 방송 시스템은 라디오 입니다. 

라디오 이후 동영상을 전송할 수 있는 흑백 TV 가 개발되었습니다.

무선신호를 먼 거리에 보내기 위해서는 커다란 안테나가 필요합니다.

인터넷의 발달(네트워크 발전)로 시간적인 제약을 극복하였는데,

이게 주문형 비디오(Video On Demand; VOD)입니다.

OTT(Over The Top) 서비스도 시간적인 제약을 극복한 예 입니다.

 

여기서 간단하게 먼저 얘기를 해보자면

통신 시스템의 종류는 다음과 같습니다.

  • 유니캐스트 : 1 대 1로 통신하는 방식
  • 브로드캐스트 : 1 대 N (불특정 다수, ex) 지상파TV ) - 시간과 공간의 제약이 있음.
  • 멀티캐스트 : 1 대 N (특정 다수, ex) 유료 채널, 넷플릭스)

이는 일단 보기만 하고 나중에 다시 자세하게 알아보도록 하겠습니다.

 

이번 장에서는 통신에 대해서 알아보았습니다.

다음 장에서는 데이터통신에 대해서 알아보도록 하겠습니다. 

 

 

 

 

 

 

 

 

부프로그램이란 함수 정의를 따로 하는 것임

단일의 진입점을 가짐

부프로그램의 실행이 끝나면 제어는 항상 호출 프로그램에게 돌아감

 

 

부프로그램 선언

  • 부프로그램의 프로토콜만 제공(몸체 제공 안함)
  •  타입검사에 이용

형식 매개변수 : 헤더 상에 명세, 사용되는 변수

실 매개변수 : 호출문에 나열된 값이나 구조

 

매개변수 대응 : 부프로그램 호출 시 형식 매개변수는 실 매개변수에 바인딩 됨(위치기반, 키워드 기반)

  • 위치 매개변수 : 실 매개변수 앞에 변수는 형식 매개변수의 앞 변수와 바인딩, 뒤에꺼는 뒤에꺼랑 바인딩
  • 키워드 매개변수 : 형식 매개변수의 이름이 실 매개변수와 함께 명세되는 것
  • ex) Sumer (length = my_length) //length가 형식매개변수, my_length가 실 매개변수
  • 키워드 매개변수에서 위치 매개변수 사용가능함

단, 키워드 매개변수가 나타난 이후에는 남아있는 매개변수는 모두 키워드 매개변수로 작성해야함

ex) Sumer (my_length, //위치 매개변수

                   sum = my_sum, //키워드

                    list = my_array) //키워드

 

디폴트 매개변수 : 형식 매개변수이며 실 매개변수가 전달되지 않으면 디폴트 값 사용

 

Python에서 생략된 디폴트 매개변수 다음에는 반드시 키워드 매개변수가 와야함

ex)def compute_pay( income,  exemptions=1, tax)

 

C++에서 디폴트 매개변수는 리스트의 마지막에 와야함

ex) float compute_pay(float income, float tax, int exemptions=1)

 

 

 

 

 

세자리수 컴퓨팅에서의 goto문

  • 문제점 : 스파게티 코드 (작성 및 해석의 어려움)
  • 해결방법 : 단일 입구, 단일 출구

문장 수준의 흐름제어

  • 순차구조(암시적 형태)
  • 선택구조(IF문)
  • 반복구조(For문)

구조화 프로그래밍

- 공간적 순서가 수행 순서임

- 계층적으로 설계 (반복문 안에 반복문...가능)

 

복합문 : 여러 문장이 모여 하나의 문장을 이룬 형태

ex) ALGOL60 : begin ... end/ C언어 : { } 

 

블록 : 새로운 선언을 포함할 수 있는 복합문

ex) Pascal : begin ... end (블록 지원 안함) / C : {중괄호} , 모든 복합문은 블록임 / python : 들여쓰기

 

선택문 : 둘 이상의 경로 중 하나 선택할 수 있는 제어문

- 양방향, 다중선택 (단방향선택 , 3방향 선택)

 

단방향 선택 : (else가 없는) if문 

양방향 선택 : (then, else가 있는) if문

 

문제점 : 선택문의 중첩

일반적인 해결책 : 짝이 없는 else문 발생 -> 가장 가까운 if문과 짝을 이루자!

-> pascal, C, c++, java

 

해결책 1 : 직접 중첩 금지

Perl에서 then절과 else절이 복합문 => 바깥 if문에 if,else문 포함

 

해결책 2 : 종결어 사용

end if, fi, end 사용

-> Fortran 90, Ada, Ruby

 

해결책 3 : 들여쓰기

-> 파이썬

 

 다중 선택 구조

  • 초기 다중 선택 구조(FORTRAN)
    • 중첩된 if문, goto문으로 만들 수 있음
    • 길고 복잡 비신뢰적임
  • C의 다중 선택구조 (c++,java에서도 채택됨)
    • swith-case문 - 정수형만 가능 
    • 해당하는 조건이 맞으면 그거부터 계속 실행함
    • break문으로 빠져나옴
  • Java의 continue문
    • 이 반복을 종료해서 그 다음 반복으로 가겠다는 의미
    • 해당 반복을 빠져나와서 첫번째 반복문에서 다시 검사를 시작함
  • Java의 label break문
    • 여러 반복문을 빠져나올 수 있음
    • goto 대신 사용함
    • ex) break outerloop; // outerloop명을 가진 루프를 벗어나겠다

 

 

사용자 정의 반복 제어

 

python vs c#,java

  • c#,java는 컴파일 언어로, 변수 타입 선언 필요
  • python는 계수기 변수를 선언하여 리스트 크기를 알아서 그 만큼 반복을 진행해야함
  • c#,java는 알아서 크기 계산해줌. 계수기 필요X

 

goto문 문제점 : 스파게티 코드

goto문이 유용한 예

중첩된 반복문!

- break문을 실행하면 이 반복을 정상종료하고 나온 것인지, break를 통해서 종료된 것인지 알 수 없음

- goto를 사용하면 이해하기 쉽게 할 수 있음

 

 

 

 

 

 

Abstract

이 연구에서는 메타 학습이 이러한 문제를 해결하기 위한 자연스러운 선택임을 보여주고, 이전 접근 방식의 글로벌 모델 대신 매개변수화된 알고리즘(또는 메타 학습자)이 공유되는 연합 메타 학습 프레임워크 FedMeta를 제안합니다. FedMeta는 LEAF 데이터 세트와 실제 생산 데이터 세트에 대한 광범위한 실증 평가를 수행했으며, FedMeta가 연합 학습의 선도적인 최적화 알고리즘인 FedAvg(Federated Averaging)에 비해 더 빠른 수렴으로 필요한 통신 비용을 2.82-4.33배 절감하고 정확도를 3.23%-14.84% 증가시켰음을 입증했습니다. 또한 FedMeta는 매개변수화된 알고리즘만 모바일 장치와 중앙 서버 간에 전송되고 원시 데이터가 서버에 수집되지 않기 때문에 사용자 개인 정보를 보호합니다

 

Introduction

많은 시나리오에서 데이터는 다양한 클라이언트 간에 분산되고 개인 정보 보호에 민감하므로 모델 학습을 위해 중앙 서버에 원시 데이터를 수집하는 것이 비현실적입니다. 한편, 모바일 장치의 스토리지 및 계산 능력이 증가함에 따라 기계 학습 모델 학습과 같은 계산을 클라우드에서 에지 장치로 이동하는 것이 점점 더 매력적으로 다가오고 있습니다.

통계적 문제의 경우, 탈중앙화 데이터는 IID가 아니고 고도로 개인화되고 이질적이어서 모델 정확도가 크게 떨어집니다

체계적인 문제의 경우 장치 수는 일반적으로 기존의 분산 설정보다 훨씬 더 많습니다. 게다가, 각 장치는 저장, 계산 및 통신 용량 측면에서 상당한 제약을 가질 수 있습니다. 이 두 가지 문제를 해결하기 위해 [14]는 SGD를 사용한 로컬 학습의 Epoch 수와 배치 크기를 유연하게 결정할 수 있는 FedAvg(Federated Averaging) 알고리즘을 제안하여 높은 정확도를 달성하고 계산과 통신 비용 간의 균형을 달성했습니다.

 

Meta-learning과 federated learning을 연결한다. Meta-learning에서 매개 변수화 된 알고리즘은 많은 수의 작업에서 천천히 학습되며, 특정 모델은 각 작업의 알고리즘에 의해 빠르게 학습된다. 작업별 모델은 학습된 다음 쿼리 집합에서 테스트되고 테스트 결과는 알고리즘을 업데이트 하는데 사용된다. 반면 federated learning은 알고리즘이 서버에서 유지 관리되고 모델 학습을 위해 클라이언트에 배포된다.

 

comparing federated meta-learning with federated learning

연합 메타 학습 프레임 작업은 서버와 클라이언트 간에 전송되는 정보가 전역 모델이 아닌 알고리즘(매개 변수)이라는 점을 제외하고는 연합 학습과 유사해 보일 수 있습니다. 그러나 Federated learning은 모든 클라이언트의 데이터를 활용하도록 대규모 n-way 분류기를 훈련해야 하는 반면, k-way 분류기는 매번 하나의 클라이언트에 대해 예측을 하기 때문에 충분합니다. 모델이 크면 통신 및 계산 비용이 증가합니다. 관련 매개변수를 업데이트하기 위해 모델의 일부만 클라이언트에 보낼 수 있지만, 이를 위해서는 부분을 결정하기 위해 사전에 클라이언트의 개인 데이터에 대한 지식이 필요합니다. 반면에 메타 학습에서 알고리즘은 다양한 범주를 포함하는 작업을 훈련할 수 있습니다. 예를 들어, MAML(Model-Agnostic Meta-Learning) 알고리즘은 특정 범주에 관계없이 k-way 작업에 대한 메타 학습을 통해 k-way 분류기에 대한 초기화를 제공할 수 있습니다. 따라서 페더레이션 메타 러닝 프레임워크에서는 MAML을 사용하여 n개의 범주를 모두 사용하여 k-way 분류기 초기화를 메타 학습할 수 있습니다. 이러한 방식으로 연합 메타 학습은 통신 및 계산 비용을 상당히 낮춥니다.

 

contributuions

federated setting의 알고리즘 설계 측면에 중점을 두며, 광범위한 실험결과와 함께 새로운 프레임워크 제시.

1. 메타학습이 연합 설정을 위한 자연스러운 선택임을 보여주고, 메타학습 알고리즘을 연합학습과 통합한 FedMeta라는 새로운 연합 학습 메타 프레임 워크 제안

(서버에 데이터가 수집되지 않고 클라이언트 개인정보 보호 가능, MAML 및 Meta-SGD 설명 위한 프레임워크에 통합)

2. LEAF데이터셋에 대한 실험실행하여 FedMeta 프레임 워크에 포함된 실행 예제를 정확도, 계산 비용 및 통신 비용 측면에서 FedAvg와 비교 (FedMeta가 더 적거나 비슷한 오버헤드로 더 높은 정확도를 보임)

3 개인된 기록을 가지고 있는 산업 추천 작업에 FedMeta를 적용하고, 더 높은 정확도를 달성한다는 것을 실험으로 보임.

 

Related work

본 내용은 논문을 참고해주세요.

 

Federated Meta-Learning

이 섹션에서는 제안된 연합 메타 학습 프레임워크를 자세히 설명합니다. 먼저 메타 학습 접근 방식에 대해 논의하고 MAML(Model-Agnostic Meta-Learning)[5] 및 Meta SGD[12] 알고리즘을 실행 예제로 제시합니다. 그런 다음 메타 학습 알고리즘이 연합 설정에서 구현되는 방법을 설명합니다

 

The Meta-Learning Approach

 

메타 학습의 목표는 새로운 작업을 위해 심층 신경망과 같은 모델을 빠르게 훈련할 수 있는 알고리즘 A를 메타 학습하는 것입니다. 알고리즘 A는 일반적으로 매개 변수화되어 있으며, 매개 변수는 작업 모음을 사용하여 메타 학습 프로세스에서 업데이트됩니다. 메타 학습의 작업 T는 지원 집합 DT S = (xi yi) DT S i=1 및 쿼리 집합 DT Q = (xi yi) DT Q i=1 로 구성되며, 둘 다 레이블이 지정된 데이터 포인트를 포함합니다. 알고리즘 A는 서포트 세트 DT S에 대해 모델 f를 훈련시키고 내부 업데이트라고 하는 파라미터 T를 출력합니다. 그런 다음 모델 fT는 쿼리 세트 DT Q에 대해 평가되고 일부 테스트 손실 LDT Q(T)는 A의 훈련 능력을 반영하도록 계산됩니다. 마지막으로, 테스트 손실을 최소화하기 위해 A가 업데이트되며, 이를 외부 업데이트라고 합니다  지원 및 쿼리 집합은 일반화 가능성을 최대화하기 위해 분리되어 있습니다. 메타 훈련은 에피소드 배치가 작업 분포에서 샘플링되는 메타 훈련 방식입니다. 따라서 알고리즘A는 다음 목표에 따라 최적화됩니다.

 

 

 

MAML 알고리즘[5]이 대표적인 그래디언트 기반 메타 학습 방법으로, 그래디언트 업데이트 단계를 통해 모델을 훈련합니다. 알고리즘AforMAML은 모델에 대한 초기화를 제공하기 위해 간단히 사용됩니다. 특히, foreachtaskTthealgorithmmaintain = 이는 modelf의 매개 변수의 초기 값을 제공합니다. 그런 다음 지원 세트DT S에 변형되고 훈련 손실이 있는 기울기 단계를 사용하여 T로 업데이트됩니다LDT S ( ):= 1 DT S (xy) DT S (f (x) y), 여기서 손실함수, 예를 들어 이미지 분류 작업에 대한 교차 엔트로피.마지막으로 fT는 쿼리 세트DT QandthetestlossLDT Q ( T):= 1 DT Q (x y) DT Q (fT (x) y)가 계산된다. 방정식(1)의 최적화 목표는 다음과 같이 인스턴스화됩니다. 여기서 는 내부 기울기 업데이트에 대한 학습률입니다.

 

 

BasedonMAML,Meta-SGD[12]는 초기화 및 저녁 학습 속도를 동시에 학습하기 위해 단계적으로 학습합니다. 테스트 손실LDT Q ( T)는 SGD를 사용하여 외부 루프를 사용하여 외부 루프에서 업데이트 할 수 있습니다. 또한, 학습률은 좌표에 해당하는 동일한 차원의 벡터입니다. Meta-SGD의 최적화 목표는 다음과 같이 작성할 수 있습니다.

 

The Federated Meta-Learning Framework

연합 학습[14] 설정에서 학습 데이터는 클라이언트 집합에 분산되며, 서버에 데이터를 수집하지 않고 모델을 공동으로 학습하는 것을 목표로 합니다. 모델은 클라이언트에 배포되고 학습되며, 서버는 클라이언트에서 수집된 업데이트된 모델의 평균을 구하여 공유 모델을 유지 관리합니다. 휴대폰 사용자를 위한 추천과 같은 많은 실제 응용 프로그램에서 모델은 동일한 클라이언트 집합에 대한 예측을 수행하는 데 사용됩니다.

 

우리는 메타 학습을 연합 학습 프레임워크에 통합합니다. 목표는 클라이언트 간에 분산된 데이터를 사용하여 알고리즘을 공동으로 메타 학습하는 것입니다. MAML을 실행 예제로 사용하여 모든 클라이언트의 데이터를 함께 사용하여 모델에 대한 초기화를 학습하는 것을 목표로 합니다. MAML에는 유지 관리되는 초기화를 사용하여 작업별 모델을 학습하는 내부 루프와 작업의 테스트 손실로 초기화를 업데이트하는 외부 루프의 두 가지 최적화 수준이 포함되어 있습니다. 페더레이션 설정에서 각 클라이언트 u는 서버에서 초기화를 검색하고, 디바이스에 있는 데이터의 지원 세트 Du S를 사용하여 모델을 학습시키고, 별도의 쿼리 세트 Du Q에 대한 테스트 손실 LDu Q( )를 서버로 보냅니다. 서버는 초기화를 유지 관리하고 클라이언트의 미니 배치에서 테스트 손실을 수집하여 업데이트합니다.

 

이 과정에서 전송되는 정보는 모델 파라미터 초기화(서버에서 클라이언트로)와 테스트 손실(클라이언트에서 서버로)로 구성되며, 서버에 데이터를 수집할 필요가 없습니다. Meta-SGD의 경우 벡터는 알고리즘 매개변수의 일부로 전송되고 내부 루프 모델 학습에도 사용됩니다

 

알고리즘 1은 MAML 및 Meta SGD를 사용한 페더레이션 메타 러닝 프레임워크를 보여주며, 여기서 통신 라운드는 메타 러닝 용어의 에피소드에 해당합니다. 알고리즘은 AlgorithmUpdate 프로시저에서 유지 관리됩니다. 각 업데이트 라운드에서 서버는 샘플링된 클라이언트 집합에서 ModelTrainingMAML 또는 ModelTrainingMeta-SGD를 호출하여 테스트 손실을 수집합니다. 메타 학습 후 클라이언트 u에 모델을 배포하기 위해 u의 학습 세트를 사용하여 초기화를 업데이트하고 얻은 u를 사용하여 예측합니다

 

Experiments

 

Evaluation Scheme

모든 실험에서 우리는 무작위로 클라이언트의 80%를 교육 클라이언트로, 10%의 클라이언트를 검증 클라이언트로, 나머지는 테스트 클라이언트로 선택하는데, 이는 새로운 클라이언트로 일반화할 수 있는 능력을 연합 학습의 중요한 속성으로 간주하기 때문입니다. 각 클라이언트에 대해 로컬 데이터는 지원 집합과 쿼리 집합으로 나뉩니다. FedMeta는 제한된 데이터로 신규 사용자에게 얼마나 효율적으로 적응할 수 있는지 연구하기 위해 각 고객에 대한 지원 세트로 사용되는 데이터의 비율 p를 다양화합니다. 이 섹션의 나머지 부분에서는 이 설정을 "p Support"로 나타냅니다.

전통적인 연합 학습의 경우 FedAvg(Federated Averaging algorithm)[14]를 고려하는데, 이는 로컬 SGD(Stochastic Gradient Descent) 업데이트의 평균을 기반으로 하는 휴리스틱 최적화 방법이며 볼록하지 않은 설정에서 경험적으로 잘 작동하는 것으로 나타났습니다. 공정한 비교를 위해 FedAvg(Meta)에 의해 비활성화된 FedAvg의 메타 학습 버전도 구현합니다. 직관적인 FedAvg와 달리 FedAvg(Meta)는 테스트 클라이언트의 지원 세트를 사용하여 서버에서 받은 모델 초기화를 테스트하기 전에 미세 조정하며, 이는 메타 학습의 본질인 "미세 조정을 위한 학습"을 구현합니다. 학습 프로세스 중에 FedAvg 및 FedAvg(Meta)는 모두 학습 클라이언트의 모든 데이터를 사용합니다.

 

연합 메타 학습의 경우 MAML, MAML의 1차 근사치(FOMAML로 표시) [5] 및 Meta-SGD[12]의 세 가지 최적화 지향 알고리즘이 포함되어 있으며, 모두 모델에 구애받지 않는 방법이며 FedMeta 프레임워크 내에서 쉽게 구현할 수 있습니다. FOMAML은 2차 파생 상품이 생략된 MAML의 단순화된 버전으로, MAML과 유사한 성능을 가지면서도 계산 비용이 약 33% 빨라지는 것으로 보고되었습니다[5]. 따라서 시스템 오버헤드를 비교할 때 FOMAML을 추가로 고려합니다. 구현에 대한 자세한 내용은 부록에 나와 있습니다

 

LEAF Datasets

먼저 페더레이션 설정에 대한 벤치마크인 LEAF[3]를 살펴봅니다. LEAF는 세 가지 데이터 세트로 구성됩니다: (1) 62 클래스 이미지 분류를 위한 FEMNIST는 널리 사용되는 MNIST 데이터 세트의 더 복잡한 버전 역할을 합니다[9]. 데이터는 숫자/문자의 작성기를 기준으로 분할됩니다. (2) 윌리엄 셰익스피어 전집(The Complete Works of William Shake speare)[21]에서 발췌한 다음 인물 예측을 위한 셰익스피어. 각 연극에서 말하는 각 역할은 다른 클라이언트로 간주됩니다. (3) Sentiment140 [6] 2-class 감정 분류의 경우, 트윗에 제시된 이모티콘을 기반으로 트윗에 주석을 달아 자동으로 생성됩니다. 각 트위터 사용자는 클라이언트로 간주됩니다. 펨니스트의 경우 CNN 모델을, 셰익스피어의 경우 누적 문자 수준 LSTM 모델을, Sent140의 경우 LSTM 분류기를 사용합니다. 펨니스트, 셰익스피어, 센드140에 대해 각각 10, 20, 25로 설정된 k 레코드 미만의 비활성 클라이언트를 필터링합니다. 데이터 세트 및 채택한 모델에 대한 자세한 내용은 부록에 나와 있습니다.

 

https://arxiv.org/pdf/1802.07876v2

  • I. 소프트웨어 공학 개요

01. 소프트웨어 공학의 배경과 목적

가) 소프트웨어 공학 소개

3가지 핵심 요소 : 프로세스, 전문지식을 갖춘 조직 및 인력, 기술

 

나) 소프트웨어 공학 배경

다) 소프트웨어 공학의 4가지 중요요소

소프트웨어 공학 : "소프트웨어의 개발, 운용, 유지보수 등의 생명주기 전반을 체계적이고 서술적이며 정량적으로 다루는 학문"

 

  1. 방법 : 자료구조, 알고리즘, 코딩 등과 같은 작업들로 구성
  2. 도구 : 생산성 혹은 일관성을 목적으로 사용하는 방법들을 자동화나 반자동화시켜 놓은 것
  3. 절차 : 방법과 도구 결합하여 소프트웨어 합리적이게 개발할 수 있게 함
  4. 사람 : 소프트웨어 공학에서는 사람에 대한 의존성이 상대적으로 큼

02. 소프트웨어 개발 생명주기

가) 정의

소프트웨어 생명주기

: 타당성 검토 -> 개발계획 -> 요구사항 분석 -> 설계 -> 구현 -> 테스트 -> 운용 -> 유지보수

 

나) 목적

: 프로젝트 관리

 

다) 소프트웨어 생명주기 선정

: 프로젝트를 잘 실행하고 리스크를 최소화할 수 있어야겠지.

 

라) 소프트웨어 생명주기 모델 종류

자세한 정보는 생략했으니 깊게 공부하고 싶다면 원본을 보도록 하자.

 

1. V모델

: 프로젝트 적용, 관리 용이

: 프로젝트의 검증 및 확인을 강조하는 모델

 

2. VP모델(V Model with Prototyping)

 프로토타이핑 : 리스크 등을 해결하기 위해 시스템 혹은 일부분을 빠르게 개발하는 방법

 접근방법 1 

불확실성 요소 정의 - 해결책 찾고 적용하기위한 방법 정의 - 해결책 정용해봄(반복 수행 ㄱㄴ) - 결과를 통해 불확실성 요소 원인 찾기

=> 문제가 명확하지 않을 때 적용

 

접근방법 2

불확실성 요소 정의 - 해결책 열거, 선택 기준 정의 - 선택 기준에 따라 해결책 평가 - 가장 적합한 해결책 선택

=> 해결책에 리스크 등이 존재하는 경우에 적용함

 

3. 점증적 모델

: 시스템 개발 시간 줄일 때 유용함

: V모델, VP모델 모두 적용 가능

 

4. 진화 모델

: 시스템에 대한 초기 교육 가능

: 개발 기간 단축

 

 

03. 소프트웨어 개발 방법론

가) 소프트웨어 개발 방법론의 필요성

  • 개발 생산성 향상
  • 효과적인 프로젝트 관리
  • 의사소통 수단 제공
  • 일정 수준의 품질 보증

나) 소프트웨어 개발 방법론 비교

 

다) 소프트웨어 개발 단계

  1. 요구사항 분석 
  2. 설계
  3. 구현
  4. 테스팅

무슨 의미인지 알것같으니 자세한 설명은 생략함

 

04. 애자일 개발 방법론

가) 애자일 방법론 종류

스크럼, 린 소프트웨어 개발 방법론, 익스트림 프로그래밍(XP)...

 

나) 애자일 개발 방법론 - XP

1. XP 개요

2. XP 개발절차 및 용어

유저 스토리 : 요구사항 수집, 필요내용 간단 기재

스파이크 : 어려운 요구사항을 고려한 간단한 프로그램, 사용자 스토리의 신뢰성 증대, 기술 문제 위험 감소

릴리즈 : 배포계획 수립하여 균일 유지

 

3. XP가치

의사소통, 단순성, 피드백, 용기, 존중

 

4. XP 실천방법

5가지 가치 외에 12가지 실천방법 제시

 

 

다) 스크럼

1. 스크럼 개요

2. 스크럼 프로세스

 3가지 미팅 : 일일 스크럼, 스프린트 계획, 스프린트 리뷰

 3가지 산출물 : 제품 백로그, 스프린트 백로그, 소멸 차트

 

3. 스크럼 특징

투명성

타임박싱 : 스크럼 진행하는데 들어가는 시간 제한, 주기적 진행

커뮤니케이션

경험주의 모델

 

 

II. 소프트웨어 재사용

01. 소프트웨어 재사용

가) 소프트웨어 재사용 개요

소프트웨어 재사용 : 자산(기존의 소프트웨어나 지식)을 활용해 새로운 소프트웨어 구축하는 것

자산 - 설계, 요구명세, 검사, 아키텍처 등 포함

 

1. 소프트웨어 재사용 배경

: 생산성 저하, 등

 

2. 소프트웨어 재사용 정의

: 개발 생산성을 높이기 위하여 반복적으로 사용하기에 적합하도록 구성하는 방법

: 품질 생산성 신뢰성 향상, 개발일정 비용 감소

 

3. 소프트웨어 재사용 목적

: 신뢰성, 확장성, 생산성

 

 

나) 소프트웨어 재사용 대상

  1. 일반적 지식
  2. 설계 정보
  3. 데이터 정보
  4. 프로그램 코드
  5. 기타 (투자 대 효과 분석정보, 사용자 지침서, 타장성 조사방법 및 결과, 프로토타입, 인력)

 

다) 소프트웨어 재사용의 원칙

  1. 범용성
  2. 모듈성
  3. 하드웨어 독립성
  4. 소프트웨어 독립성
  5. 자기문서화 : 모듈의 정확한 기능, 용법, 인터페이스를 기술함
  6. 일반성
  7. 신뢰성

라) 실무에서 재사용 구현의 문제점

: 표준화가 부족하고~ 비현실적이고~ 이해가 곤란하고~  등

 

마) 소프트웨어 재사용의 장애요인 및 대책

1. 장애요인

- 거부반응, 동기 결여, 표준화 부재, 사회적 또는 법적 장애

 

2. 장애요인 제거 대책

기술적

- 새로운 설계, 방법론 활용

- 재사용 라이브러리 구축

- 자동화 도구 활용

 

관리, 제도적

- 보상제도 확립

- 능동적인 경영전략

- 조직 변화

 

바) 재사용 적용시 고려사항

사) 소프트웨어 재사용 효과

 

02.역공학

역공학 : 이미 만들어진 시스템을 역으로 추적하여 처음 문서나 설계기법 등의 자료 얻는 것

소프트웨어 유지보수 단계에서 수행

 

장점

: 이미 개발된 소프트웨어 분석 도와줌

: 유지 보수성 향상

 

 

III. 자료구조와 알고리즘

01. 자료구조

가) 정의

자료를 컴퓨터의 기억장치 내에 저장하는 방법, 자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 정의한 것

 

나) 분류

자료구조 : 선형구조/ 비선형 구조

선형구조 : 1:1 관계

비선형 구조 : 1:다/ 다:다관계 

 

순차자료구조

: 메모리저장을 빈자리 없이 순서대로 연속적으로 저장

: 논리적인 순서와 문리적 순서가 일치함

: 삽입 삭제 연산을 해도 빈자리가 없기 때문에 자료가 순서대로 연속하여 저장

: 배열을 이용한 구현

 

 

연결자료구조

: 메모리에 저장된 물리적 위치나 순서에 상관없이 링크에 의해 논리적인 순서 표현하는 방식

: 논리적 순서와 물리적 순서 일치하지 않음

: 삽입 삭제 연산으로 논리적 순서가 변경되어도 링크정보만 변경되어 물리적 순서 변경X

: 포인터를 이용한 구현

 

 

다) 스택과 큐

1. 스택(Stack)

: 선형리스트의 하나로 입력된 순서로 저장되어 LIFO출력

스택 연산 종류

  • top() : 맨 위에 있는 데이터 반환
  • push() : 스택에 데이터 삽입
  • pop() : 스택에서 데이터 삭제하여 반환
  • isemply() : 스택에 원소가 없으면 true 반환, 값을 반환하고 있으면 false값 반환
  • isfull() : 스택에 원소가 없으면 false값 반환, 값을 반환하고 있으면 true값 반환

 

 

2. 큐

: 스택과 유사하지만 데이터가 삽입되는 곳과 삭제되는 곳이 다른 자료구조

: 뒤에서만 삽입되고 앞에서는 삭제만 할 수 있는 구조

: 가장 먼저 삽입한 원소는 가장 먼저 삭제됨

큐의 연산

  • enQueue : 큐에 데이터 삽입, rear를 움직여 큐의 공간 확보한 후 데이터 삽입
  • deQueue :큐에서 데이터 삭제, front를 움직여 가장 오래된 데이터를 다음 번째 데이터로 넘기게 됨.

 

3. 스택과 큐 연산 비교

 

 

라) 트리와 그래프

1. 트리 

: 원소들 간데 계층관계를 가지는 계층형 자료 구조, 1대 다 관계

: 루트노드, 간선, 형제노드, 서브트리

2. 그래프

: 연결되어 있는 원소 사이의 다대다 관계를 표현하는 자료구조

: 정점, 간선의 집합

인접행렬 : 순차 자료구조를 이용한 그래프 구현방식, 2차원 배열을 사용하여 그래프의 두 정점을 연결한 간선의 유무로 행렬 저장하는 방식

 

인접리스트 : 연결 자료구조를 이용한 그래프 구현방식, 각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트로 각 정점의 차수만큼 노드를 연결하는 방식

 

마) 자료구조의 선택 기준

  1. 자료의 처리시간
  2. 자료의 크기
  3. 자료의 활용 빈도
  4. 자료의 갱신 정도
  5. 프로그램의 용이성

 

바) 자료구조의 활용

데이터의 정렬, 검색, 파일 편성 및 인덱스등에서 주로 활용됨

 

 

02. 알고리즘

가) 알고리즘 개요

1. 알고리즘의 정의

주어진 문제를 해결하기 위한 일련의 처리 절차를 단계저그올 기술한 것으로 문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서

=> 처리시간이나 기억장소 사용 측면에서 효율적인 알고리즘 개발하는 것

 

2. 알고리즘 조건

 

 

나) 알고리즘 분석 기준

  1. 정확성
    • 알고리즘이 타당한 입력에 대해서 유한 시간 내에 올바를 결과를 산출하는 가를 판단
  2. 작업량
    • 알고리즘 수행하는데 걸리는 수행 횟수
  3. 기억 장소 사용량
    • 알고리즘이 수행되는 동안 데이터와 정보 등을 저장하기 위해 필요한 컴퓨터 메모리의 사용량
  4. 최적성
    • 시스템의 사용환경(수행량, 메모리 사용량 등)을 고려할 때 그 알고리즘보다 더 적합한 알고리즘이 없다는 것
  5. 단순성
    • 얼마나 이해하기 쉽게 명확하게 작성되었는지

 

 

다) 알고리즘 표현 방법

 

 

라) 알고리즘 성능 분석

  1. 공간 복잡도
    • 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장공간 
    • 공간 복잡도 = 고정 공간량 + 가변 공간량
    • 고정 공간량 : 프로그램, 변수 및 상수들과 같이 프로그램의 크기나 입출력 횟수에 상관없이 고정적으로 피룡한  저장 공간
    • 가변 공간량 : 프로그램 수행과정에서 사용하는 자료와 변수들을 저장하는 공간과 함수 실행에 관련된 정보를 저장하는 공간
  2. 시간 복잡도
    • 시간복잡도 = 컴파일시간 + 실행시간
    • 컴파일시간 : 프로그램 특성과 관련이 적은 고정적인 시간, 컴파일이 되면 프로그램의 수정이 일어나지 않는 한 일정하게 유지
    • 실행시간 : 프로그램의 실행시간으로 컴퓨터의 성능 등에 의존하므로 실제 정확한 실행시간을 측정하기 보다는 명령문의 실행 빈도수를 구하여 계산

알고리즘 비교 시에는 주로 실행 시간을 사용하여 시간복잡도로 나타낼 빅-오 표기법 사용하여 O(n)로 표기

 

 

 

마) 정렬 알고리즘

  1. 정렬의 분류
    • 내부 정렬 : 소량의 데이터에 대해 주기억 장치에 올려서 정렬하는 방식, 데이터 양 제한
    • 외부정렬 : 대량의 데이터에 대해 보조 기억장치에서 정렬하는 방식, 몇개의 서브 파일로 나누어 내부 정렬 할 후 보조기억장치에서 정렬된 각 서브 파일들을 병합하는 방식으로 속도가 느림
  2. 내부 정렬 알고리즘의 분류

   3. 버블정렬

 

 

바) 검색 알고리즘

1. 검색 알고리즘 개요

: 데이터의 정렬 여부에 따라 순차검색, 제어검색

 

2. 검색 알고리즘의 분류

 

 

사) 그래프 탐색 알고리즘

  1. 그래프 탐색
    • 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번식 방문하여 처리하는 연산
  2. 깊이 우선 탐색(DFS)
    • 왼쪽부터 시작
    • A -B-F-G-C-H-I-N-D-J-O-P-E-K-L-Q-M

   3. 너비 우선 탐색(BFS)

  • A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q
  • 인접해있는 노드 방문

 

아) 최소 신장 트리(Minimum Spanning Tree)

  1. 최소 신장 트리 
    • 신장 트리 : 무방향 가중치 그래프 내 모든 정점을 포함, 서로 연결, 사이클을 포함해서는 안되는 트리.
    • 최소 신장 트리 : 가중치의 합이 최소인 신장 트리 - 크루스칼, 프림 알고리즘
  2. 크루스칼 알고리즘
    • 연결된 간선 중 가중치 최소인 간선 선택, 사이클 만드는지 체크함
    • 가중치가 작은 간선을 순서대로 선택
  3. 프림 알고리즘
    • 임의의 한 정점을 선택하여 최소 신장 트리부분에 방문하지 않은 새로운 정점과 간선을 선택하여 확장

 

 

IV. 소프트웨어 설계 원리와 구조적 설계

 

 

추가적인 내용의 자료는 topcit 홈페이지에서 찾을 수 있음

https://www.topcit.or.kr/home.do

MAML에 관심이 생겨서 읽어 본 첫 논문이다.

2017년에 나온 논문이고 이미 유명하니 관심 있으면 한번 쯤은 읽어보도록 하자.

나름대로 쉽게 핵심만 요약해보았다.

https://arxiv.org/pdf/1703.03400v3

먼저 간단하게 예를 들어 설명해보겠다.

어린아이와 딥러닝이 있을 때 각각 개와 고양이 사진을 10,000장씩 학습을 시켰다고 하자.

그런데 말 사진을 보여주게 되면 어린아이와 딥러닝 둘다 말 사진을 알리가 없다.

어린아이에게 말 사진을 보여주며 한 두번 알려주면 어린아이는 말 사진을 이제 구별할 수가 있다.

하지만 딥러닝을 그렇지 않다. ===> 그래서 나온게 메타러닝이라고 할 수 있다.

 

Abstract

Meta learning의 핵심 목표는 다양한 learning task에 학습하고 적은 수의 학습 sample만을 이용하여 새로운 learning task를 해결하는 것이다.

Meta learning은 learn-to-learn 방식으로 작은 예제들로 이전의 경험을 바탕으로 새로운 task를 학습하는 방식이다.

 

 

Introduction

Key idea : 적은 양의 data를 사용하여 gradient updates한 parameter가 최대한의 성능을 보여줄 수 있도록 학습 하는 것

parameter를 확장하지 않는 특징이 있으며, 다양한 모델에 적용이 가능하다.

Sensitivity(민감성)을 극대화 시켜서 작은 local change에도 큰 향상을 보이게 한다.

 

Meta-learning Set up

모델 f를 observation x 로부터 output a 를 매핑한다.

(x1,a1,..., xH, aH) : 입출력 쌍으로 이루어진 training data 이다.

 

 

Meta-learning Algorithm

Meta learning은 θ의 사용방법에 따라 접근 방법이 달라진다. 

  • Metric-based approach
    • 저차원 공간에서 임베딩(θ)하여 가장 가까운 클래스로 분류하는 것이다.
  • Optimization-based approach
    • 효율적인 update방법(θ)을 배워 빠른 학습이 가능하게 하는 것이다.

메타러닝은 Optimization-based approach방식이다.

위의 그림을 설명해보자면, 먼저 목적은 초기 가중치 θ 를 찾는 것이다.

L1,L2,L3 각각의 Loss function을 측정하여 가장 loss가 적은 곳으로 update를 한다.

그리고 그 작업을 계속하여 반복한다.

여기서 gradient의 횟수를 감소시키고, Fine-tuning에 도움을 준다. 

적은 update만으로 θ를 찾는 것을 목표로 한다.

 

앞서 설명한 내용을 알고리즘과 함께 살펴보자. 더 이해가 잘 될 것이다.

  1. 세타를 랜덤 초기화한다.
  2. 아래의 조건에 맞으면 반복한다.
  3. p(T)에서 Ti를 샘플링한다.
  4. 샘플링한 Ti에 대해서 작업을 반복한다.
  5. K의 예시에 대하여 Loss function을 측정하여 평가한다.
  6. Gradient descent를 측정하고 세타 프라임을 update한다.
  7. 작업 루프를 종료한다.
  8. B베타를 이용하여 진행했던 gradient 결과를 세타에 update한다.
  9. 반복을 종료한다.

 

 

Supervised Regression and Classification

few-shot learning을 사용하는데 이것은 Prior datameta learning에 사용하여  적은 데이터로 새로운 task 학습하는 방식이다. 

classification, regression도 사용한다.

앞에서 설명했던 알고리즘과 동일한 단계를 제외한 inner loop만을 설명하겠다.

5. 데이터 포인트 K를 무작위 샘플링한다.

6. K의 예시에 대하여 Loss function을 측정하여 평가한다.

7. Gradient descent를 측정하고 세타 프라임을 update한다.

8. B베타를 이용하여 진행했던 gradient 결과를 세타에 update한다.

 

5번만 차이가 있고 나머지는 순서차이인거 같다.

 

 

'논문리뷰' 카테고리의 다른 글

FedMeta  (0) 2024.05.25

4장은 코드 중심 내용이므로 나중에 깃허브에 올려두도록 해보겠다.

5장 내용 바로 시작해보겠다.

 

  • 변수
    • 이름, 주소, 값, 타입, 존속기간, 영역(scope)
  • 이름 형식
    • 길이가 너무 짧으면 의미 포함이 불가능하다 
      • FORTRAN 95: 최대 31글자이다.
      • C99: 제한이 없으나 처음63개 문자만 의미, 외부 이름은 최대 31자에 제한된다.
      • C#, Ada, Java: 제한 없고, 이름에 포함된 모든 문자는 의미가 있다.
      • C++: 제한 없고, 흔히 언어 구현자가 제한한다.
    • 특수문자
      • PHP : 모든 변수 이름이 $로 시작한다.
      • Perl : 모든 변수이름은 특수문자 $, @, %로 시작되며 각각 scalar, array, hash타입이다.
    • 특수어
    • 키워드
    • 예약어
      • 대부분의 언어에서 특수어는 예약어이다.
  • 주소(l-value)
  • 값(r-value)

 

바인딩

  • 바인딩(binding) - 개체와 속성간의 연관
    • ex) 변수와 타입, 변수와 값, 기호와 연산 등
  • 바인딩 시기: 바인딩이 일어나는 시기
    • 언어 설계 시간 : 연산자기호와 연산간의 바인딩
    • 언어 구현 시간(컴파일러 설계 시간) : 정수 타입과 그 크기 간의 바인딩 in C
    • 컴파일 시간: 변수와 타입간의 바인딩
    • 링킹(linking) 시간 : 라이브러리 함수 호출과 함수 코드와의 바인딩
    • 적재(loading) 시간 : static 변수와 메모리 셀의 바인딩
    • 실행 시간 : 비static 지역 변수와 메모리 셀의 바인딩

 

다음 코드에서 바인딩 시기를 알아보도록 하자.

// In C

int count;

...

count = count + 5

  1. count의 타입  
    • 변수와 타입간의 바인딩이므로 컴파일 시간에 바인딩
  2. count의 가능한 값들의 집합
    • 정수 타입과 그 크기 간의 바인딩 이므로 언어 구현 시간에 바인딩
  3. 연산자 기호 + 의 의미
    • 연산자 기호이므로 언어 설계 시간에 바인딩
  4. 리터럴 5의 내부 표현
    • 정수 타입과 그 크기 간의 바인딩 이므로 언어 구현 시간에 바인딩
  5. count의 값
    • 비static 지역 변수와 메모리 셀의 바인딩 이므로 실행 시간에 바인딩

 

  • 바인딩 유형
    • 정적 : 바인딩이 실행 전에 일어나고, 실행 중에 변경 X
      • 타입 명세가 명시적이거나 묵시적
    • 동적 : 바인딩이 실행 중에 일어나고, 실행 중에 변경 O
  • 타입 바인딩
    • * 정적일 경우
    • 명시적(explicit) : 선언문을 통해 타입 명세
    • 묵시적(implicit) : 디폴트 관례를 통해서 타입 명세 => 타입 추론(type inference)
      • ex) Perl에서 $,@,%
    •  *동적일 경우
    • 변수 타입이 할당문을 통해서 명세

 

변수의 유형

  • 정적
  • 스택-동적
  • 명시적 힙-동적
  • 묵시적 힙-동적

 

 

  • 정적 변수(static variable)

     : 프로그램 실행 시작 전 에 메모리 셀에 바인딩되고, 그 바인딩이 프로그램 실행이 종료될 때까지 유지

 

     장점

      : 효율성, history-sensitive 부프로그램 (이전 값에 따라 현재 값이 달라지는 것) 지원

     단점

     : 유연성 감소( 재귀함수 불가), 기억공간이 변수들 간에 공유 불가

 

 

 

  • 스택-동적 변수(stack-dynamic variable)

     : 선언문이 세련화(elaboration)될 때 기억공간에 바인딩되는 변수

 

     장점

     : 재귀적 부프로그램 지원 , 부프로그램간 메모리 공간 공유 가능

     단점

     : 할당/회수에 따른 실행 부담, 간접 주소지정으로 느린 접근, history-sensitive  부프로그램 지원 불가

 

 

 

 

  • 명시적 힙-동적 변수(explicit heap-dynamic variable)

     : 프로그래머가 명세하는 실행시간 명령 어에 의해서 할당되고 회수되는 이름 없는 변수

      : 메모리 셀은 힙 상에 할당

      : 변수의 타입 바인딩은정적

      : 포인터나 참조 변수를 통해서 참조

          ex) Java의 객체, C++에서 new로 할당되는 객체

 

     장점

     : 동적 자료구조 생성

     단점

     : 예측 불가능하기 때문에 사용,관리 어려움

 

 

 

 

  • 묵시적 힙-동적 변수(implicit heap-dynamic variable)

     : 할당문에 의해서 할당과 반환이 이루어 지는 변수

      : 메모리 셀은 힙 상에 할당

      : 변수의 모든 속성이 값이 할당될 때마다 바인딩

   

     장점

     : 유연성

     단점

     : 컴파일러에 의한 오류 탐지 능력 상실

 

 

프로그래밍 역사에 관한 내용인 2장은 패스하도록 하겠다.

 

이번 장에서는 BNF, 파스트리, 모호성, 연산자 우선순위 등에 대해서 다뤄볼 것이다.

 

언어를 기술하기 위한 방법

  • 구문(syntax)
    • 식, 문장, 프로그램 단위 형태 
  • 의미론(semantics)
    • 식, 문장, 프로글매 단위의 의미

 

용어 구문기술 구성요소

: 문장, 언어, 어휘항목, 토큰

 

토큰에 대한 예를 들어 살펴보자

 index = 2 * count + 17;

식별자 : index, count
연산자 : =, *, +
상수 : 2, 17
분리자 : ;

 

*프로그램을 구성하는 기본 단위

: 변수

:키워드 ex) if, while, int, float

:분리자 ex) (), {}, ;

:연산자 ex) +, -, *, /, >

:함수

 

 

스트링 형태를 표현하는 방법에는 정규문법, 문맥-자유 문법(=문맥무관문법)이 있다.

구문을 기술하는 표기법에는 BNF(Backus-Naur Form)가 있다.

 

BNF에 대해 자세히 다뤄보겠다.

 

 

BNF 개념

  • 논터미널(비단말) symbol, 터미널(단말) symbol로 구성
    • 논터미널 symbol은 추가 설명이 필요한 것이고, 터미널 symbol은 말 그대로 종점이며 더 이상의 설명이 필요없는 것이다.  
  • LHS : 한개의 논터미널로 구성
  • RHS : 터미널과 논터미널들로 구성

<if_stmt> -> if<logic_expr> then <stmt>

논터미널 : <if_stmt>, <logic_expr>, <stmt>
터미널 : ->, if, then
  • BNF는 단순하나 프로그램이 언어의 구문 대부분을 기술한다.

 

 

  • begin A = B + C; B = C end를 유도해보자.
<program> -> begin <stmt_list> end
<stmt_list> -> <stmt>
                    | <stmt>; <stmt_list>
<stmt> -> <var> = <expression>
<var> -> A | B | C
<expression> -> <var> + <var>
                        | <var> - <var>
                        | <var>

*유도 과정

begin <stmt_list>end

begin<stmt>; <stmt_list>end

begin<var>=<expression>; <stmt_list>end

begin<var>=<expression>; <stmt>end

begin A = <expression>; <stmt> end

begin A = <var> + <var>; <var> = <expression> end

begin A = B + C; B = <var> end

begin A = B + C; B = C end

 

- 주어진 문장을 만들기 위해서 순서대로 선택하여 대입하면 되니 한번 해보도록 하자.

 

  • BNF를 EBNF(확장 BNF)로 바꿔보자.
*BNF

<expr> -> <expr> + <term>
                 | <expr> - <term>
                 | <term>
<term> -> <term> * <factor>
                 | <term> / <factor>
                 | <factor>
<factor> -> <exp> ** <factor>
                 |<exp>

<exp> -> ( <expr> )
            | id
*EBNF

<expr> -> <term>{ (+|-) <term>}
<term> -> <factor>{ (*|/) <factor>}
<factor>-> <exp> { (**)<exp>}
<exp> -> ( <expr> )
                | id

 

+ Recent posts