Provably Efficient Sensor Allocation for Unknown High-dimensional Systems with Limited Sensing

기술적 요약: 제한된 센서를 가진 미지의 고차원 시스템에 대한 증명 가능한 효율적 센서 할당

문제 제기
본 논문은 상태 차원 $r$이 큰 미지의 고차원 선형 동역학 시스템 ($x_{t+1} = Ax_t + Bu_t + w_t$) 에 대해 효율적인 센서 할당을 학습하는 과제를 다룹니다. 목표는 데이터 수집 단계에서 제한된 수의 센서만을 사용하여 시스템이 관측 가능함을 보장하는 최소한의 센서 집합 (상태 좌표) 을 식별하는 것입니다.

기존 접근법은 이러한 설정에서 두 가지 주요 한계에 직면해 있습니다:

1. 모델 의존성: 고전적인 센서 할당 방법은 시스템 행렬 ($A, B$) 에 대한 정확한 지식을 요구하며, 이는 미지의 시스템에서는 사용할 수 없습니다.
2. 데이터 요구 사항: 표준 시스템 식별 (SYSID) 방법은 일반적으로 전체 상태 관측 (부적절하게 비용이 많이 듦) 을 필요로 하거나, 이미 관측 가능성을 보장하는 초기 센서 할당의 존재를 가정합니다 (순환적 의존성).

방법론
저자들은 시스템이 제어 가능하고 안정적이라는 가정 (가정 1 및 2) 하에 이러한 한계를 극복하기 위한 2 단계 프레임워크를 제안합니다.

• 1 단계: 동적 측정 선택을 통한 시스템 식별
  저자들은 전체 상태 측정이거나 사전에 존재하는 관측 가능 할당이 필요하지 않은 새로운 SYSID 알고리즘 (알고리즘 1) 을 소개합니다.

  • 데이터 수집: 모든 상태를 동시에 측정하는 대신, 알고리즘은 $K$개의 궤적을 수집합니다. 각 궤적 $k$에서 소수의 센서 ($\bar{n}$) 가 특정이며 잠재적으로 다른 상태 좌표의 부분 집합을 측정합니다.
  • 측정 전략: 측정 행렬 $C_k$는 모든 상태 좌표가 적어도 $s$개의 궤적에서 관측되도록 ($s_{min} \ge 1$) 순환적으로 설계됩니다.
  • 추정: 알고리즘은 상태 동역학의 재귀적 확장을 활용하여 상태를 과거 입력의 선형 결합 (마르코프 매개변수) 으로 표현합니다. 모든 궤적에 걸쳐 이러한 입력 - 출력 쌍에 대해 최소제곱 회귀를 수행함으로써, 알고리즘은 마르코프 매개변수 행렬 $G = [B, AB, \dots, A^dB]$를 추정합니다.
  • 복원: 추정 순위 $d \ge r$인 경우, 의사역행렬 접근법을 사용하여 추정된 마르코프 매개변수로부터 시스템 행렬 $\hat{A}$와 $\hat{B}$가 이후 복원됩니다.

• 2 단계: 데이터 기반 센서 할당
  1 단계에서 추정된 시스템 행렬을 사용하여, 저자들은 최종 센서 집합을 선택하기 위해 탐욕적 센서 할당 알고리즘 (알고리즘 2) 을 적용합니다.

  • 순위 추정 서브루틴: 중요한 구성 요소는 잡음이 있는 추정치 $\hat{A}$를 사용하여 관측 가능성 행렬 $\mathcal{O}(\hat{C})$의 순위를 추정하는 순위 추정 서브루틴 (알고리즘 3) 입니다. 이 서브루틴은 영이 아닌 특이값과 영인 특이값을 구별하기 위해 추정 오차 경계에 기반하여 신중하게 유도된 임계값을 사용합니다.
  • 탐욕적 선택: 알고리즘은 관측 가능성 행렬의 추정된 순위 증가를 최대화하는 상태 좌표에 센서를 반복적으로 추가하여 완전한 순위 ($r$) 에 도달할 때까지 진행합니다.

• 접근 불가능한 좌표로의 확장
  이 프레임워크는 특정 상태 좌표가 물리적으로 센서 배치에 접근할 수 없는 시나리오로 확장됩니다. 알고리즘은 검색 공간을 접근 가능한 좌표로 제한하고, 마르코프 매개변수의 접근 가능한 행들로 구성된 추정된 행켈 행렬을 활용하여 순위 추정을 수행합니다 (알고리즘 4).

주요 기여 및 이론적 결과

1. SYSID 를 위한 비점근적 오차 경계: 본 논문은 제안된 SYSID 알고리즘에 대한 유한 표본 보장을 제공합니다. 정리 1 은 마르코프 매개변수 추정 오차가 $\tilde{O}(\sqrt{md/(s_{min}T)})$로 감소함을 확립합니다. 여기서 $m$은 입력 차원, $d$는 추정 순위, $T$는 궤적 길이, $s_{min}$은 임의의 상태가 관측되는 최소 횟수입니다. 중요한 점은 충분한 수의 궤적이 수집된다면 단일 센서 ($\bar{n}=1$) 로도 이것이 성립한다는 것입니다.
2. 센서 할당 보장: 정리 2 와 정리 3 은 제안된 2 단계 프레임워크가 관측 가능성을 보장하는 센서 할당을 산출함을 증명합니다. 사용된 센서의 수 $\hat{n}$은 $(1 + \log(r))n^*$로 제한되며, 여기서 $n^*$는 필요한 최적 최소 센서 수입니다. 이 근사 비율은 학습된 근사 모델을 기반으로 작동함에도 불구하고 알려진 시스템에 대한 가장 잘 알려진 결과와 일치합니다.
3. 접근 불가능성에 대한 강건성: 이 프레임워크는 접근 가능한 좌표가 관측 가능성을 보장하기에 충분하다면 (가정 3), 접근 불가능한 상태 좌표를 가진 시스템을 성공적으로 처리합니다.

실험적 검증
저자들은 두 가지 모델에 대한 수치 실험을 통해 접근 방식을 검증했습니다:

• 블록 순환 시스템: 관측 가능성에 대해 블록당 하나의 센서가 필요한 시스템입니다. 알고리즘은 시스템 매개변수를 성공적으로 학습하고 5 개의 센서에 대한 최적 할당을 식별했습니다.
• 열역학 (HVAC): 5 개의 접근 불가능한 좌표를 가진 20 존 시스템입니다. 알고리즘은 접근 가능한 측정값만을 사용하여 동역학을 학습하고 관측 가능성을 보장하기 위해 (블록당 2 개씩) 10 개의 센서에 대한 최적 할당을 식별했습니다.

의의
본 논문은 알려진 모델을 가정하는 이론적 센서 할당과 종종 완전한 관측 가능성이 부족한 실용적 데이터 기반 제어 사이의 간극을 해소한다고 주장합니다. 시스템 식별 과정을 전체 상태 관측 가능성의 요구 사항에서 분리함으로써, 제안된 방법은 센서가 희소하거나 비싸거나 특정 위치로 제한된 고차원 시스템에 대한 효율적인 센서 구성을 학습할 수 있게 합니다. 비점근적 보장은 전력망, 기상 예보, 신경과학과 같은 안전이 중요한 응용 분야에서 이러한 데이터 기반 할당의 신뢰성에 대한 이론적 기반을 제공합니다.